Наткнулся тут на официальном сайте ЕГЭ на образец заданий по информатике (http://www1.ege.edu.ru/images/stories/e ... o_2010.pdf).

Особый интерес вызвало задание С3 из третьей части экзамена (страница 19 вышеупомянутого документа).

Вот его текст: Два игрока играют в следующую игру. На координатной плоскости стоит фишка. В начале игры фишка находится в точке с координатами (–2,–1). Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3,y), (x,y+4), (x+2,y+2). Игра заканчивается, как только расстояние от фишки до начала координат превысит число 9. Выигрывает игрок, который сделал последний ход. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

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

Здесь работает анализ выигрышных и проигрышных позиций. Занятие довольно трудоемкое.
Т.е. нужно изобразить все интересующие на позиции - узлы сетки в пределах круга радиуса 9 с центром в начале координат, - и помечать последовательно (1) кружком все узлы, из которых можно сделать выигрывающий ход (2) крестиком все узлы, из которых можно попасть только в узлы из п. 1 (3) узлы, из которых есть ход в какой-либо узел п. 2 и.т.д, пока не доберемся до начальной точки.

У меня получилось, что выигрывает первый ход
А. (x+3,y) -> (1,-1)
Дальше три варианта:
1) Б. -> (1,3) , А. -> (4, 3)
2) Б. -> (4,-1), А. -> (4, 3)
3) Б. -> (3, 1), А. -> (5, 3).
После этих ходов от игроков уже ничего не зависит. Игрок Б. делает произвольный ход, и игрок А. выигрывает любым ходом. Проверить несложно.

Если я нигде не сбился, то остальные два хода, возможные в начальной позиции, проигрывают.


А вообще, этим заданиям следовало предпослать эпиграф из Лема:
"Детская мода XXI века: мальчик, переодетый компьютером".

Да, у меня получился точно такой же результат. И я тоже использовал графическое представление этой задачи.

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

Словом, на мой взгляд, абсолютно неадекватная для ЕГЭ задача.

P.S. Я потом нашёл методические материалы, где подобная задача решалась методом перебора всех возможных вариантов. Это жёстко.

На мой взгляд, это вполне укладывается в рамки. Например, посчитали по теореме Пифагора, где прямая x=8 пересекается с окружностью, получается y=sqrt(26)>5, и видно, что узлы с ординатой до 5 лежат внутри круга.
Согласен, что задача неудачная. Полным перебором решать долго и нудно, а тот способ, о котором я говорил, школьники знать не обязаны.

Не так уж много состояний. Можно и перебрать все.
Потом из дерева состояний легко заметить, то что говорил vor
Мне эта задача понравилась, в свое время в школе я таких не решал )