Выбрано 4 задачи 
Убрать все задачи
В выпуклом пятиугольнике проведены все диагонали. Каждая вершина и каждая точка пересечения диагоналей окрашены в синий цвет. Вася хочет перекрасить эти синие точки в красный цвет. За одну операцию ему разрешается поменять цвет всех окрашенных точек, принадлежащих либо одной из сторон либо одной из диагоналей на противоположный (синие точки становятся красными, а красные – синими). Сможет ли он добиться желаемого, выполнив какое-то количество описанных операций?
Четыре натуральных числа таковы, что квадрат суммы любых двух из них делится
на произведение двух оставшихся.
Докажите, что по крайней мере три из этих чисел равны между собой.
В сундуке лежали два колпака белого цвета и три черного. В темную комнату завели трех мудрецов и надели на них какие-то колпаки из сундука. Потом вывели в другую комнату. Они не видят, какого цвета колпак на них, но видят колпакки других. Через некоторое время один из них догадался, какого цвета на нем колпак. Как? Какого цвета был колпак?
По кругу расставлено несколько коробочек. В каждой из них может лежать один или несколько шариков (или она может быть пустой). За один ход разрешается взять все шарики из любой коробочки и разложить их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя в каждую коробочку по одному шарику.
а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.
б) Докажите, что за несколько ходов из любого начального размещения шариков по коробочкам можно получить любое другое.
|
|
 |
Условие
По кругу расставлено несколько коробочек. В каждой из них может лежать один или несколько шариков (или она может быть пустой). За один ход разрешается взять все шарики из любой коробочки и разложить их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя в каждую коробочку по одному шарику.
а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.
б) Докажите, что за несколько ходов из любого начального размещения шариков по коробочкам можно получить любое другое.
Решение
а) Текущее состояние описанной в задаче системы определяется количеством шариков в каждой коробочке и указанием коробочки, с которой нужно начинать раскладывать шарики в следующий раз. Поэтому возможных состояний системы конечное число. Из каждого состояния можно, раскладывая шарики, перейти в другое состояние системы, которое определено однозначно. Наоборот, зная состояние системы в настоящий момент, можно однозначно определить состояние системы перед последним раскладыванием шариков. Действительно, последнее раскладывание должно было закончиться на выделенной коробочке; поэтому, чтобы восстановить предыдущее состояние, нужно взять один шарик из выделенной коробочки и далее, идя против часовой стрелки, брать по шарику из каждой коробочки, пока это возможно. Когда же мы встретим пустую коробочку, мы положим в неё все собранные шарики и объявим её отмеченной. Если обозначить состояния системы точками, а возможность перехода из одного состояния в другое – стрелкой, соединяющей соответствующие точки (то есть построить граф состояний системы), то из каждой точки будет выходить ровно одна стрелка и в каждую точку будет входить ровно одна стрелка. Начнём двигаться по стрелкам, начиная с заданного состояния A1. Получаем последовательность состояний A2, A3, ... Поскольку число состояний конечно, в некоторый момент в последовательности {Ai} возникнет повторение. Пусть, например, Ak = An, где k < n. Поскольку в точку Ak входит ровно одна стрелка, из равенства Ak = An следует Ak–1 = An–1, ..., A1 = Ak–n+1. Тем самым, через n – k ходов мы вернулись в состояние A1.
б) В отличие от задачи а) теперь состояние системы определяется лишь тем, как разложены шарики по коробочкам.
Заметим, что если ход ведет из состояния A в состояние B, то, согласно а), мы можем (за несколько ходов) вернуться из B в A. Если мы можем попасть из состояния A в состояние C за несколько ходов, то мы можем вернуться из C в A, "откатывая" ходы по одному. Теперь понятно, что если мы научимся попадать из любого состояния в некоторое фиксированное состояние М, то сможем "путешествовать" между любыми состояниями, "проезжая" через М.
Обозначим через М состояние, когда все шарики собраны в фиксированной коробочке m. Будем при каждой операции брать шарики из ближайшей (против часовой стрелки) к m непустой коробочки. Тогда либо число шариков в m увеличится, либо ближайшая к m непустая коробочка станет еще ближе. Рано или поздно все шарики соберутся в m.
Замечания
баллы: 4 + 4
