Теория игр в заданиях дистанционных олимпиад по информатике
Всероссийская Олимпиада по информатике «Отличник» проводится на дистанционной основе через сеть интернет уже не первый год. За все года проведения олимпиады участникам предлагались самые разнообразные задания по информатике, математике, теории игр и другие. Самыми сложными, на наш взгляд, являются именно последние из перечисленных. В данной статье мы хотим немного подробнее рассмотреть такой тип заданий.
В методическом разделе на сайте дистанционных олимпиад приведены примерные решения заданий на теорию игр. В разделе с примерными решениями сложных олимпиадных заданий зачастую нет данных, каким образом получен ответ, нет никаких пояснений. Но несмотря на это, указана стратегия. Просто есть ответ на вопрос, но не дано непосредственно объяснение, как найдены или подобраны эти результаты. Мы не видим из решения ничего. Сами решения олимпиадных задач, конечно, замечательны, они совершенно верные. Эти решения достаточны, для того чтобы получить максимальное число баллов дистанционной олимпиады по информатике, но, для того чтобы объяснить школьникам, откуда появились эти значения, нужно, конечно, дать какое-то пояснение. Нужно всё-таки дать возможность понять, как же были получены.
Собственно об этом и пойдет сегодня речь. Мы можем предложить вам теорию решения данного раздела сложных олимпиадных заданий на теорию игр с пояснениями, которые достаточны для того, чтобы ребята, разобрав данное решение, могли решать и другие подобные задачи на олимпиаде по математике, информатике и даже физике, близкие по логическим умозаключениям. Хорошим примером олимпиадного задания является задача на количество камней и игру с ними.
Давайте вначале посмотрим и проанализируем условия задачи. Например, нам дана куча с камнями. Известны правила, что можно добавлять в кучу один камень, два камня или увеличить количество камней в куче в два раза. И также известно, что исходное число камней S больше или равно единице, но меньше, либо равно 26. Игрок победит в том случае, если число камней будет больше или равно двадцати семи. Здесь, по сути, изложили исходные данные. Теперь после того, как мы определились, что дано, непосредственно рассмотрим те вопросы, на которые нам предстоит ответить. Нужно указать такие значения S исходного количество камни, которые первый игрок может выиграть своим первым ходом. Это довольно-таки простая задача, на нее несложно дать ответ.
Исходное число камней больше S больше либо равно 1, меньше либо равно 26. Первым ходом первый игрок может сделать один из трёх вариантов ходов, добавить один камень, добавить два камня или увеличить количество камней в два раза. После того, как совершит свой ход, число камней должно быть больше либо равно 27 для того, чтобы первый мог выиграть первым ходом. Таким образом у нас получается такая совокупность неравенств, решая которую мы находим для первого неравенства. Тут, конечно, можно сказать что, если число камней, например, 26, то можно просто добавить один камень. Но нас в условии просят указать хотя бы один какой-то выигрывающий ход. Поэтому мы указали, что в общем случае можно удвоить количество камней и выиграть. Этого все, что и достаточно для ответа.
Как мы и отмечали ранее, всероссийские дистанционные олимпиады по любому предмету требуют подготовки от учащихся. Но задания на олимпиады при всей кажущейся сложности можно легко и логично решить. Это и было доказано в данной статье.
