4.Задачи, предлагаемые для проведения конкурса КИО-2005 (конструируй, исследуй, оптимизируй)
Напоминаем правила конкурса. Учащимся школ на три дня выдается программное обеспечение, позволяющее вести эксперименты в рамках описанных сюжетов. Лучшие результаты запоминаются программой и вместе с решением, т.е. последовательностью действий ученика, отсылаются в оргкомитет. Здесь решения автоматически обрабатываются по описанным в задаче параметрам. Участники, достигшие лучших результатов, объявляются победителями.
Наряду с конкурсной версией сюжетов, создаются их расширенные версии, позволяющие конструировать аналогичные задачи самим. Эти версии передаются участникам конкурса в качестве подарка и средства для последующего содержательного общения.
Более подробная информация о конкурсе на странице www.ipo.spb.ru/kio.
Там же (после регистрации) можно получить материалы конкурса прошлого года КИО-2004. Имеется английская версия конкурса прошлого года. Она расположена на странице www.ipo.spb.ru/eng.
Сюжет 1. Шахматы со спящим противником
На обычной шахматной доске расставлены чёрные шахматные фигуры. Для каждого вида фигуры задано, сколько очков будет добавлено участнику за «съедание» этой фигуры. Чёрные фигуры не движутся. Участник ставит на доску белого коня и делает им любое количество ходов так, чтобы не попадать на клетки, бьющиеся еще не «съеденными» фигурами. Цель - набрать как можно больше очков. При равных очках сравнивается количество сделанных ходов: чем меньше, тем лучше.
Комментарий к реализации.
Программа демонстрирует битые клетки, не разрешает делать неправильные ходы. Ведет счет ходов и очков. Позволяет сохранять, проигрывать и изменять старые партии.
Полная версия (высылаемая в качестве подарка).
На шахматной доске NxM клеток можно расставлять чёрные шахматные фигуры. Для каждой фигуры (или для каждого вида фигуры) можно определять, сколько очков будет добавлено участнику за “съедание” этой фигуры. Можно задать набор белых фигур (пешек, ладей, коней, слонов или королей; пешка, добравшись до 8 горизонтали, может стать любой другой фигурой – это интересно). Возможен вариант, когда за проигрыш (не все фигуры сняты) вычитается некоторое количество очков. Тогда выгодно атаковать последним ходом “дорогую” фигуру (которая принесёт больше очков, чем отнимет проигрыш). Сконструированная игра разыгрывается по тем же правилам, что и конкурсная.
Сюжет 2. Меандры
(обработка одной из известных задач Арнольда)
Прямолинейное шоссе, идущее с запада на восток, пересекает несколько раз реку, текущую с юго-запада на восток. Занумеруем мосты в порядке их следования вдоль шоссе (с запада на восток). Проплывая под мостами вниз по реке, мы будем встречать их, вообще говоря, в другом порядке. Например, 3,4,5,2,1. Таким образом, эта река определяет перестановку. Другая река могла бы задавать другую перестановку. Но далеко не любая перестановка чисел (мостов) может быть реализована таким образом. Например, не придумать реку, проходящую через мосты в порядке 2,1,3,4,5. Будем называть перестановку меандром, если ее можно задать с помощью подходящей реки. Сколько существует различных меандров для 8 мостов?
Комментарий к реализации. Инструмент дает возможность рисовать картинки, демонстрирующие вид реки, запоминать соответствующие перестановки и вести подсчет различных перестановок, удовлетворяющих условиям задачи.
Русло реки можно изобразить ломаной, состоящей только из вертикальных и горизонтальных участков.
Полная версия (высылаемая в качестве подарка).
Шоссе не является прямолинейным, а может быть самопересекающимся (посредством шоссейных мостов). Его можно сконструировать самому и расставить мосты через реку. Задача останется та же – для данного шоссе построить все меандры.
Шоссе, идущее с запада на восток, пересекает несколько раз реку, текущую с юго-запада на восток. Занумеруем мосты в порядке их следования вдоль шоссе (с запада на восток). Проплывая под мостами вниз по реке, мы будем встречать их, вообще говоря, в другом порядке. Например, 3,4,5,2,1. Таким образом, эта река определяет перестановку. Другая река могла бы задавать другую перестановку . Но далеко не любая перестановка чисел (мостов) может быть реализована таким образом. Например, не придумать реку, проходящую через мосты в порядке 2,1,3,4,5. Будем называть перестановку меандром, если ее можно задать с помощью подходящей реки. Сколько существует различных меандров в зависимости от n? Очевидно, что а(1) =1; а(2) =1; а(3) =2.
Можно показать, что а(4) =3; а(5) = 8; а(6) =14; а(7) = 42; а(8) = 81; а(9) =262; а(10) = 538;
а(11) = 1828; а(12) = 3926; а(13) = 13820…
Формула для а(n) =1 неизвестна. Неизвестны даже асимптотики и при .
Можно доказать, что
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
1
|
1
|
2
|
3
|
8
|
14
|
42
|
81
|
262
|
538
|
|
1
|
1
|
1
|
2
|
3
|
8
|
14
|
42
|
81
|
262
|
|
|
|
1
|
1
|
2
|
3
|
7
|
14
|
36
|
81
|
|
|
|
|
|
3
|
3
|
7
|
11
|
28
|
57
|
|
|
|
|
|
|
|
14
|
14
|
36
|
57
|
|
|
|
|
|
|
|
|
|
81
|
81
|
1. Первый номер встречи с мостом нечетный.
2. Номер 1-го, 3-го, 5-го …мостов (вдоль реки) нечетны, а номера 2-го,4-го… мостов четны.
3. где или . Здесь - число меандр с мостами, для которых река пересекает шоссе первый раз под i – ым мостом.
Задача. Найти закономерность в таблице. Случайно ли число 14 появилось 5 раз?
|