Графы и теория игр: задачи С3, В9, В13. 
Автор: Д.А. Михалин, учитель информатики ГБОУ ЦО № 345 

Введение 
Несколько заданий из демоверсии ЕГЭ 2013 года связано с графами или построением дерева игры. Это задачи A2, B9, B13 и C3. При этом в задаче B9 граф изображен явно, в задаче C3 требуется построить дерево игры. В двух других задачах про графы явно не сказано, но их использование может упростить решение, а также показывает схожесть различных по формулировкам задач.

История задачи C3. 
Несколько лет мы решали задачи про двух игроков, которые перекладывали камушки, двигали фишки на координатной плоскости и т. д. К этим задачам было много справедливых претензий. В прошлом году мы увидели совсем новое задание – на подсчет числа возможных программ. Но и эта задача была трудна для проверки (например, была размыта граница 2 и 3 баллов), было не очень понятно, что она проверяла (вряд ли заявленное «умение построить алгоритм»), и от нее тоже отказались. В этом году мы снова увидели перекладывающих камни Петю и Ваню в задаче, одно только условие которой занимает почти страницу. Сначала это вызвало ропот многих учителей и испуг ребят, но при внимательном рассмотрении выяснилось, что авторы сделали попытку не усложнить задачу, а приблизить задачу на игры к реальным приемам определения выигрышной стратегии: с конца, или начиная с тривиальных случаев. При этом также уменьшается объем вычислительной работы, что снижает вероятность ошибки.

Скачать полный разбор вариантов заданий и их решений:
Графы и теория игр: задачи С3, В9, В13.