ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 19 20 21 22 23 24 25 >> [Всего задач: 146]      



Задача 79256

Темы:   [ Теория игр (прочее) ]
[ Подобные фигуры ]
Сложность: 5
Классы: 9,10,11

Автор: Белкин А.

В центре квадрата находится полицейский, а в одной из его вершин – гангстер. Полицейский может бегать по всему квадрату, а гангстер – только по его сторонам. Известно, что отношение максимальной скорости полицейского и максимальной скорости гангстера равно:
а) 0,5;   б) 0,49;   в) 0,34;   г) 1/3.   Сможет ли полицейский может бежать так, что в какой-то момент окажется на одной стороне с гангстером?

Решение

  Пусть u и v – максимальные скорости полицейского и гангстера. Введём систему координат с началом в центре исходного квадрата ABCD и осями, параллельными его сторонам. Положим сторону квадрата ABCD равной 6 м и будем считать, что максимальная скорость гангстера
v = 3 (м/мин)  (нам ведь важно лишь отношение  u : v).  Точки, в которых находятся полицейский и гангстер, обозначим через
П(хП, yП)  и  Г(xГ, yГ),  соответственно. Обозначим через Г' точку с координатами  (1/3 xГ, 1/3 yГ);  если точка Г движется по контуру квадрата ABCD со скоростью 3, то Г' движется по контуру квадрата со стороной 2 со скоростью 1.

  а-в) Докажем, что полицейский достигнет своей цели (то есть окажется с гангстером на одной стороне квадрата; будем говорить, что в этом случае он ловит гангстера). Полицейский будет ловить гангстера в несколько этапов.

  Первый этап. Полицейский догоняет Г'. Это всегда можно сделать, так как  u > 1.  Первый этап заканчивается, когда точки П и Г' совпадают.
  Второй этап. Можно считать без ограничения общности, что к концу первого этапа точка Г окажется на стороне ; тогда  3xП = xГ.  На протяжении всего второго этапа полицейский должен двигаться таким образом, чтобы всё время выполнялось равенство  3xП = xГ;  для этого необходимо и достаточно, чтобы то же соотношение все время имело место для горизонтальных составляющих скоростей полицейского и гангстера. При этом по вертикали полицейский может двигаться к стороне AB со скоростью     Возможны два случая.
  1) Г остаётся все время на AB. Тогда П через некоторое время достигнет AB, и следовательно, гангстер будет пойман.

  2) В какой-то момент Г уйдёт со стороны AB. Как только Г достигнет границы AB (будем считать, точки B) начинается   Третий этап. К началу этого этапа точки Г и B совпадают, а точка П находится от каждой из сторон AB и BC на расстоянии, не большем 2. На третьем этапе полицейский должен с максимальной скоростью приближаться по перпендикуляру к той стороне, на которой находится гангстер (если  Г = B,  то безразлично, к какой именно, – к стороне AB или же к стороне BC). Чтобы добежать из точки B до точки A или до точки С, гангстеру понадобится 2 минуты, а полицейскому, чтобы достигнуть соответствующей стороны (AB или ), понадобится меньше 2 минут. Следовательно, полицейский поймает гангстера на одной из сторон AB или BC.

  г) Покажем, что при  u = 1 м/мин   гангстер может выбрать такую стратегию, при которой полицейский не сумеет его догнать. Проведём прямые A'B', C'D', параллельные стороне AB, и прямые A"D", B"C", параллельные BC, так, чтобы
AA' = BB' = CC' = DD' = AA" = BB" = CC" = DD" = 1  (рис. слева). Пусть в самом начале гангстер Г находится в середине стороны AB, а полицейский П – над прямой A'B'. Проведем между П и A'B' вспомогательную прямую A1B1, параллельную AB (рис. справа).

  Опишем теперь стратегию гангстера. Пока полицейский находится выше прямой A1B1, гангстер остается на месте – в середине AB. Рано или поздно полицейский достигнет A1B1 (иначе он никогда не поймает гангстера).
  Пусть при этом  xП ≤ 0  (случай  xП ≥ 0  симметричен). Тогда Г перебегает в середину отрезка BC. На это ему требуется 2 минуты. За первую минуту (пока ганстер находится на AB) полицейский не успеет добежать до прямой AB и, значит, не сможет поймать Г на стороне AB. Кроме того, за 2 минуты он не успеет добежать до прямой B"C".
  Итак, мы пришли к конфигурации, эквивалентной начальной: Г – в середине стороны BC, а П – левее прямой B"C". При этом прошло более 2 минут.
  Дальнейшее поведение Г аналогично описанному выше. Очевидно, что при такой стратегии гангстера полицейский не поймает его ни за какое конечное время.

Прислать комментарий

Задача 79385

Темы:   [ Теория игр (прочее) ]
[ Наибольшая или наименьшая длина ]
[ Рекуррентные соотношения (прочее) ]
[ Процессы и операции ]
Сложность: 5
Классы: 9,10,11

Три прямолинейных коридора одинаковой длины l образуют фигуру, изображённую на рисунке. По ним бегают гангстер и полицейский. Максимальная скорость полицейского в 2 раза больше максимальной скорости гангстера. Полицейский сможет увидеть гангстера, если он окажется от него на расстоянии, не большем r. Доказать, что полицейский всегда может поймать гангстера, если:   а)  r > l/3;   б)   r > l/4;   в)   r > l/5;   г)   r > l/7.

Решение

  Договоримся, что полицейский всегда движется с максимальной скоростью. Сначала он "прочёсывает" коридор OC. Убедившись, что гангстера там нет, полицейский удаляется в коридор OA на расстояние 2r и затем возвращается в точку O. Пусть отсюда он не увидел гангстер. Заметим, что тогда он не может находиться в коридоре OC: если бы он за время отсутствия полицейского в точке O попытался перебежать из коридора OB в коридор OC, то к моменту возвращения полицейского в точку O расстояние от гангстера до O было бы не больше, чем r.

  а) Если  l ≤ 3r,  то гангстер не может находиться и в коридоре OA, и полицейский ловит его, "прочесав" коридор OB.

  б) Пусть  3r < l ≤ 4r.  Тогда гангстер может находиться в коридоре OA, но на расстоянии от O , большем 2r.
  Теперь полицейский отправляется в коридор OB на расстояние 3r. Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OB гангстера нет. Но и в коридоре OC гангстера нет (если гангстер находился в коридоре OA, то на расстоянии от O, большем 2r, и потому до возвращения полицейского в точку O, гангстер не сможет перебежать в коридор OC так, чтобы при этом оказаться от O на расстоянии, большем r). Осталось "прочесать" коридор OA.

  в) Пусть  4r < l < 5r.  Тогда гангстер может находиться в коридоре OB, но на расстоянии от O, большем  (3r + r) – 3r/2 = 5r/2.
  Дальнейшие действия полицейского заключаются в том, чтобы углубляться то в коридор OB, то в коридор OA на все большие расстояния, но так, чтобы гангстер не смог перебежать в коридор OC. Каждое такое "углубление" вместе с последующим возвратом в точку O будем называть циклом. Два первых цикла уже описаны.
  Пусть после n-го цикла полицейский знает, что в коридоре OC гангстера нет, а в коридоре OX (где  X = A  при нечётном n и  X = B  при чётном n) гангстер может находиться только на расстоянии от O, большем yn. Тогда в следующем цикле полицейский отправляется в другой коридор на расстояние  yn + r.  Вернувшись в точку O, полицейский знает, что в коридоре OC гангстера нет, а в только что исследованном коридоре гангстер может находиться только на расстоянии от O, большем  yn+1 = (½ (yn + r) + r) = ½ (yn + 3r).  Если же  yn + r ≥ l – r,  то в исследованном коридоре гангстера вообще нет.
  Так как  3r – yn+1 = ½ (3r – yn),  то  3r – yn = 21–n(3r – y1) = 21–nr,  то есть  yn = 3r – 21–nr.  Гангстер ловится, если  yn + r ≤ l – r  при каком-нибудь n, то есть если  21–nr ≤ 5r – l.  Поскольку  l < 5r,  то после достаточно большого числа циклов гангстер ловится.

  г) Пусть  5r ≤ l < 7r.  Положим  ε = ½ (7r – l).  Полицейский действует так, как описано в п. в), пока при каком-то не окажется, что  yn ≥ 3r – ε  (из формулы для yn следует, что когда-то это произойдёт). После этого полицейский углубляется в очередной коридор (скажем, OA) на расстояние  l – r.
  Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OA гангстера нет, а в коридоре OC гангстер не может находиться от O на расстоянии, большем   (l – r) – (3r – ε) = 3r – ε.  Затем полицейский углубляется в коридор OC на расстояние  4r – 2ε.  Вернувшись в точку O и не увидев гангстера, полицейский знает, что в коридоре OC гангстера нет (в противном случае гангстер был бы пойман, оказавшись в коридоре OC от полицейского на расстоянии, меньшем  (3r – ε) + ½ (4r – 2ε) – (4r – 2ε) = r),  а в коридоре OA гангстер не может находиться на расстоянии от O, большем  (4r – 2ε) – r = 3r – 2ε.  Затем полицейский идёт в коридор OA на расстояние  4r – 4ε,  затем в коридор OC на расстояние  4r – 8ε,  снова в коридор OA на расстояние  4r – 16ε  и т. д. Когда окажется, что надо идти на отрицательное расстояние, полицейский понимает, что гангстер находится в коридоре OB.

Прислать комментарий

Задача 79645

Темы:   [ Теория игр (прочее) ]
[ Наибольшая или наименьшая длина ]
[ Рекуррентные соотношения (прочее) ]
[ Процессы и операции ]
Сложность: 5
Классы: 7,8

См. задачу 79385 в) и г).

Прислать комментарий

Задача 107808

Темы:   [ Теория игр (прочее) ]
[ Полуинварианты ]
[ Процессы и операции ]
Сложность: 5
Классы: 9,10,11

Али-Баба и разбойник делят клад, состоящий из 100 золотых монет, разложенных в 10 кучек по 10 монет. Али-Баба выбирает 4 кучки, ставит около каждой из них по кружке, откладывает в каждую кружку по несколько монет (не менее одной, но не всю кучку). Разбойник должен как-то переставить кружки, изменив их первоначальное расположение, после чего монеты высыпаются из кружек в те кучки, около которых оказались кружки. Далее Али-Баба снова выбирает 4 кучки из 10, ставит около них кружки, и т. д. В любой момент Али-Баба может уйти, унеся с собой любые три кучки по выбору. Остальные монеты достаются разбойнику. Какое наибольшее число монет сможет унести Али-Баба, если разбойник тоже старается получить побольше монет?

Решение

  Покажем, что Али-Баба может добиться, чтобы в 7 кучках лежало не более, чем по 4 монеты, а разбойник может добиться, чтобы не было кучек, содержащих менее 4 монет. Следовательно, Али-Баба унесет 100 - 7 . 4 = 72 монеты.

Докажем сначала, что разбойник может действовать так, чтобы не было кучек, содержащих менее 4 монет. Действительно, для первоначальной ситуации это верно. Пусть на некотором шаге это верно и часть монет уже отложена в кружки. Тогда, если в двух кружках содержится одинаковое число монет, то разбойник переставляет эти кружки и положение не изменяется, если же количество монет во всех кружках разное, то в двух наибольших из них соответственно не менее 3 и 4 монет, и разбойник переставляет эти кружки. В результате во всех новых кучках опять будет не менее 4 монет.

Покажем теперь, что Али-Баба может добиться, чтобы в 7 кучках лежало не более, чем по 4 монеты.

Пусть имеются 4 кучки, в каждой из которых лежит более, чем 4 монеты, и x1(0)$ \ge$x2(0)$ \ge$x3(0)$ \ge$x4(0)$ \ge$5 — количества монет в этих кучках. Покажем, что Али-Баба может добиться, чтобы в одной из этих кучек стало меньше 4 монет, причем количество монет в каждой из оставшихся шести кучек не изменилось. Разложим эти кучки следующим образом:

x1(0) = y1 + 1,    x2(0) = y2 + 2,    x3(0) = y3 + 3,    x4(0) = y4 + 4,

положив в кружки соответственно 1, 2, 3 и 4 монеты. После перестановки кружек получим новые кучки, состоящие из

x1(1) = y1 + z1,    x2(1) = y2 + z2,    x3(1) = y3 + z3,    x4(1) = y4 + z4

монет, где z1, z2, z3 и z4 — некоторая перестановка чисел 1, 2, 3, 4. Далее процесс повторяется с заменой чисел x1(0), ..., x4(0) на расположенные в невозрастающем порядке числа x1(1), ..., x4(1).

Докажем, что на некотором шаге процесс оборвется, т. е. в одной из этих кучек станет меньше 5 монет. Имеет место одна из следующих трех возможностей:

1) x1(1) > x1(0) (если первую кружку переставили);

2) x1(1) = x1(0), x2(1) > x2(0) (если первую кружку оставили на месте, а вторую переставили);

3) x1(1) = x1(0), x2(1) = x2(0), x3(1) > x3(0) (если первые две кружки остались на месте).

На каждом шаге количество монет в первой кучке не уменьшается. Поэтому число шагов, при которых реализуется первая возможность, конечно. Суммарное число монет в первой и второй кучках тоже не уменьшается, поэтому число шагов, при которых реализуется вторая возможность, также конечно. Аналогично проверяется, что число шагов, реализующих третью возможность, тоже конечно. Следовательно, на некотором шаге процесс оборвется, что соответствует тому, что в некоторой кучке окажется не более 4 монет. При этом количество кучек с не более, чем 4 монетами увеличится. Повторяя этот процесс, в конце концов придем к тому, что останется не более трех кучек, содержащих больше 4 монет.
Прислать комментарий


Задача 86123

Темы:   [ Теория игр (прочее) ]
[ Принцип Дирихле (конечное число точек, прямых и т. д.) ]
[ Индукция в геометрии ]
[ Построения (прочее) ]
Сложность: 5+
Классы: 9,10,11

На прямоугольном листе бумаги нарисован круг, внутри которого Миша мысленно выбирает n точек, а Коля пытается их разгадать. За одну попытку Коля указывает на листе (внутри или вне круга) одну точку, а Миша сообщает Коле расстояние от нее до ближайшей неразгаданной точки. Если оно оказывается нулевым, то после этого указанная точка считается разгаданной. Коля умеет отмечать на листе точки, откладывать расстояния и производить построения циркулем и линейкой. Может ли Коля наверняка разгадать все выбранные точки менее, чем за (n+1)2 попыток?

Решение

Пусть на листе бумаги осталось k ≥ 1 неразгаданных точек ck,1, ck,2, …, ck,k. Покажем, как с помощью 2k + 1 попытки разгадать одну из них.
Начертим на листе бумаги отрезок прямой l, не пересекающей отмеченный круг. На этом отрезке так укажем (k + 1) точку
ak,1, ak,2, …, ak,k + 1, что ak,j лежит строго между ak,j − 1 и ak,j + 1 для всех j = 2,3, … , k. Пусть Миша назвал для этих точек расстояния dk,1, dk,2, … , dk,k + 1 соответственно.
Найдём с помощью циркуля и линейки и укажем такие точки bk,j (j = 1,2,…,k), что они лежат по ту же сторону от прямой l, что и отмеченный круг, и отстоят от точек ak,j и ak,j + 1 на расстояния dk,j и dk,j + 1 соответственно (те индексы j, для которых такую точку bk,j указать невозможно, мы пропускаем).
Докажем, что среди указанных точек bk,j найдётся по крайней мере одна из точек ck,i (i = 1,2,…,k). Действительно, по принципу Дирихле найдутся по крайней мере две точки ak,j и ak,m (1 ≤ j < mk + 1), для которых ближайшей из неразгаданных точек будет одна и та же точка ck,i для некоторого i (1 ≤ ik). Тогда, как нетрудно показать, для любой точки из отрезка [ak,j, ak,m], и в частности для точки ak,j + 1, точка ck,i также будет являться ближайшей из всех неразгаданных точек. Следовательно, ck,i будет отстоять от точек ak,j и ak,j + 1 на расстояния dk,j и dk,j + 1 соответственно, и лежать по ту же сторону от прямой l, что и отмеченный круг. Таким образом, точка ck,i совпадает с одной из указанных нами точек bk,j (j = 1,2,…,k). Итак, не более чем за 2k + 1 попытки можно заведомо разгадать одну из неразгаданных точек.
Докажем индукцией по n, что действуя указанным выше образом для k = n, n − 1, …, 1, Коля разгадает все загаданные Мишей точки менее чем за (n + 1)2 попытку. Пусть n = 1, тогда указанный выше способ позволяет угадать единственную неразгаданную точку за
3 < (n + 1)2 попытки. Предположим, что N неразгаданных точек можно заведомо разгадать менее чем за (N + 1)2 попытку. Пусть
n = N + 1. Разгадаем одну из загаданных Мишей точек указанным выше способом не более чем за 2N + 3 попытки. Тогда по предположению индукции, все точки могут быть разгаданы менее чем за (N + 1)2 + 2N + 3 = (N + 2)2 попыток. Утверждение доказано.
Прислать комментарий


Страница: << 19 20 21 22 23 24 25 >> [Всего задач: 146]      



© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .