две задачки
Sep. 18th, 2013 02:14 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЕще две задачки из книги Винклера. По-моему, очень красивые и несколько сложнее, чем в прошлый раз. Комменты скрывать не буду Буду скрывать правильные решения несколько часов, но не гарантирую.
1. Учитель сидит в классе, на его столе стоят весы с двумя чашами. На чашах находится какое-то количество грузов. На каждом грузе написано как минимум одно имя ученика (возможно, больше одного имени). На данный момент правая чаша весов перевешивает.
Снаружи у входа стоят ученики. Когда ученик заходит в класс, он берет все грузы на обеих чашах, на которых написано его имя, и переставляет каждый такой груз на противоположную чашу. Те, что были слева, переходят направо, те, что справа - налево. Следующий ученик делает то же самое с грузами со своим именем, и так далее.
Доказать: учитель может впустить в класс определенный набор учеников таким образом, что когда они все войдут, левая чаша будет перевешивать.
2. Алиса и Боб по очереди выбирают цифры от 1 до 9, без повторов (каждая цифра берется не больше одного раза). Выигрывает тот, кто первым соберет у себя три цифры, в сумме дающие 15. Алиса начинает. Есть ли у нее выигрышная стратегия?
Update: открываю все комментарии, в них есть правильные ответы, учтите.
1. Учитель сидит в классе, на его столе стоят весы с двумя чашами. На чашах находится какое-то количество грузов. На каждом грузе написано как минимум одно имя ученика (возможно, больше одного имени). На данный момент правая чаша весов перевешивает.
Снаружи у входа стоят ученики. Когда ученик заходит в класс, он берет все грузы на обеих чашах, на которых написано его имя, и переставляет каждый такой груз на противоположную чашу. Те, что были слева, переходят направо, те, что справа - налево. Следующий ученик делает то же самое с грузами со своим именем, и так далее.
Доказать: учитель может впустить в класс определенный набор учеников таким образом, что когда они все войдут, левая чаша будет перевешивать.
2. Алиса и Боб по очереди выбирают цифры от 1 до 9, без повторов (каждая цифра берется не больше одного раза). Выигрывает тот, кто первым соберет у себя три цифры, в сумме дающие 15. Алиса начинает. Есть ли у нее выигрышная стратегия?
Update: открываю все комментарии, в них есть правильные ответы, учтите.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-09-18 11:22 am (UTC)no subject
Date: 2013-09-18 11:25 am (UTC)Удалил комментарий, чтобы не спойлить.
no subject
Date: 2013-09-18 11:30 am (UTC)no subject
Date: 2013-09-18 11:35 am (UTC)Если перебор автоматически проигрывает, то
А 6
Б 9 иначе первый берёт 9 и выигрывает
А 2 цугцванг ?
no subject
Date: 2013-09-18 11:37 am (UTC)no subject
Date: 2013-09-18 11:42 am (UTC)боб: 6,7,5
или
алиса: 9,8,2,5
боб: 6,7,4
если боб будет ходить иначе на более ранних ходах, проиграет(при данной стратегии он пытается не дать выиграть алисе)
no subject
Date: 2013-09-18 11:42 am (UTC)no subject
Date: 2013-09-18 11:46 am (UTC)no subject
Date: 2013-09-18 11:49 am (UTC)no subject
Date: 2013-09-18 11:49 am (UTC)Условие:
In a mathematical competition some competitors are friends. Friendship
is always mutual. Call a group of competitors a clique if each two of them are friends. (In
particular, any group of fewer than two competitors is a clique.) The number of members
of a clique is called its size.
Given that, in this competition, the largest size of a clique is even, prove that the
competitors can be arranged in two rooms such that the largest size of a clique contained
in one room is the same as the largest size of a clique contained in the other room.
Решения онлайн нигде не нашел (было какое-то на арт ов проблем солвинг, но его сняли из-за ошибки). Но у меня есть свое. Так что если кто-то решит или захочет проверить мое решение, было бы клево.
no subject
Date: 2013-09-18 11:55 am (UTC)no subject
Date: 2013-09-18 11:56 am (UTC)no subject
Date: 2013-09-18 11:59 am (UTC)no subject
Date: 2013-09-18 12:01 pm (UTC)- А: 6
- Б: 1
- А:9
Но А не имеет трёх цифр, а имеет только две.Я так понял, что набор "3,4,5,6" - это четыре цифры; три последние дают в сумме искомые 15, так что этот набор выигрышный (если его можно собрать).
Т.е. я полагаю, что перебор не приводит к проигрышу.
no subject
Date: 2013-09-18 12:03 pm (UTC)no subject
Date: 2013-09-18 12:03 pm (UTC)Рассмотрим произвольный груз W. Пусть P — один из тех, чьё имя написано на этом грузе (таковой есть по условию). Тогда все подмножества в множестве учеников можно разбить на пары, отличающиеся только тем, входит ли в них ученик P. Если X и Y — два множества из одной пары, то vX,W+vY,W=0, что означает, что сумма vX,W по всем возможным X равна нулю. Отсюда сумма vX,W по всем возможным X и W также равна нулю.
Пусть sX — сумма vX,W по всем возможным W. Это — разность между весом грузов на правой чашке и весом грузов на левой чашке после того, как ученики из множества X войдут в класс. Тогда сумма sX по всем возможным X равна нулю в силу вышеизложенного. С другой стороны, по условию sø — положительная величина. Значит, хотя бы одно из остальных слагаемых должно быть отрицательным.
Если теперь X — такое, что sX отрицательно, то, после того, как ученики из множества X войдут в класс, левая чашка перевесит.
Вторую задачу знаю, это, собственно, другая игра.
no subject
Date: 2013-09-18 12:06 pm (UTC)no subject
Date: 2013-09-18 12:06 pm (UTC)ps: Обычно при публикации задач ставится опция "скрывать комментарии".
no subject
Date: 2013-09-18 12:10 pm (UTC)no subject
Date: 2013-09-18 12:11 pm (UTC)no subject
Date: 2013-09-18 12:11 pm (UTC)no subject
Date: 2013-09-18 12:12 pm (UTC)no subject
Date: 2013-09-18 12:12 pm (UTC)no subject
Date: 2013-09-18 12:18 pm (UTC)no subject
Date: 2013-09-18 12:18 pm (UTC)