Двое игроков по очереди называют натуральные числа, причем следующее число должно быть строго меньше предыдущего, но не меньше половины предыдущего. Проигрывает тот, кто будет вынужден назвать число 1. Первым ходом первый игрок назвал 2003. Кто выиграет?
Ответ: Выигрывает второй. Проводя анализ с конца, получаем, что выигрышными позициями для второго будут 1535, 767, 383, 191, 95, 47, 23, 11, 5, 2
Комментарии
В ответе пропущена одна позиция между 191 и 47 - это 95.
Я, кстати, решал с начала и получил такую комбинацию (жирным выделены ходы второго):
2003 - 1001 - 500 - 249 - 124 - 61 - 30 - 14 - 6 - 2 - 1
Но не очень понятен один момент - 1 не меньше половины от 2, это ровно половина от 2. Может ли первый игрок его называть? По условию задачи, вроде, нет, но в таком случае игра зайдёт в тупик.
*её называть (единицу).
Или на последний ход это правило не распространяется?
Наверно, правильнее это обговаривать в условии, но не хотелось бы его (условие) загромождать
Спасибо, что заметили про 95
Не меньше - это значит больше либо равно. Если следующее число равно половине от предыдущего, то это соответствует условию "не меньше половины", поэтому называть после двойки единицу, это правилам соответствует. А вот после 2003 называть 1001 - это как раз не по правилам.
Ошибка в условии, никто не мешает второму назвать следующим ходом число "2"
Как это понять: "следующее число должно быть строго меньше предыдущего, но меньше половины предыдущего"?
Если число меньше половины предыдущего, то оно меньше и самого предыдущего... Например, после 2 уже не назвать следующее число, т.к. 1 - последнее, меньшее 2, натуральное число и оно не меньше половины двойки.
Что-то напутали в условии? Или я что-то не понял?
ВНИМАНИЕ АДМИНИСТРАТОРАМ И РЕДАКТОРУ! Поправьте условие задачи: "...следующее число должно быть строго меньше предыдущего, но НЕ меньше половины предыдущего." Иначе второй игрок может сразу назвать 2 или 3.
Спасибо! Ошибку исправил
нельзя точно сказать, кто это будет. строго говоря, выигрывает тот, кто первым назовет 2. например, если каждый называет цифру на 1 меньше, чем предыдущая, то выиграет второй игрок, так как он, начиная с 2002 всегда будет называть только четные числа (в том числе и 2). если каждый будет называет цифру ровно в 2 раза меньше предыдущей, то выиграет первый.
Если игроки будут называть числа как попало, то выиграть может разумеется любой из них. Но второй игрок может гарантированно выиграть при правильной тактике. А тактика в том, чтобы называть числа из приведенного в ответе ряда. Если второй назвал 1535, то первый может по правилам назвать числа в диапазоне от 768 до 1534. После любого из них второй назовет 767 и так далее.
Ряд строится по формуле A[i+1] = A[i]*2 + 1
Ты права 2 игрок выиграл.
Второй назвал число 2002 и выиграл. Чего время тянуть?
Согласно условию: "причем следующее число должно быть строго меньше предыдущего, но не меньше половины предыдущего". А приведенном ответе (1535, 767, 383, 191, 95, 47, 23, 11, 5, 2) последующие числа меньше половины предыдущего. Должно быть: 2003, 1002, 501, 251, 126, 63, 32, 16, 8, 4, 2, 1.
Надо называть простые числа.1002,501,63,32,16,8,4 - не являются простыми.А что касается приведенного примера,тоже неправильно.767 меньше половины 1535.Так как 1535/2=767.5 Я думаю ни кто не станет спорит,что 767 меньше чем 767.5,а следовательно не подпадает под условия задачи.Это касается и остальных чисел в приведенном примере.
В ответе приведены числа, которые должен называть один из игроков для победы. Между ними числа говорит также другой игрок, поэтому нарушений правил никаких нет.
Решение, изложенное в ответе понятно, но кажется мне достаточно трудоёмким и не очень поучительным. Я же хотел бы показать, как по мне, очень интересное решение данной задачи. Приступим. Мы будем пользоваться одной из главных теорем теории чисел: в любой конечной игре для двух игроков без ничьих есть стратегия для одного из игроков. Доказывается она очевидно, надо просто посмотреть на всевозможные комбинации ходов. Но вернемся к нашей задаче. Очевидно, что в нашей игре нет ничьих, а ходов будет не больше 2003, а значит игра конечна, ведь каждым ходом число уменьшается как минимум на 1. Соответственно либо у второго, либо у первого есть выигрышная стратегия. Если у второго, то нам хорошо, мы решили задача. Предположим противное, пускай у первого есть выигрышная стратегия. Пускай она записана в большой книге, будем иногда туда подглядывать. Попробуем своим ходом походить в число 2002. Посмотрим на ход противника. Он может походить в числа от 1001 до 2001. Если его ходом будет число от 1002 до 2001, то мы своим первым ходом могли "прыгнуть" в это число, и играть дальше в роли первого по его стратегии, а первый игрок становится как бы вторым. Это так называемая "передача хода". В таком случае мы выиграли. Тогда пускай противник походил в 1001. Мы опять провернем нашу вышеописанную стратегию, походив в 1000. Либо мы стали первым игроком, либо первым игроком, либо первый прыгнул в число 500. Здесь мы опять проделываем нашу стратегию, но здесь, прыгнув в 499, мы оставляем противнику ходу от 250 до 498. Но в любое из этих чисел можно прыгнуть и из 500, значит мы могли сделать это и продолжить играть в роли первого. Т.е. если бы у первого была выигрышная стратегия, то второй мог бы играть так, чтобы первый проиграл. Противоречие. Получилось, что мы выиграли! Все лавры достаются нам!Возможно это решение и выглядит громоздким, но это не так. Просто оно текстовое, и я всё подробно пояснял. Метод, используемый в этой задаче(передача хода) используется в широком спектре задач, поэтому советую тем, кто о нем не знал, познакомиться с ним поближе. Спасибо за внимание, удачного дня.
Решение, изложенное в ответе понятно, но кажется мне достаточно трудоёмким и не очень поучительным. Я же хотел бы показать, как по мне, очень интересное решение данной задачи. Приступим. Мы будем пользоваться одной из главных теорем теории чисел: в любой конечной игре для двух игроков без ничьих есть стратегия для одного из игроков. Доказывается она очевидно, надо просто посмотреть на всевозможные комбинации ходов. Но вернемся к нашей задаче. Очевидно, что в нашей игре нет ничьих, а ходов будет не больше 2003, а значит игра конечна, ведь каждым ходом число уменьшается как минимум на 1. Соответственно либо у второго, либо у первого есть выигрышная стратегия. Если у второго, то нам хорошо, мы решили задача. Предположим противное, пускай у первого есть выигрышная стратегия. Пускай она записана в большой книге, будем иногда туда подглядывать. Попробуем своим ходом походить в число 2002. Посмотрим на ход противника. Он может походить в числа от 1001 до 2001. Если его ходом будет число от 1002 до 2001, то мы своим первым ходом могли "прыгнуть" в это число, и играть дальше в роли первого по его стратегии, а первый игрок становится как бы вторым. Это так называемая "передача хода". В таком случае мы выиграли. Тогда пускай противник походил в 1001. Мы опять провернем нашу вышеописанную стратегию, походив в 1000. Либо мы стали первым игроком, либо первым игроком, либо первый прыгнул в число 500. Здесь мы опять проделываем нашу стратегию, но здесь, прыгнув в 499, мы оставляем противнику ходу от 250 до 498. Но в любое из этих чисел можно прыгнуть и из 500, значит мы могли сделать это и продолжить играть в роли первого. Т.е. если бы у первого была выигрышная стратегия, то второй мог бы играть так, чтобы первый проиграл. Противоречие. Получилось, что мы выиграли! Все лавры достаются нам!Возможно это решение и выглядит громоздким, но это не так. Просто оно текстовое, и я всё подробно пояснял. Метод, используемый в этой задаче(передача хода) используется в широком спектре задач, поэтому советую тем, кто о нем не знал, познакомиться с ним поближе. Спасибо за внимание, удачного дня.
у первого есть преимущество в ход, т.е. та самая +ЕДИНИЦА в ходе
Строго говоря Ваше решение действительно отвечает на вопрос задачи - "Кто выиграет". Но я бы не сказал, что оно проще. Фактически это точно такой же анализ, как у автора, только проведенный с начала, а не с конца и требует столько же шагов анализа. При этом авторский вариант позволяет не только ответить на вопрос о победителе, но и найти ту самую выигрышную стратегию из "книги".
Задачи не имеет решение ибо выиграть может каждый это как игра в шахматы
Согласен.Но если,каждый будет называть число примерно в 2 раза меньшее предыдущего,то выиграет второй.
2 игрок выигрывает
условие нужно исправить. Вместо "натуральные" нужно указать "простые" числа