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

   Решение

В микросхеме 2000 контактов, первоначально любые два контакта соединены отдельным проводом. Хулиганы Вася и Петя по очереди перерезают провода, причем Вася (он начинает) за ход режет один провод, а Петя – либо один, либо три провода. Хулиган, отрезающий последний провод от какого-либо контакта, проигрывает. Кто из них выигрывает при правильной игре?

   Решение

Темы:    [ Теория игр (прочее) ] [ Разбиения на пары и группы; биекции ]

Сложность: 5- Классы: 7,8,9

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

Условие

В микросхеме 2000 контактов, первоначально любые два контакта соединены отдельным проводом. Хулиганы Вася и Петя по очереди перерезают провода, причем Вася (он начинает) за ход режет один провод, а Петя – либо один, либо три провода. Хулиган, отрезающий последний провод от какого-либо контакта, проигрывает. Кто из них выигрывает при правильной игре?

Решение

Мысленно разобьем контакты на четыре одинаковых группы: A , B , C и D . В каждой группе пронумеруем контакты числами от 1 до 500.
Петя будет отвечать на любой ход Васи так, чтобы для каждого номера k от контактов A_k , B_k , C_k и D_k отходило поровну проводов. До начала игры это условие, очевидно, выполняется.
Именно благодаря этому условию проигрышная ситуация впервые случится после Васиного хода.

Опишем подробно Петину стратегию. Если Вася перерезает провод между контактами одной группы, например, провод A_iA_j , то Петя перережет провода B_jB_j , C_iC_j и D_jD_j .
Если Вася перерезает провод между проводами из разных групп и с разными номерами, например, провод A_iB_j , то Петя в ответ перережет провода A_jB_i , C_iD_j и C_jD_i . Если же Вася перерезал провод между контактами из разных групп с одинаковыми номерами, например, провод A_kB_k , то Петя перережет провод C_kD_k . Заметим, что из описанной стратегии Пети следует, что провода, которые он собирается резать, не будут отрезаны до его хода. Поэтому Петя всегда сможет разрезать требуемые провода.

Отметим, что каждый раз после хода Пети от контактов A_k , B_k , C_k и D_k отходит поровну проводов; при этом от одного из них столько же проводов отходило уже после Васиного хода. Поэтому ситуация, когда от одного контакта отрезан последний провод, случится впервые после Васиного хода. Так как количество проводов конечно, проиграет Вася.

См. также данную задачу.

Ответ

Выигрывает Петя.

Источники и прецеденты использования