две задачки

[avva]

Еще две задачки из книги Винклера. По-моему, очень красивые и несколько сложнее, чем в прошлый раз. Комменты скрывать не буду Буду скрывать правильные решения несколько часов, но не гарантирую.

1. Учитель сидит в классе, на его столе стоят весы с двумя чашами. На чашах находится какое-то количество грузов. На каждом грузе написано как минимум одно имя ученика (возможно, больше одного имени). На данный момент правая чаша весов перевешивает.

Снаружи у входа стоят ученики. Когда ученик заходит в класс, он берет все грузы на обеих чашах, на которых написано его имя, и переставляет каждый такой груз на противоположную чашу. Те, что были слева, переходят направо, те, что справа - налево. Следующий ученик делает то же самое с грузами со своим именем, и так далее.

Доказать: учитель может впустить в класс определенный набор учеников таким образом, что когда они все войдут, левая чаша будет перевешивать.


2. Алиса и Боб по очереди выбирают цифры от 1 до 9, без повторов (каждая цифра берется не больше одного раза). Выигрывает тот, кто первым соберет у себя три цифры, в сумме дающие 15. Алиса начинает. Есть ли у нее выигрышная стратегия?

Update: открываю все комментарии, в них есть правильные ответы, учтите.

Comments

[avva.livejournal.com]

Ну, вы наверное знали эту задачу?

[oldkettle.livejournal.com]

Задача 2

Если перебор автоматически проигрывает, то
А 6
Б 9 иначе первый берёт 9 и выигрывает
А 2 цугцванг ?

[avva.livejournal.com]

Чтобы выиграть, нужно иметь именно три цифры с суммой 15 - 6 и 9 не работают.

[tembel.livejournal.com]

алиса: 9,8,2,4
боб: 6,7,5

или

алиса: 9,8,2,5
боб: 6,7,4

если боб будет ходить иначе на более ранних ходах, проиграет(при данной стратегии он пытается не дать выиграть алисе)

[tembel.livejournal.com]

блин, точно, я забыла про три цифры!

[avva.livejournal.com]

Гм, я не очень понял, но фишка явно не в этом. То, в каком состоянии находятся чаши в процессе перекладывания, вообще неважно. Ученик заходит. Берет каждый груз на котором есть его имя (неважно, в каком порядке) и перекладывает его на противоположную чашу. После того, как он закончил, мы смотрим, перевешивает теперь левая чаша или нет. Нового ученика не запускаем, пока этот не закончил.

[tidbit-stories.livejournal.com]

Интересная задачка с ИМО. Решило полностью по-моему 2 человека. И еще 2 не полностью. Она в духе первой задачи.
Условие:
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.

Решения онлайн нигде не нашел (было какое-то на арт ов проблем солвинг, но его сняли из-за ошибки). Но у меня есть свое. Так что если кто-то решит или захочет проверить мое решение, было бы клево.

[avva.livejournal.com]

Спасибо, выглядит интересно, буду думать.

(если дружба транзитивна, тогда совсем просто, но конечно это не так)

[prosto-tak.livejournal.com]

2: нет. Крестики-нолики на магическом квадрате

[avva.livejournal.com]

верно! Я скрою твое решение на какое-то время.

[migmit.livejournal.com]

Для каждого подмножества X в множестве учеников и каждого груза W обозначим через v_X,W вес груза W со знаком "плюс", если после того, как ученики из множества X (и только они) войдут в класс (неважно, в каком порядке) груз W окажется на правой чашке, и "минус" в противном случае.

Рассмотрим произвольный груз W. Пусть P — один из тех, чьё имя написано на этом грузе (таковой есть по условию). Тогда все подмножества в множестве учеников можно разбить на пары, отличающиеся только тем, входит ли в них ученик P. Если X и Y — два множества из одной пары, то v_X,W+v_Y,W=0, что означает, что сумма v_X,W по всем возможным X равна нулю. Отсюда сумма v_X,W по всем возможным X и W также равна нулю.

Пусть s_X — сумма v_X,W по всем возможным W. Это — разность между весом грузов на правой чашке и весом грузов на левой чашке после того, как ученики из множества X войдут в класс. Тогда сумма s_X по всем возможным X равна нулю в силу вышеизложенного. С другой стороны, по условию s_ø — положительная величина. Значит, хотя бы одно из остальных слагаемых должно быть отрицательным.

Если теперь X — такое, что s_X отрицательно, то, после того, как ученики из множества X войдут в класс, левая чашка перевесит.

Вторую задачу знаю, это, собственно, другая игра.

[avva.livejournal.com]

Да, все верно.

[ny-quant.livejournal.com]

Не понимаю, что сложного во второй задаче. Вторым ходом Боб всегда может помешать Алисе выиграть, выбрав нужную ей на последнем ходу цифру. Думал около минуты.

[migmit.livejournal.com]

Пардон, неверно прочитал ваш коммент.

[karpion.livejournal.com]

1. Я так понимаю - надо впускать учеников, от входа которых равновесие смещается влево. Мне кажется, что пока равновесие смещено вправо - такие ученики всегда будут.

ps: Обычно при публикации задач ставится опция "скрывать комментарии".

[avva.livejournal.com]

Это неверно - есть ситуации, когда вход любого ученика "ухудшает" баланс.

[sthinks.livejournal.com]

2. от 1 до 9 с суммой 15 - это стандартный магический квадрат. Похоже, нет там выигрышной стратегии для Алисы.

[avva.livejournal.com]

верно :)

[janatem.livejournal.com]

2-я мне кажется знакомой: там фишка в том, что эта игра эквивалентна крестикам-ноликам. Так?

[avva.livejournal.com]

ага.

Алиса и боб

[46bip.livejournal.com]

Алиса: 7, 6, 5, 4/3
Боб (чтобы не дать выиграть): 8, 2, 3/4

Re: Алиса и боб

[migmit.livejournal.com]

ТРИ цифры. Две не годятся.

[sthinks.livejournal.com]

1. (если я правильно поняла спросонья) Раз то, что было слева переходит направо, и наоборот, значит для каждой комбинации непременно есть симметричная. Поскольку начальное положение с перевесом вправо, то найдется вариант, когда перевес будет влево.

[avva.livejournal.com]

Нет, необязательно, из-за того, что на некоторых грузах может быть написано несколько имен, симметрия теряется, когда ученики заходят один за другим.

[ger04ka.livejournal.com]

У Алисы нет выигрышной стратегии. Всего есть 8 комбинаций из трех цифр с суммой 15 (порядок не важен). Причем только 5 входит более чем в 3 из них - в 4 комбинации.
Если Алиса не выбрала 5 первым ходом, то все ее выигрышные комбинации "разрушаются" за 3 хода Бобом.
Если Алиса выбрала 5, то все комбинации разрушаются 4-мя ходами Боба

[mathclimber.livejournal.com]

Насколько я понимаю, вторая игра изоморфна крестикам-ноликам на доске 3х3. Значит - ничья!

[avva.livejournal.com]

Верно, да :)

[cousin-it.livejournal.com]

The second problem looks like tic-tac-toe on the magic square (2 7 6, 9 5 1, 4 3 8), so neither player has a winning strategy.

[beldmit.livejournal.com]

2. Игра изоморфна крестикам-ноликам на магическом квадрате. Нету.

[max-i-m.livejournal.com]

1) Буем считать что гири слева отрицательного веса а гири справа положительного. Для каждого набора учеников получится некоторый суммарный вес. Суммируя по всем наборам получим 0, поскольку для каждой гири количество наборов для которых она справа и слева одинаково. По условию для пустого набора суммарный вес положителен. Значит существует набор для которого суммарный вес отрицателен. QED.

Симпатично.

2) Я примерно месяц назад играл в эту игру в Манхэттенском музее математики! Кстати, очень симпатичный музей. http://momath.org/

[glukanat.livejournal.com]

Вторая задача - классика. Крестики-нолики forever...

[tyrannoeil.livejournal.com]

1. Пусть n учеников. Давайте рассмотрим многочлен P от переменных x_1, x_2,.., x_n следующего вида: в нём будет не более 2^n ненулевых членов, и эти члены будут стоять при мономах, в которых каждая переменная встречается не более одного раза.

Рассмотрим те гирьки, на которых написаны имена первых трёх учеников и только эти номера. Пусть на правой чаше их суммарный вес равен A, а на левой -- B. Коэффициент многочлена P при x_1x_2x_3 положим равным A-B.
Тогда по условию P(0,..,0) = 0 и P(1,..,1) > 0.
Кроме этого, если зафиксировать все переменные, кроме одной, то по этой одной переменной многочлен будет линейной функцией.

Если мы докажем, что существует набор переменных, состоящий из 1 и -1, на котором многочлен меньше нуля, то задача решена: достаточно пустить в класс тех, кому соответствует -1. Далее ищем такой набор значений переменных.
Пусть, например в P моном минимальной ненулевой степени это ax_1x_2...x_k, где a -- коэффициент. Положим x_1=x_2=...=x_{k-1}=1, x_k = -sign(a), а остальные -- нули. Тогда значение P на этом наборе отрицательно.

Пусть значение P на некотором наборе, состоящем из 1, -1 и 0, отрицательно. Покажем, что ещё один ноль в наборе переменных можно заменить числом 1 или -1 так, чтобы на этом наборе P давал отрицательное значение. А это очевидно, т.к. по каждой переменной P линеен.

Действуя так, получим требуемый набор.

[avva.livejournal.com]

Интересное доказательство, спасибо! А где в нем вы пользуетесь тем, что P(1,...,1) > 0?

[tidbit-stories.livejournal.com]

Мне кажется что существует комбинация грузов и имен на них, такая что переместить равновесие влево невозможно. Допустим на левой чаше груз весом 2 и с именем А. На правой -- весом 2 и 4 с именами Б и А. Не сушествует такой комбинации, которая сделает перевес на левую чашу.

[avva.livejournal.com]

Почему же - если войдут А и Б, то положение будет: слева 4Б и 4А, справа 2А.

Это если вы имели в виду, что справа 2Б и 4А. Если справа 2АБ и 4АБ, то вход А меняет все грузы местами и тоже достигает нужного.

[lithovore.livejournal.com]

1. Рассмотрим конечные расположения грузов, соответствующие всем возможным подмножествам учеников. Каждый груз будет в половине случаев лежать на левой чаше, а в половине - на правой. (Выберем любого ученика, фамилия которого написана на грузе, и разобьём подможества на пары, отличаюшиеся на этого ученика; в каждой паре положения груза будут разными.) Тогда средние суммарные массы грузов на чашах равны. Поскольку есть расположение, в котором перевешивает правая чаша (соответствующее пустому множеству), то найдётся и такое, в котором перевешивает левая.

2. Крестики-нолики на магическом квадрате - выигрышной стратегии нет ни у кого. (Эту задачу я, возможно, когда-то знал.)

[avva.livejournal.com]

Да, все верно :)

[spamsink.livejournal.com]

2. Нет, потому что это крестики-нолики.

[liberal75.livejournal.com]

Задача2 это крестики-нолики. Я полгода назад ее решил, получил удовольствие, сравнимое с экстазом :)

[gaz-v-pol.livejournal.com]

Я знаю задачу 2 с детства (из книги Гарднера). И с тех пор считаю, что решить эту задачу невозможно. Её можно только придумать (при удачных обстоятельствах). Ну то есть можно решить, сделав обратный анализ как Налимов в шахматах, но есть ли хоть один человек, который придумал то, что Вы имеете в виду?

[avva.livejournal.com]

Вот здесь прямо в комментах (которые сейчас открываю) несколько человек, которые решили ее. Как - я понятия не имею, сам я ее решил анализом, так и не догадавшись. Но есть такие люди, умнее нас с вами. Факт.