Страница:
<< 20 21 22 23 24 25 26 >> [Всего задач: 367]
|
|
|
Сложность: 4-
Классы: 7,8,9
|
Найдётся ли среди чисел вида 1...1 число, которое делится на 57?
Решение
См. задачу 34968.
Ответ
Найдётся.
|
|
|
Сложность: 4-
Классы: 9,10
|
На доску выписаны 2011 чисел. Оказалось, что сумма каждых трёх выписанных чисел также является выписанным числом.
Какое наименьшее количество нулей может быть среди этих чисел?
Решение
Пример из 2009 нулей и чисел 1, –1 удовлетворяет условию.
Предположим, что количество нулей не больше 2008. Тогда на доске найдутся либо три неотрицательных числа, среди которых хотя бы два строго положительных, либо три неположительных числа, среди которых хотя бы два строго отрицательны. Пусть выполнено первое: числа a и b положительны, а c неотрицательно. Можно считать, что a – наибольшее из всех выписанных чисел. Но тогда число a + b + c > a не может быть выписанным. Противоречие.
Ответ
2009 нулей.
|
|
|
Сложность: 4
Классы: 8,9,10
|
В течение
92
дней авиакомпания ежедневно выполняла по
десять рейсов. За день каждый самолет выполнял не более одного
рейса. Известно, что для любой пары дней найдется один и только
один самолет, летавший в оба эти дня. Докажите, что есть самолет,
летавший каждый день.
Решение
Рассмотрим
10
самолетов, летавших в первый день. Хотя бы один из
них должен был летать еще, по крайней мере,
10
дней (так как в
каждый из оставшихся
91
день летал один из этих десяти
самолетов).
Рассмотрим самолет, летавший не менее одиннадцати дней. Без
ограничения общности можно считать, что это были дни с первого по
одиннадцатый (и возможно еще какие-нибудь). Предположим, что есть
день
А , в который этот самолет не летал, тогда для каждого из
первых одиннадцати дней и дня
А найдется самолет, летавший в
этот день и в день
А . Для каких-то двух из одиннадцати дней
(например, для первого и для второго) эти самолеты совпадут,
поскольку в день
A совершить более десяти рейсов невозможно.
Получим противоречие: два самолета летало как в первый день, так и
во второй.
|
|
|
Сложность: 4
Классы: 7,8,9
|
11 пионеров занимаются в пяти кружках дома культуры.
Докажите, что найдутся два пионера А и В такие, что все кружки,
которые посещает А, посещает и В.
Решение
Занумеруем кружки числами от 1 до 5 и вместо каждого пионера будем рассматривать тот набор кружков - подмножество множества {1, 2, 3, 4, 5} - который состоит из посещаемых им кружков. Осталось разбить 32 подмножества указанного множества на 10 наборов так, чтобы в каждом из наборов из любых двух множеств этого набора одно содержалось в другом. В качестве таких наборов рассмотрим следующие: [∅, {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5}], [{2}, {2,5}, {1,2,5}, {1,2,3,5}], [{3}, {1,3}, {1,3,4}, {1,3,4,5}], [{4}, {1,4}, {1,2,4}, {1,2,4,5}], [{5}, {1,5}, {1,3,5}], [{2,4}, {2,4,5}, {2,3,4,5}], [{3,4}, {3,4,5}], [{3,5}, {2,3,5}], [{4,5}, {1,4,5}], [{2,3}, {2,3,4}].
|
|
|
Сложность: 4
Классы: 7,8,9,10
|
Сто мудрецов хотят проехать на электричке из 12 вагонов от первой до 76-й станции. Они знают, что на первой станции в два вагона электрички сядут два контролёра. После четвёртой станции на каждом перегоне один из контролёров будет переходить в соседний вагон, причём они "ходят" по очереди. Мудрец видит контролёра, только если он в соседнем вагоне или через вагон. На каждой станции каждый мудрец может перебежать по платформе не далее чем на три вагона (например, из 7-го вагона мудрец может добежать до любого вагона с номером от 4 до 10 и сесть в него). Какое максимальное число мудрецов сможет ни разу не оказаться в одном вагоне с контролёром, как бы контролёры ни перемещались? (Никакой информации о контролёрах, кроме указанной в задаче, мудрец не получает. Мудрецы договариваются о стратегии заранее.)
Решение
Есть хотя бы два вагона, в каждом из которых хотя бы 9 мудрецов, иначе всего их не более чем 9 + 8·11 = 97 < 100. Значит, контролёры смогут сразу же поймать 18 мудрецов.
Покажем, что все мудрецы, кого не получится поймать сразу, не будут пойманы никогда. После появления контролёров до их первого хода каждый мудрец имеет три возможности перебежать в другой вагон. Назовём вагон хорошим, если в момент начала ходов контролёров в нём и в соседних с ним вагонах контролёров нет. В хорошем вагоне мудрец не будет пойман в первый ход контролёров.
Допустим, мудрец находится в первой половине электрички (для второй половины рассуждения симметричны) в вагоне k ≠ 1. Тогда мудрец может действовать следующим образом.
Если он может остаться на месте (то есть в соседних вагонах нет контролёров), то остаётся. Допустим, это не так.
Смотрим, есть ли контролёр в вагоне k + 2. Если есть, то с помощью перебежек k → k + 3 → k + 4 можно оказаться в хорошем вагоне.
Если нет, переместимся в вагон k + 2 и посмотрим, есть ли контролёр в одном из двух следующих вагонов. Если в обоих нет, то хорош вагон k + 3, если есть в k + 3, перебежим в k + 5, иначе перебежим в k + 5 , а потом в k + 6.
Мудрец из вагона 1 может оказаться в хорошем вагоне следующим образом.
Если в вагоне 2 есть контролёр, то он может действовать аналогично предыдущей ситуации для k = 1.
Если контролёра во 2-м вагоне нет, перебежим во 2-й вагон. Если в 3-м нет контролёров, то второй вагон нас устроит.
Если в 3-м вагоне есть контролёр, посмотрим на 4-й. Если там контролёр есть, то перебегаем в 5-й, а потом в 6-й. Если нет, перебегаем в 4-й и смотрим на следующие два. Если и там нет контролёров, идём в 5-й, если есть в 5-м – идем в 7-й, а если есть в 6-м, то возвращаемся в 1-й.
Заметим, что использовано не более трёх перебежек. И оказаться в крайнем вагоне мудрец мог только в случае, если он – в 1-м, контролёры – в 3-м и 6-м, или (для k = 6) он – в 12-м, а контролёры – в 10-м, 7-м или 10-м и 5-м. В последнем случае рассмотрим симметричную ситуацию, в которой мудрец – в вагоне 1, а контролёры – в 3-м и 6-м или 3-м и 8-м. Поэтому далее рассматриваем только мудрецов из вагонов с 1-го по 6-й.
Покажем, что делать, когда контролеры начнут ходить. Назовём активным контролера, который будет следующим ходить и пассивным того, кто только что ходил. Если мудрец видит контролёра, то он знает, является ли тот активным или пассивным: если в его поле зрения появился контролёр или контролёр совершил перемещение по вагонам, то он был активным перед прошлым перегоном, а значит, теперь будет пассивным; если он не совершал перемещения, то будет активным.
Пусть мудрец находится в одном из вагонов 3, 4, 5, 6.
Допустим, мудрец не в вагонах 2, 11. Тогда ему видно пять вагонов, а
перемещаться нельзя разве что в четыре (три из-за активного контролёра и один из-за пассивного). Тогда можно перебежать в оставшийся. Так и сделаем, если этот вагон – не 1-й. В противном случае заметим, что мудрец находится в вагоне 3, а оба контролёра – в соседних с ним вагонах, и мудрец может перебежать в вагон 6.
Допустим, мудрец находился в вагоне 2. Ему видно четыре вагона. Если среди них нет безопасного, то безопасен вагон 5, куда он и перебежит. Пусть есть безопасный.
Если это не 1-й, то перебежим туда. Допустим, безопасен только вагон 1. Если видно двух контролёров, то они в 3-м и 4-м, и можно перебежать в 5-й или остаться во 2-м (в зависимости от того, какой контролёр активен).
Если видно только одного контролёра, тогда он – в вагоне 3. Тогда сначала надо перебежать в 1-й, а после хода этого контролёра (возможно, его придётся подождать) перебежать туда, где был он (в вагон 3). Отметим, что только этот вариант предписывает действия на два хода.
Заметим, что в результате выполнения каждого из вариантов мы оказываемся не в вагоне 1. Это могло случиться только при изначальном расположении, так что контролёры расположены в 3-м и 6-м или 3-м и 8-м. Тогда мудрецу следует подождать хода контролёра из вагона 3 и тогда сразу перебежать на его место. А для начального расположения не в крайнем вагоне перебежки мудреца уже разобраны.
Итак, чтобы было поймано не больше 18 мудрецов, они должны расположиться по 8 в восьми вагонах и по 9 – еще в четырёх, а далее следовать указанному алгоритму.
Ответ
82 мудреца.
Страница:
<< 20 21 22 23 24 25 26 >> [Всего задач: 367]
Фильтр
