Вопрос по информатике:
Помогите решить логическую задачу!!!Ербол и Максим*, любители сладкого, по очереди ломают шоколадку размером А×В долек. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход. Кто выиграет в этой игре, если Ербол делает первый ход? Ответ обоснуйте
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок - бесплатно!
- 26.05.2015 18:10
- Информатика
- remove_red_eye 6473
- thumb_up 35
Ответы и объяснения 1
Предположим, что Максим и Ербол играют по оптимальной стратегии.
Для удобства введем два понятия: выигрышная позиция и проигрышная позиция. Выигрышная - это позиция, которая приводит игрока, ходившего с нее, к выигрышу. Проигрышная - это позиция, которая приводит игрока, ходившего с нее, к проигрышу. Также выигрышная позиция - это позиция, ведущая противника к проигрышной. И наоборот, проигрышная позиция - это позиция, ведущая противника к выигрышной.
Вести понятия будем относительно Ербола.
Рассмотрим все возможные варианты размера шоколадки:
1x1 - Lose.
Позиция проигрышная, т.к. Ербол не сможет сделать ход.
1xN, N > 1 - Win.
Все позиции вида такого вида выигрышные, т.к. приводят к проигрышной позиции 1x1.
2x2 - Lose.
Позиция проигрышная, т.к. приводит противника к выигрышной позиции 1xN.
2xN - Win.
Все позицию такого вида выигрышные, т.к. приводят противника к проигрышной позиции 2x2.
3x3 - Lose.
Позиция проигрышная, т.к. приводит противника к выигрышной позиции 2xN или 1xN.
3xN - Win.
Все позицию такого вида выигрышные, т.к. приводят противника к проигрышной позиции 3x3.
Отсюда несложно заметить, что позиции вида NxN - проигрышные, а остальные - выигрышные.
Ответ: Если A = B, то выиграет Максим, иначе выиграет Ербол
- 27.05.2015 21:53
- thumb_up 3
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.