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

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

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



Задача 64857

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

  В некотором государстве ценятся золотой и платиновый песок. Золото можно менять на платину, а платину на золото по курсу, который определяется натуральными числами g и p так: x граммов золотого песка равноценны y граммам платинового, если  xp = yg  (числа x и y могут быть нецелыми). Сейчас у банкира есть по килограмму золотого и платинового песка, а  g = p = 1001.  Государство обещает каждый день уменьшать одно из чисел g и p на единицу, так что через 2000 дней они оба станут единицами; но последовательность уменьшений неизвестна. Может ли банкир каждый день менять песок так, чтобы в конце гарантированно получить хотя бы по 2 кг каждого песка?

Решение

  Докажем, что если вначале у банкира по 1 кг песка, и  g = p = k,  то в конце хотя бы одного песка будет не больше  2 – 1/k кг.  Для этого достаточно доказать, что если вначале у банкира по     кг песка, то в конце он не может получить каждого песка больше чем по килограмму.
  Назовём состоянием банкира число  S = Gp + Pg,  если у него G кг золота и P кг платины. Заметим, что в результате обмена песка по курсу состояние не меняется. Покажем индукцией по числу дней, что наибольшее гарантированное состояние банкира в день, когда курсы равны g и p, не превосходит     В начальный день это так.
  Пусть в некоторый день это так. Ясно, что при этом либо     либо     (Оба неравенство выполнены одновременно только в случае, когда оба превращаются в равенства.)
  Пусть выполнено первое неравенство, то есть     Тогда государство уменьшит p на 1 (случай  g > p = 1  будет разобран ниже). При этом из состояния вычтется G, то есть оно станет равно

 
что и требовалось.
  Случай, когда выполнено второе неравенство, в частности, случай  g > p = 1,  разбирается "симметрично".
  В итоге, в последний день  (g = p = 1)  состояние будет не больше 2, а значит, количество какого-то песка будет не больше килограмма.

Ответ

Не может.

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

Задача 79256

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

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

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

Решение

  Пусть u и v – максимальные скорости полицейского и гангстера. Введём систему координат с началом в центре исходного квадрата ABCD и осями, параллельными его сторонам. Положим сторону квадрата ABCD равной 6 м и будем считать, что максимальная скорость гангстера  v = 3 (м/мин)  (нам ведь важно лишь отношение  u : v).  Точки, в которых находятся полицейский и гангстер, обозначим через  П(хП, yП)  и  Г(xГ, yГ),  соответственно. Обозначим через Г' точку с координатами  (⅓ xГ, ⅓ 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 монет.
Прислать комментарий


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



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

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