Страница:
<< 23 24 25 26 27 28 29 >> [Всего задач: 326]
|
|
|
Сложность: 5-
Классы: 9,10
|
В некотором царстве, территория которого имеет форму квадрата со стороной 2 км,
царь решает созвать всех жителей к 7 ч вечера к себе во дворец на бал. Для
этого он в полдень посылает с поручением гонца, который может передать любое
указание любому жителю, который в свою очередь может передать любое указание
любому другому жителю и т.д. Каждый житель до поступления указания находится в
известном месте (у себя дома) и может передвигаться со скоростью 3 км/ч в любом
направлении (по прямой). Доказать, что царь может организовать оповещение так,
чтобы все жители успели прийти к началу бала.
Решение
Организуем оповещение следующим образом. Разобьём царство на 4 квадрата со
стороной 1 км — квадраты 1-го ранга; каждый из этих квадратов разобьём на 4
квадрата со стороной 1/2 км— квадраты 2-го ранга, эти квадраты в свою
очередь на квадраты 3-го ранга (со стороной 1/4 км) и т. д., пока не дойдём
до столь большого ранга
n, что в каждом квадрате этого ранга будет не более
одного жителя царства (жителей, попавших за общую границу нескольких
квадратов нужно произвольно распределить по этим квадратам). Оповещение будет
происходить поэтапно. Цель 1-го этапа — оповестить по одному жителю в
каждом из (населённых) квадратов 1-го ранга, после чего гонец и все посыльные
должны вернуться в исходные пункты. На 2-м этапе каждый из уже оповещённых
жителей, действуя как гонец на 1-м этапе, устраивает оповещение каждого из
квадратов 2-го ранга а своем квадрате 1-го ранга, на 3-м этапе оповещаются по
одному жителю в каждом квадрате 3-го ранга и т. д.. После
n-го этапа будут
оповещены все жители.
Оценим время, необходимое для 1-го этапа оповещения. Поскольку расстояние
между любыми двумя точками квадрата со стороной 2 км не превосходит
2
км, при скорости 3 км/ч его можно пройти меньше чем за 1 ч.
Поэтому по схеме, показанной на рисунке, 1-й этап можно осуществить не более
чем за 3 ч (гонец
A оповещает жителей
B и
C, житель
B - жителя
D;
если в одном из квадратов 1-го ранга жителей не окажется, время оповещения
может только сократиться). Второй этап повторяет первый одновременно в
четырёх квадратах с вдвое меньшей стороной — он потребует не более 3/2 ч;
вообще,
k-й этап осуществляется за
ч, а для оповещения всех жителей понадобится
3 + 3/2 + ... +
< 6 ч.
Таким образом, к 6 часам вечера все жители получат приглашение на бал;
ещё час им потребуется, чтобы прибыть во дворец.
|
|
|
Сложность: 5-
Классы: 8,9,10
|
В колоде
n карт. Часть из них лежит рубашками вверх, остальные – рубашками вниз.
За один ход разрешается взять несколько карт сверху, перевернуть полученную стопку и снова положить
ее сверху колоды. За какое наименьшее число ходов при любом начальном расположении карт можно
добиться того, чтобы все карты лежали рубашками вниз?
Решение
За
n ходов.
Докажем сначала, что не более чем за
n ходов всегда можно положить все
карты рубашками вниз. Если изначально все карты лежат рубашками вниз, то
утверждение доказано. В противном случае разобьем колоду на группы подряд
идущих карт, лежащих одинаково (т.е. в каждой группе все карты лежат либо
рубашками вверх, либо рубашками вниз). Перевернем самую верхнюю группу.
Тогда число групп уменьшится на единицу. Будем далее повторять эту
процедуру до тех пор, пока не останется одна группа, т.е. все карты в
колоде будут лежать одинаково. Так как изначально было не более
n групп,
то для этого потребуется не более
n-1
ходов. Полученную в результате
группу можно, если это необходимо, за один ход перевернуть, добившись,
чтобы все карты лежали рубашками вниз.
Покажем теперь, что существует расположение карт, при котором нельзя
получить требуемое расположение карт в колоде менее, чем за
n ходов. Так
как каждый ход, как легко проверить, уменьшает число групп не более, чем
на единицу, то колода, содержащая
n групп, может быть приведена к одной
группе минимум за
n-1
ходов. Рассмотрим колоду, в которой нижняя карта
лежит рубашкой вверх, вторая снизу – рубашкой вниз, и так далее. Если
каждый раз делается ход, уменьшающий число групп, то вся колода
целиком не переворачивалась, поэтому через
n-1
ходов такая колода будет
приведена к одной группе, в которой все карты лежат рубашками вверх (т.е.
так, как первоначально лежала нижняя карта). Следовательно, понадобится
n -й ход, чтобы перевернуть все карты и положить их, как требуется в
условии задачи. Если же, кроме
n-1
ходов, уменьшающих число групп, будут
сделаны какие-то ходы, не уменьшающие число групп, то, очевидно, всего
будет сделано не менее
n ходов. Таким образом, указанную колоду нельзя
привести к одной группе менее, чем за
n ходов.
Ответ
За
n ходов.
|
|
|
Сложность: 5-
Классы: 8,9,10
|
В государстве n городов, и между каждыми двумя из них курсирует экспресс (в обе стороны). Для каждого экспресса цены билетов "туда" и "обратно" равны, а для разных экспрессов эти цены различны. Докажите, что путешественник может выбрать начальный город, выехать из него и проехать последовательно на n – 1 экспрессах, платя за проезд на каждом следующем меньше, чем за проезд на предыдущем. (Путешественник может попадать несколько раз в один и тот же город.)
Решение
Уберём все экспрессы, а затем начнём запускать их обратно по одному в порядке возрастания цены (первым запустим самый дешёвый, вторым – самый дешёвый из остальных, и т. д.). В каждый момент в каждом городе будем писать максимальное количество экспрессов, на которых можно последовательно проехать, начав из этого города, так, чтобы цены проезда монотонно убывали.
В начальный момент все числа в городах равны нулю. Пусть в некоторый момент мы вводим экспресс, соединяющий города A и B, в которых до этого были написаны числа a и b соответственно. После введения нового экспресса в A будет число, не меньшее b + 1 (ибо теперь из A можно проехать новым экспрессом в B, а затем по маршруту длины b, начинавшемуся из B). Аналогично, в B будет написано число, не меньшее a + 1. Поэтому сумма чисел в A и B увеличится хотя бы на 2, а числа в остальных городах не уменьшатся. Значит, и сумма всех чисел в городах увеличится хотя бы на 2.
Таким образом, когда все экспрессы будут введены, сумма чисел в городах станет не меньше, чем n(n – 1). Значит, хотя бы в одном городе будет число, не меньшее n – 1. Это и означает наличие требуемого маршрута из этого города.
|
|
|
Сложность: 5-
Классы: 10,11
|
Двое игроков играют в карточную игру. У них есть колода из n попарно различных карт. Про любые две карты из колоды известно, какая из них бьёт другую (при этом, если A бьёт B, а B бьёт C, то может оказаться, что C бьёт A). Колода распределена между игроками произвольным образом. На каждом ходу игроки открывают по верхней карте из своих колод, и тот, чья карта бьёт карту другого игрока, берёт обе карты и кладёт их в самый низ своей колоды в произвольном порядке по своему усмотрению. Докажите, что при любой исходной раздаче игроки могут, зная расположение карт, договориться и действовать так, чтобы один из игроков остался без карт.
Решение
Выпишем все возможные ситуации, которые могут встретиться в игре (то есть все возможные пары колод у участников). Назовём ситуацию финальной, если все карты у одного игрока; критической, если у одного из игроков ровно одна карта; и регулярной, если у обоих игроков хотя бы по две карты. Проведём стрелку от каждой ситуации к ситуациям, которые могут из неё получиться после одного хода. Тогда из любой нефинальной ситуации ведут две стрелки, а из любой финальной – ноль. Нам надо доказать, что из каждой нефинальной ситуации по стрелкам можно дойти до финальной.
Выясним, сколько стрелок ведут в каждую ситуацию. Предположим, что она получилась в результате какого-то хода, в котором карты взял первый игрок. Тогда у него оказалось хотя бы две карты, которые лежат в конце колоды; при этом известно, что одна из них – a – бьёт другую – b. Значит, в этом случае карта a была у первого игрока, а карта b – у второго, то есть предыдущая ситуация восстанавливается однозначно. Итак, если наша ситуация регулярна, то на предыдущем ходе карты мог получить любой из двух игроков, и в каждом из этих случаев предыдущая ситуация восстанавливается однозначно. Значит, в каждую регулярную ситуацию ведут ровно две стрелки. Аналогично в каждую нерегулярную ситуацию ведёт ровно одна стрелка.
Предположим, что из некоторой ситуации S нельзя попасть в финальную. Назовём ситуацию достижимой, если в неё можно добраться из S. Из каждой достижимой ситуации ведут две стрелки в достижимые. С другой стороны, в каждую достижимую ситуацию ведёт не более двух стрелок из достижимых. Это возможно только в том случае, если в каждую достижимую ситуацию ведёт ровно по две стрелки из достижимых. Из этого, в частности, следует, что все достижимые ситуации регулярны. Более того, поскольку в каждую ситуацию ведёт не более двух стрелок, получаем, что все стрелки, входящие в достижимые ситуации, выходят также из достижимых.
Пусть в ситуации S у первого игрока k > 1 карт. Тогда в одной из двух ситуаций, из которых ведут стрелки в S, у первого игрока k – 1 карта – назовём эту ситуацию S1; по показанному выше, она достижима. Аналогично, если k – 1 > 1, то в одной из двух ситуаций, из которых ведут стрелки в S1, у первого игрока k – 2 карты; назовём её S2 и продолжим рассуждения. В итоге мы получим цепочку из достижимых ситуаций S1, S2, ..., Sk–1, причём в Sk–1 у первого игрока одна карта, то есть она критическая, и в неё входит только одна стрелка. Но в каждую достижимую ситуацию должно входить две стрелки. Противоречие.
|
|
|
Сложность: 5-
Классы: 8,9,10
|
За круглым столом сидят десять человек, перед каждым – несколько орехов.
Всего орехов – сто. По общему сигналу каждый передаёт часть своих орехов соседу справа: половину, если у него (у того, кто передаёт) было чётное число, или один орех плюс половину остатка – если нечётное число. Такая операция проделывается второй раз, затем третий и так далее, до бесконечности. Докажите, что через некоторое время у всех станет по десять орехов.
Решение
Отберём у каждого из сидящих за столом по 10 орехов (у некоторых при этом число орехов может стать отрицательным). При этом из каждой “половины” (отдаваемой соседу и оставляемой у себя) вычтется по 5 орехов. Поэтому правило передачи орехов не нарушится. Теперь общее число орехов за столом равно нулю, и нам надо доказать, что через некоторое время у каждого из сидящих за столом будет по 0 орехов.
Занумеруем сидящих за столом по порядку числами от 1 до 10 так, что первый передает орехи второму, второй – третьему, ..., десятый – первому. Пусть у
k-го человека в данный момент
xk орехов, а по сигналу он отдаёт соседу
ak и оставляет себе
bk орехов.
Рассмотрим сумму
S = |
x1| + |
x2| + ... + |
x10|. Так как числа
ak и
bk одного знака (или хотя бы одно из них равно нулю), то |
xk| = |
ak + bk| = |
ak| + |
bk|, то есть
S = |
a1| + |
b1| + ... + |
a10| + |
b10|.
После передачи орехов у
k-го человека будет
ak–1 +
bk орехов (если условиться, что
a0 =
a10). Значение суммы
S теперь равно
|
a10 +
b1| + |
a1 +
b2| + ... + |
a9 +
b10| ≤ |
a1| + |
b1| + ... + |
a10| + |
b10|.
Таким образом,
S не увеличивается. Более того, неравенство становится строгим (
S уменьшается),
если хотя бы для одного из значений k числа
ak–1 и
bk имеют разный знак (тогда |
ak–1 +
bk| < |
ak–1| + |
bk|). В частности, это произойдёт при передаче орехов от человека с положительным числом орехов (будем обозначать его знаком "+"; ясно, что число орехов, которые он
отдаёт соседу, также положительно) человеку с отрицательным ("–"; число орехов, которые он
оставляет себе, также отрицательно). Если в какой-то момент за столом нет ни одной такой пары (но есть еще люди с ненулевым числом орехов), то найдётся группа вида "+ 0 ... 0 –" (по правую руку от "+" сидят несколько человек с нулевым числом орехов, а затем "–"). Заметим, что число нулей между "+" и "–" при каждом ходе уменьшается (левый 0 превращается в "+", а остальные 0 и "–" не меняются). Поэтому через несколько ходов "+" и "–" окажутся рядом и сумма
S уменьшится.
Таким образом, сумма
S не может “остановиться” ни на каком положительном значении. А так как эта сумма – целое неотрицательное число, то когда-нибудь она станет равной нулю, то есть у всех станет по 0 орехов.
Страница:
<< 23 24 25 26 27 28 29 >> [Всего задач: 326]
Фильтр
