Докажите, что в игре «15» нельзя поменять местами фишки «15» и «14», оставив остальные на месте
Закончить намеченное решение
Графы
Выпишите в ряд цифры от 1 до 9 так, чтобы число, составленное из двух соседних цифр, делилось либо на 7, либо на 13
Докажите, что если в задаче 3.33 вместо шести точек взять пять, треугольник с одноцветными сторонами может и не найтись
Задачи с целыми числами. Четные и нечетные числа
Докажите, что в любой компании число тех людей, которые знакомы с нечетным числом членов компании, четно
Навигация
Докажите, что в игре «15» нельзя поменять местами фишки «15» и «14», оставив остальные на месте
Нестандартные задачи по математике
79636
знаков
3
таблицы
0
изображений
16. Докажите, что в игре «15» нельзя поменять местами фишки «15» и «14», оставив остальные на месте.
Идея решения.
Рассмотрим «пустое поле» как отдельную фишку. Мы можем только менять «пустую фишку» с соседними. Поскольку пустая фишка должна попасть на исходное поле, число наших операций должно быть четным. Поэтому мы можем получить конфигурации, отличающиеся от начальной только четным числом перестановок.
17. На 44 деревьях, расположенных по кругу, сидели по веселому чижу. Время от времени какие-то два чижа перелетают на соседнее дерево - один по часовой стрелке, а другой - против. Могут ли все чижи собраться на одном дереве?
Решение.
Пронумеруем деревья по кругу с 1-го по 44-е. Сумма номеров деревьев, на которых сидят чижи либо не меняется, либо уменьшается на 44, либо увеличивается на 44. Тем самым, остаток от деления этой суммы номеров на 44 не меняется. Изначально этот остаток равен 22, а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому чижи не смогут собраться на одном дереве.
18. Можно ли разрезать выпуклый 17-угольник на 14 треугольников?
Общая постановка задачи.
При помощи инвариантов решаются задачи следующего типа: даны множество М (элементы его мы будем называть «позициями») и правило, по которому разрешается переходить от одной позиции к другой; можно ли из данной позиции а перейти за несколько шагов в другую данную позицию p? Более общая задача: как. для произвольной пары позиций а, p установить, можно ли из а за несколько шагов перейти в р?
Очевидно, описанные ситуации обладают следующим свойством: если из позиции a можно перейти в позицию р и из p можно перейти в позицию h, то из a можно перейти в h. Это свойство называется транзитивностью.
Рассмотрим конкретную задачу.
Задача 1. Круг разделен на n секторов, в которых как-то расставлены n фишек. Разрешается одновременно передвинуть любые две фишки: одну — на один сектор по часовой стрелке, другую — на один сектор в противоположном направлении. Можно ли из позиции M, в которой в каждом секторе стоит' по одной фишке, перейти к позиции V, в которой все фишки собраны в каком-нибудь одном секторе?
В данной задаче, кроме свойства транзитивности, имеет место также следующее важное свойство: если из позиции a можно перейти в позицию р, то и из р можно перейти в a. Это свойство называется симметричностью.
Свойство симметричности соблюдается не во всех задачах рассматриваемого типа; например, в шахматах пешки назад не ходят. В этой статье мы ограничимся задачами, для которых условие симметричности выполнено.
Условимся считать, что из любой позиции a можно «перейти» в нее же. Это свойство называется рефлексивностью.
Назовем позиции a и p эквивалентными, если по заданным правилам из a можно перейти в p (ввиду предположенной симметричности это равносильно тому, что из p можно перейти в a). Эквивалентность позиций a и p мы будем обозначать так: a~ p; неэквивалентность — так: a ~/ p.
Поскольку эквивалентность позиций рефлексивна, симметрична и транзитивна, исходное множество М разбивается на непустые непересекающиеся подмножества (рис. 1): М = M1UM2UM3U... В каждом из подмножеств Mi, все позиции эквивалентны: если a из Мi, и p из Mi, то a~ p. Если же позиции a и p принадлежат разным подмножествам: a из Mi p из Mj ( i отлично от j ), то a и p не эквивалентны ). Подмножества Мi мы будем называть орбитами. Повторим еще раз: если мы находимся в позиции a, принадлежащей какой-нибудь орбите Mi, то мы можем, перемещаясь по этой орбите, перебраться из позиции a в любую другую позицию, принадлежащую орбите. С другой стороны, сойти с этой орбиты, т. е. перебраться с позиции a на позицию p, принадлежащую любой другой орбите, мы не можем. Орбит может быть как конечное, так и бесконечное число. Впрочем, если множество М конечно, то, разумеется, и число орбит конечно. Инвариант. Числовая функция f, определенная на множестве «позиций» M, называется инвариантной функцией, или инвариантом, если на эквивалентных позициях она принимает одинаковые значения: если a~ р, то f(а) = f(р). (1)
Задача 1 (продолжение). Пусть п = 2т. Раскрасим секторы через один в серый и белый цвет. Тогда при каждом перемещении число фишек в белых секторах либо не меняется (рис. 2), либо увеличивается на 2 (рис. 3), либо уменьшается на 2 (рис. 4). Для произвольной расстановки a фишек по секторам обозначим через б (а) число фишек в белых секторах. Рассмотрим теперь такую функцию g.
0, если б (a) четно,
g(a) =
1, если б (a) нечетно.
Из сказанного выше вытекает, что эта функция g (четность числа фишек в белых секторах) является инвариантом. Поскольку п = 2т, для конечной позиции v имеем g(v) = 0. Если т = 2k+ 1, то n/2 нечетно. Значит, для начальной позиции w имеем g(w) =1. Из того, что g(w) отлично от g(v) вытекает, что позиции w и v не эквивалентны. Таким образом, в этом случае
(п = 2 т, т = 2 k + 1) из позиции w нельзя перейти в позицию v. Ну, а если т =2 k? Тогда n/2 четно и g(w) = g(v) = 0. В этом случае инвариант g не дает возможности установить эквивалентны позиции w и v или нет.
Дело в том, что если f - инвариант, то из f(a.) = f(p), вообще говоря, ничего не вытекает. Если f(a) отлично от f(p) то позиции а и p не эквивалентны (это следует из (1)). Если же f(a) = f(p), то позиции а и р могут быть как эквивалентными, так и не эквивалентными: инварианту не запрещается на разных орбитах принимать одинаковые значения. (Например, постоянная функция, т. е. функция, которая на всех элементах из М принимает одно и то же значение, тоже инвариантна.)
Как же быть? Попробуйте для какого-нибудь п вида 4k перейти от позиции w, к позиции v... Почему-то не удается. Попробуем Найти другой , более тонкий инвариант.
Занумеруем секторы (скажем, по часовой стрелке) от 1 до n. Для произвольной расстановки а.фишек по секторам обозначим через xk (а) количество фишек в k-м секторе при расстановке a.
Рассмотрим теперь такую функцию q:
q (a)= 1 x1 (a) + 2 x2 (a) +3x3(a) +
+ ... + n xn(a). (2)
Является ли функция q инвариантом?
Произвольное допустимое перемещение (рис. 5) затрагивает 4 слагаемых суммы (2):
... + i xi (a) + (i + 1) xi+1 (a) + ...+ (j - 1) xj -1(a) + j x j(a)+ … (3)
При перемещении , изображенном... + i [xi(a) - 1] + (i + 1) [xi+1(a) + 1]+
+…+(j – 1) [xj-1(a) + 1] + j [x j (a) - 1] +…
Легко проверяется, что обе суммы равны. Итак, q - инвариант! Нет,
мы забыли, что n-й сектор граничит с первым. Значит, есть еще 3 возможности. Подсчет, аналогичный только что сделанному, показывает, что в случае, изображенном на рис. 6, q (a) уменьшится на п, а в случае увеличится на п. В третьем случае q (а), конечно, не изменится. Итак, за одно перемещение значение функции q может измениться, но только на п. Следовательно, функция r, значение которой на расстановке a равно остатку. от деления числа q (a) на п, есть инвариант.
Для позиции v (если все п фишек собраны в 1-м секторе)
x1(v) = x2(v) =…= xl -1(v) = xl+1(v) = …=xn (v) = 0,
xl(v) = n.
Значит, q (v) = l n и r (v) = 0 (каковы бы ни были п и l ). С другой стороны,
x1(w) = x2(w) =…= xn(w) = 1. Значит, q(w) = 1 + 2 + 3 +…+ n = (n(n+1))/2
Если n = 2m, то q(w) = nm + m и r(w) = т =/0 . Следовательно, при четном п получаем r(w) =/ r(v). Итак, при четном п позиции w и v не эквивалентны.
Если же п = 2т + 1, то q(w) = n(m + 1) и r(w) = 0. Таким образом, при нечетном п мы опять имеем: r (и) — r (v). Получается, что при нечетном п вопрос об эквивалентности позиций w и v снова остается открытым.
Универсальный инвариант
Назовем инвариант f универсальным, если на неэквивалентных позициях он принимает различные значения: если a ~/ p, то f(a) ¹f(p) . Таким образом, для универсального инварианта f: если f(a) = f (р), то a ~ р.
Универсальный инвариант на каждой орбите принимает свое значение. Поскольку для универсального инварианта a~p Û f(a) = f(p), универсальный инвариант для любой пары позиций позволяет установить, эквивалентны ояи или нет.
Как проверить, что некоторый инвариант f универсален? Общего метода не существует. Иногда может помочь следующая простая
Теорема. Если а) существуют такие l позиций б1, б2, ..., бl, что каждая позиция a из М эквивалентна одной из них и b) инвариант f принимает, по крайней мере, l различных- значений, то f—универсальный инвариант и позиции бi, бj (i=/j) noпарно не эквивалентны.
Из а) вытекает, что существует не более l орбит. Из b) вытекает, что существует не менее l орбит. Следовательно, существует ровно l орбит. Снова из b) вытекает теперь, что инвариант f принимает ровно l значений и, значит, f универсален. Наконец, из а) вытекает, что позиции б1, б2, ..., бl принадлежат разным орбитам и, таким образом, попарно не эквивалентны.
Задача 1 (окончание). Докажем, что инвариант r универсален. Обозначим через бi, такую расстановку фишек: одна фишка — в i-м секторе, все остальные — в п-м секторе. Под бn мы будем, разумеется, понимать расстановку, при которой все n фишек — в n-м секторе.
Легко сообразить, что любая расстановка эквивалентна одной из позиций б1, б2, ... , бn. В самом деле, пусть a — произвольная расстановка фишек. Попытаемся собрать все п фишек в n-м секторе. Для этого будем передвигать первую фишку, пока не загоним ее в п-ый сектор; одновременно, в соответствии с правилами, мы будем перемещать вторую фишку в противоположную сторону. Затем загоним в n-й сектор вторую фишку, двигая в противоположную сторону третью фишку, и так далее — вплоть до (п— 1)-й фишки. Когда мы загоним п — 1 фишек в n-й сектор, п-я фишка будет в каком-то i-м секторе (i = 1, 2, ... , п). Это и означает, что a~ бi.
Посчитаем r(бi). При i не равном п:
x1(бi) == x2(бi) = …= x i - 1(бi) = x i+1 (бi) =...= xn-1(бi)=0,
xi(бi)=1,
xn(бi)-=n - 1.
Следовательно, q (бi) -= i l + п (п— 1) и r (бi) = i. Кроме того, q(бn) = nn и r(бn) = 0. Итак, инвариант r принимает по крайней мере п значений.
По теореме инвариант r универсален и позиции б1, б2, ... , бn попарно не эквивалентны.
Поскольку r — универсальный инвариант, a ~ р Û r(а) = r(р).
В предыдущем параграфе мы посчитали, что r(w) = r(v) Û n-нечетное. Следовательно, w ~ v ,тогда и только тогда, когда п — нечетное. Задача, наконец, решена полностью.
Задачи
1.19. Докажите, не используя понятия инварианта, что при нечетном п позиции w и v эквиваленты.
1.20. Проверьте, что любая функция от инварианта снова является инвариантом: если f — инвариант и g — произвольная числовая функция, то и функция h : h(a) = g(f(a)) (4) тоже инвариантна.
1.21.Докажите, что любой инвариант можно представить в виде функции от любого универсального инварианта: если h — инвариант, a f — универсальный инвариант, то существует такая числовая функция g, что выполняется (4).
1.22.Определим через универсальный инвариант r из задачи 1 два новых инварианта: f(a) = [r(a)]2; g(a) = [r(а) - 2]2. Докажите, что инвариант f универсален, а инвариант g не универсален.
1.23. Пусть f - универсальный инвариант. Каким условиям должна удовлетворять числовая функция g, чтобы инвариант h, определенный равенством (4), был универсальным?
Задача 2. Даны 20 карточек. На двух карточках написана цифра 0, на двух — цифра 1, ... , на двух последних — цифра 9. Можно ли расположить эти карточки в ряд так, чтобы карточки с 0 лежали рядом, между карточками с 1 лежала ровно одна карточка, ... , между карточками с 9 лежало ровно 9 карточек?
Эту задачу можно решить без всяких инвариантов. Однако для нас она интересна тем, что у нее есть два принципиально разных решения, использующих инварианты.
Представим себе 20 ящиков, расположенных в ряд. Переформулируем теперь нашу задачу следующим образом: можно ли расположить карточки по ящикам так, чтобы выполнялись два условия:
a) карточки с 0 лежат в соседних ящиках, карточки с 1 — через один ящик, ... , карточки с 9— через девять ящиков;
b) в каждом ящике лежит по одной карточке?
Очевидно, порознь выполнить каждое из условий очень легко. Это и приводит к двум решениям.
Первое решение. Положим в первый ящик 10 карточек:
Одну - с 0, одну - с 1, ... , одну - с 9. Затем вторую карточку с 0 положим во второй ящик, вторую карточку с 1 - в третий ящик, .... вторую карточку с 9 — в одинадцатый ящик. Условие а) выполняется. Мы хотим попытаться, не нарушая его, так переложить карточки, чтобы условие b) тоже выполнялось. Разрешим перекладывать любые две «одноименные» (с одной и той же цифрой) карточки через одинаковое число ящиков. Нетрудно заметить, что при произвольном разрешенном перемещении сдвиг в сумме происходит на четное число ящиков. Это подсказывает идею взять в качестве инварианта остаток от деления на 2 суммы номеров ящиков, в которых лежат карточки.
Задачи
Похожие работы
... зміну площ, об'ємів, маси, віку; визначення дня тижня). 4. Задачі геометричного змісту (на просторову орієнтацію, метричні і позиційні задачі). 5. Задачі на рух. Технологія складання нестандартних задач полягає у: а) визначенні параметрів задачі, які покладаються в основу її сюжетної лінії. Наприклад, відстань між двома населеними пунктами; числа; зріст дітей; довжина відрізків; вік хлопчика ...
... «экспериментальных» (52 чел.) и «контрольном» (28 чел.), т. е. в нем участвовало 80 человек. В нашей методике моделировалось проблемное обучение, непосредственно направленное на развитие продуктивного мышления. Она была построена в виде естественного обучающего эксперимента, в котором школьники включаются в проблемные ситуации, рассчитанные на самостоятельное решение новых для них учебных задач. ...
... : 1. Задачи с несформированным условием – задачи, в которых имеются все данные, но вопрос задачи лишь подразумевается. 2. Задачи с избыточным условием – задачи, в которых имеются лишние данные, не нужные для решения, а лишь маскирующие необходимые для решения задачи данные. 3. Задачи с неполным составом условия – задачи, в которых отсутствуют некоторые данные, необходимые для решения задачи, ...
... этом промежутке неравенство (11) также не имеет решений. Итак, неравенство (11) решений не имеет. Ответ: Ø. 3 НЕКОТОРЫЕ ИСКУССТВЕННЫЕ СПОСОБЫ РЕШЕНИЯ УРАВНЕНИЙ Существуют и другие нестандартные методы решения уравнений и неравенств, помимо использования свойств функции. Данная глава посвящена дополнительным методам решения. 3.1 Умножение уравнения на функцию Иногда решение ...
0 комментариев