|
Двое поочерёдно называют по одному числу, которое может равняться 0 или 1. Это делается в общей сложности 2014 раз. Первый игрок выигрывает, если сумма названных чисел не делится на 3, и проигрывает в противном случае. Есть ли у первого игрока выигрышная стратегия? Мне кажется, что первый должен сперва назвать нуль, а затем после каждого хода второго называть бит, противоположный названному вторым. В таком случае после 2013 ходов сумма цифр будет равна 1006, что даёт остаток 1 при делении на 3. И тогда второй не сможет, как бы ни хотел, своим последним ходом сделать число кратным трём. Я права? Единственна ли данная стратегия? И ещё вопрос: Почему студентам задают менее трудные задачи, нежели школьникам? Опубликованная мной задача предлагалась на Московской Городской Студенческой Олимпиаде. задан 29 Окт '14 11:55 
حنين
показано 5 из 7
показать еще 2
|
|
Да, выигрышная стратегия здесь единственна. Докажем индукцией по числу $%n$% (полу)ходов, оставшихся до конца игры, что позиция является проигрышной для того, кто в неё начинает, тогда и только тогда, когда сумма всех названных к этому моменту чисел сравнима с $%n$% по модулю 3. При $%n=0$% это верно по условию: второй игрок сделал последний ход, игра закончилась. Формально начинает первый, и он проиграл в том и только в том случае, если сумма названных чисел делится на 3, то есть сравнима с нулём. Ясно, что выигрышной является только такая стратегия, когда оппоненту предлагается проигрышная для него позиция. Если таковой является позиция с суммой, дающей остаток $%k$% от деления на 3, то на момент предыдущего хода сумма должна быть сравнима с $%k+1$% по модулю 3. Если она сравнима с $%k$%, то называем 0 и выигрываем. Если сравнима с $%k+2$%, то называем 1, и тоже выигрываем. А если она сравнима с $%k+1$%, то после хода будет $%k+1$% или $%k+2$%, и проигранной для оппонента ситуации не достичь. Из сказанного следует, что при увеличении на один (полу)ход длины игры, проигрышное для начинающего в этой позиции число увеличивается на 1, и оно всегда единственно. Это обосновывает шаг индукционного рассуждения. Если игра длится 2014 (полу)ходов, то "проигрышный" остаток равен 1. На деле он равен нулю, поэтому начальная позиция является выигранной. Чтобы выиграть, необходимо и достаточно назвать такое число, при котором сумма станет сравнима с 2013 по модулю 3, то есть будет делиться на 3. А это значит, что надо назвать 0. Теперь второй (в основной партии) игрок должен проиграть. Из сказанного выше следует, что выигрышный ход в любой ситуации всего один, если он есть. Поскольку описанная в тексте вопроса стратегия выигрывает, то никакой другой быть не может. отвечен 29 Окт '14 15:36 
falcao |
По поводу сложности задач: в принципе, она бывает разной на разных олимпиадах. Правда, я когда-то замечал тот факт, что самые трудные задачи олимпиад типа Всесоюзной (в моё время) были труднее, чем задачи для студентов. Думаю, это связано прежде всего с тем, что сами по себе олимпиады -- они скорее для школьников, то есть там "спортивная" часть имеет большую значимость. Парадокс состоит в том, что чем меньше человек знает, тем легче ему "соображать", то есть догадываться до чего-то неожиданного в "нестандартной" ситуации.
А где она самая высокая?
Как я уже говорил, в моё время, когда я сам участвовал в олимпиадах (конец 70-х), наиболее трудные задачи бывали на Всесоюзных олимпиадах. Помимо этого, некоторые весьма трудные задачи встречались на Турнире городов. А вот задачи с Международной обычно бывали не столько трудные, сколько "навороченные".
Забыл ещё сказать про "Задачник "Кванта"". Там тоже порой встречалось нечто весьма трудное.
Спасибо, буду в курсе. Начну задачник "Кванта" потихочечку осваивать. Там более 2000 задач - на любой вкус и цвет!
@حنين , "Это делается в общей сложности 2014 раз" можно понимать как минимум двояко. Сделано 2014 ходов или полуходов? Что считается за один раз?
@Казвертеночка: тут игра проанализирована в общем виде, она не сложнее игры Баше. Ясно и то, как надо играть, и то, как нельзя. Поэтому толкование условия не принципиально. Есть ответ на оба случая.
@falcao, большое спасибо!