Страниц: [1]
  Печать  
Автор Тема: Нужна помощь  (Прочитано 3018 раз)
0 Пользователей и 1 Гость смотрят эту тему.
ianjamesbond
Свой человек
***
Offline Offline

Сообщений: 437

СПАСИБО
-вы поблагодарили: 54
-вас поблагодарили: 58



Просмотр профиля Email
: Август 22, 2013, 12:46:30 �

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

Дана доска 2013x2013. В каждой клетке доски стоит стрелка, которая может указывать вверх, вниз, вправо или влево. Из левого нижнего угла доски стартует путник, который ходит согласно направлениям стрелок (если стрелка отправит путника вне доски, он простоит один ход в этой клетке). После хода путника стрелка в клетке, где он стоял, поворачивается на 90 градусов по часовой стрелке. Хождение завершается, когда путник достигает верхней правой клетки. Докажите, что хождение завершается, вне зависимости от начальной расстановки стрелок.
Записан

//текст доступен после регистрации//
Крипто
Давненько
**
Offline Offline

Сообщений: 199

СПАСИБО
-вы поблагодарили: 60
-вас поблагодарили: 55



Просмотр профиля
Ответ #1 : Август 23, 2013, 10:55:20 �

Ну это смотря как подойти... А если в куче Количество камней n=p-1. тогда Алиса первым ходом и выигрывает... Так что не бесконечное...

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

Итог или условия писать конкретнее, или это не доказуемо.
Последнее редактирование: Август 23, 2013, 11:07:53 от Крипто Записан

КаждАму чИловеку свойствИнно Ашибаться, но только глупцу свойственно упорствовать в ошибке (Цицерон).
BIVES
Умник
****
Offline Offline

Сообщений: 687

СПАСИБО
-вы поблагодарили: 53
-вас поблагодарили: 272


Просмотр профиля
Ответ #2 : Август 27, 2013, 01:54:02 �

1) А если попробовать от противного.
Пусть существует максимальное количество камней, для которого у Боба есть выигрышная стратегия. Т. е. для n=r Боб выигрывает, а для всех n>r выигрывает тот, кто ходит первым.
Но тогда если у нас (r+2)!+r+1 камней, то какое бы число р-1 не убрал первый игрок у нас останется число камней большее чем r (т. к. (r+2)!+2,..., (r+2)!+r+1, (r+2)!+r+2 - составные).
Поэтому, по сделанному предположению выиграет Боб (осталось больше чем r камней и  ходит Боб) получили противоречие.
Последнее редактирование: Август 27, 2013, 09:13:35 от BIVES Записан
Страниц: [1]
  Печать  
 
Перейти в: