Математическая задача

sirp

Далеко не сразу понял как решать.
На доске написаны натуральные числа от 1 до 1024. Алиса и Боб играют в игру, которая заключается в том, что они по очереди выбирают какое-то число из написанных, стирают его и вместе с ним все его делители. Выигрывает тот, после чьего хода, доска остается пустой. Кто выиграет при правильной игре?

1sandra

Алиса?

texnorus

Кто начинает первым, т.к. число простых чисел между 512 и 1024 нечетно.

texnorus

Поторопился(1 ведь тоже не делитель любого числа). Первый, т.к. он управляет, например, парой 509 - 1018.

Guf96rUS

как можно на основании информации о количестве простых чисел делать вывод о том кто выиграет? Ведь одно и то же множество чисел можно вычеркнуть разными способами. Например 1 2 4 можно вычеркнуть 4 способами.

sirp

Первый, т.к. он управляет, например, парой 509 - 1018.
Расшифруй, плиз

sirp

так что же, никто не может решить?

antcatt77

после длительного всматривания - появилось интуитивное предположение, что надо представить числа в виде леса и посчитать кол-во "несиметричностей"

h_alishov

На доске написаны натуральные числа от 1 до 1024. Алиса и Боб играют в игру, которая заключается в том, что они по очереди выбирают какое-то число из написанных, стирают его и вместе с ним все его делители. Выигрывает тот, после чьего хода, доска остается пустой. Кто выиграет при правильной игре?
Рассмотрим ту же задачу, но на доске написаны числа от 2 до 1024. Предположим, что в модифицированной задаче выигрывает второй. Тогда Алиса первым своим ходом стирает 1 и сводит исходную задачу к модифицированной. Если же в модифицированной задаче выигрывает первый, причем для этого ему надо стереть число m, Алиса своим первым ходом стирает m, а поскольку 1 является делителем m, то она тоже стирается и мы приходим к той же ситуации, что и в модифицированной задаче после первого хода.
Значит, выигрывает Алиса.

sirp

Об этом я думал, когда хотел решить задачу в более-менее общем виде, но для меня это оказалось трудно.
Решение (по крайней мере то, что мне им кажется довольно простое и "читерное". Подсказка: не нужно искать алгоритм выигрыша, нужно лишь сказать, кто должен выиграть.

sirp

ты меня опередил

incwizitor

что понимается под правильной игрой?
то есть ни алиса ни боб не знают как играть, но выиграет обязательно алиса, потому что она стерла единичку ?

incwizitor

сначала нужно доказать, что существует "правильная игра" для {1...1024} и {2...1024}, а потом вертеть этим понятием

sirp

сначала нужно доказать, что существует "правильная игра" для {1...1024} и {2...1024}, а потом вертеть этим понятием
вместо ухмылки ботаем лучше теорию игр. Для конечных игр с полной информацией наличие правильной игры давно доказано.
(из подсознания всплывают почему-то слова "теорема Цермело", но не уверен, что это из той оперы )

incwizitor

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

shpanenoc

Вопрос: Кто выиграет при правильной игре?
Ответ: Алиса.
Вопрос: А какая она, эта правильная игра?
Ответ: А фиг его знает! Эта задача уже сложнее

incwizitor

хехе
да не..я почти всё решение понял, но хотелось бы задать эту задачку своим друзьям, которые не шарят так глубоко в науке, но любят разгадывать головоломки
поэтому хочется, чтобы я ее мог объяснить с решением;)
теория игр для этого нафиг мне не нужна

Xephon

ничего тут ботать не нужно, и заумных фраз тоже
утверждение, что есть правильная игра доказывается индукцией по мощности множества чисел, на котором мы играем

incwizitor

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

sirp

Так в данном случае красота задачи и неожиданность решения заключается как раз в том, что мы не ищем алгоритм выигрыша (как обычно решаются "игровые" задачи а решаем задачу совсем по другому.
даже если мы докажем существование правильной игры по индукции, то это не придаст решению исходной задачи ни краткости, ни лаконичности...
Вот с этим совершенно согласен. Но человек, более менее образованный в математике, существование правильной игры должен чувствовать интуитивно. Типа "это как так, чтобы ни у одного из игроков не было выигрышной стратегии? а кто же тогда должен выиграть?"

incwizitor

Так в данном случае красота задачи и неожиданность решения заключается как раз в том, что мы не ищем алгоритм выигрыша (как обычно решаются "игровые" задачи а решаем задачу совсем по другому.
это меня проперло
но существование мне на пальцах еще никто не смог объяснить

Mausoleum

Если ни у кого из игроков нет выигрышной стратегии, но оба играют правильно (оптимально нередко случается ничья =) Например, крестики-нолики на доске 3 на 3 =)

ARTi

из той же оперы задача: кто выиграет при правильной игре в "мигающие шахматы" - там нужно делать за один ход два перемещения фигур

zuzaka

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

ARTi

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

zuzaka

почему? как докажешь, что у белых нет выигрыша?

sirp

Если ни у кого из игроков нет выигрышной стратегии, но оба играют правильно (оптимально нередко случается ничья =)
Но в нашем случае ничья не предусмотрена. И видишь, в самой своей фразе ты тоже утвердаешь существование правильной игры. Т.е. для тебя существование правильной игры в случае конечной игры с полной информацией тоже самоочевидно.

ARTi

опять ты прав - задача должна звучать так: доказать, что при правильной игре белые не проиграют

sirp

существование мне на пальцах еще никто не смог объяснить
Долго думал, как же объяснить на пальцах, но ничего проще индукции так и не придумал

sirp

потому что на самом деле они скорее всего все-таки порвут
Оставить комментарий
Имя или ник:
Комментарий: