Сюжет 3. Автомат для голосования
Имеется неограниченное число логических элементов для голосования с тремя входами и одним выходом (если на двух или трех входах такого элемента 1, то на выходе 1, иначе на выходе 0). Из них надо собрать устройство для голосования жюри из 7 человек, используя наименьшее число элементов (на наборах входных сигналов, содержащих больше трех 1, устройство должно выдавать 1, на остальных - 0). Правильно работающие устройства сравниваются по числу элементов.
Устройства, которые работают неправильно, сравниваются по доле наборов, на которых они дают правильный результат. При равной доле лучше тот, у кого меньше элементов.
Комментарий к реализации.
В реализации задачи конструктивный элемент можно протестировать и понять, как он работает. Схема собирается посредством движений мышки. После сборки запускается тестирование. Подсчитывается и демонстрируется доля наборов, на которых голосование правильное. Демонстрируется работа схемы на неправильных наборах. Ниже нарисована схема для 5 голосующих.
Полная версия (высылаемая в качестве подарка).
Возможность создавать логические элементы с одним, двумя и тремя входами и одним выходом (задавая таблички).
Далее ставить задачи (задавая таблицей входов и выходов желаемый результат) и конструировать схемы из набора заданных элементов. Программа тестирует схемы, демонстрируя те комбинации, на которых желаемый результат отличается от того, который получается на построенной схеме. Можно также показать процент наборов, не удовлетворяющих условию.
Имеется неограниченное число логических элементов для голосования с тремя входами и одним выходом (если на двух или трех входах такого элемента 1, то на выходе 1, иначе на выходе 0). Из них надо собрать устройство для голосования жюри из 7 человек, используя наименьшее число элементов (на наборах входных сигналов, содержащих больше трех 1, устройство должно выдавать 1, на остальных - 0). Правильно работающие устройства сравниваются по числу элементов.
Устройства, которые работают неправильно, сравниваются по доле наборов, на которых они дают правильный результат. При равной доле лучше тот, у кого меньше элементов.
Комментарий к реализации.
В реализации задачи конструктивный элемент можно протестировать и понять, как он работает. Схема собирается посредством движений мышки. После сборки запускается тестирование. Подсчитывается и демонстрируется доля наборов, на которых голосование правильное. Демонстрируется работа схемы на неправильных наборах. Ниже нарисована схема для 5 голосующих.
5.Спецификация задач по математике для дистанционных олимпиад Типология задач
Вид 1. Задачи на описание множества одним из двух способов по описанию другим: описание предикатами и конструктивное описание.
Подвид 1-1. Комбинаторные задачи на подсчет числа вариантов, в которых по словесному описанию множества нужно написать формулу с переменной либо с числовыми значениями.
Тип 1. Комбинаторные задачи с видом ответа – формула (свернутый посредством использования типовых комбинаторных функций) алгоритм.
Технологизация ввода решения предполагает один этап.
Пример задачи типа 1. Трамвайный билет называется счастливым по-питерски, если сумма первых трех его цифр равна сумме трех последних цифр. Трамвайный билет называют счастливым по-московски, если сумма его цифр, стоящих на четных местах, равна сумме цифр, стоящих на нечетных местах. Сколько существует билетов, счастливых и по-питерски, и по-московски, включая и билет 000000?
Замечания по реализации. Решение задачи сводится к описанию алгоритма вычислений, который как во многих комбинаторных задачах определяется формулой вычисления, содержащей натуральные числа, арифметические операции, функции «факториал» и «число сочетаний» и, возможно, функцию ввода знакопеременной суммы с общим членом для использования формулы включений-исключений. Формула вводится через клавиатуру, содержащую базовый набор комбинаторных функций.
Параметризация. Ввести параметр 2n – длина набора. Возможен еще один параметр – p, определяющий основание системы счисления, в которой задается билет.
Замечания по верификации ответа. При параметризации, решение проверяется для различных значений параметров и принимается, если все тесты прошли успешно.
Тип 2. Комбинаторные задачи с промежуточным этапом решения, предполагающим описание решения предикатом, и конечным этапом, сводящимся к типу 1.
Пример задачи типа 2. Дан куб 12х12х12, который разрезан плоскостями, параллельными граням куба, на единичные кубики. На сколько частей разделится куб, если в нем провести сечение в виде правильного шестиугольника?
Замечания по реализации. Решение задачи сводится к решению в неотрицательных целых числах, не превосходящих 11, уравнений a+b+c=16 и a+b+c=17. Ответ можно вводить в виде числа либо в виде предиката. В обоих случаях задача сохранит содержательность. Возможно введение двух этапов решения: описание предикатом (идея решения – изоморфизм) и описание алгоритмом вычисления (числом, которое может вводиться через клавиатуру, содержащую базовый набор комбинаторных функций – факториал, число сочетаний и арифметические операции).
Параметризация. Ввести параметр n – длина ребра. Возможен еще один параметр – m, определяющий вид сечения.
Замечания по верификации ответа. При параметризации, решение проверяется для различных значений параметра и принимается, если все тесты прошли успешно.
Тип 3. Комбинаторные задачи с промежуточным этапом решения, предполагающим описание решения рекуррентной формулой, и конечным этапом, сводящимся к типу 1.
Пример задачи типа 3. Имеется k красок. Сколькими способами можно раскрасить стороны данного правильного n-угольника так, чтобы соседние стороны были окрашены в разные цвета (многоугольник поворачивать нельзя).
Замечания по реализации. Решение задачи связано с использованием метода математической индукции. Поэтому частью решения является написание рекуррентных формул. В данном случае это такие формулы:
X[1]=0; X[2]=k(k-1); X[n]=(k-2)X[n-1] + (k-1)X[n-2]. Далее по индукции доказывается явная формула X[n]=(k-1)^n+(k-1)(-1)^n.
Задачу можно разбить на этапы. На первом этапе предлагается виртуальная клавиатура, не содержащая степени, но имеющая клавиши для ввода рекуррентных соотношений. На втором этапе предлагается другая клавиатура: без средств для ввода рекуррентных соотношений, но со средствами ввода любых элементарных функций, которые должны быть реализованы для натуральных чисел произвольной длины.
Параметризация. Естественная параметризация: параметр k – число красок, параметр n – число сторон многоугольника.
Замечания по верификации ответа. На первом этапе решение проверяется на последовательностях для различных значений параметра k, на втором этапе сравниваются две функции для различных значений параметров k и n. Решение принимается, если все тесты прошли успешно.
Тип 4. Комбинаторные задачи с видом ответа – формула или формулы, которые задают оценки числа вариантов сверху и снизу.
Пример задачи типа 4. В школе изучают 2n предметов. Все ученики учатся на «четыре» и «пять» и никакие два не учатся одинаково. Ни про каких двух учеников нельзя сказать, что один учится лучше другого. Найдите как можно более хорошую оценку сверху для числа учеников в школе.
Замечания по реализации. Для ввода ответа нужна виртуальная клавиатура с описанными выше функциями и возможностями.
Параметризация. Параметризация неочевидна, необходимо объединять в один класс различные комбинаторные задачи.
Замечания по верификации ответа. Решение сравнивается с точным решением, подсчитывающимся для различных значений n по алгоритму, либо сравнивается с эталонной оценкой, предлагаемой в решении задачи. Решения разных участников могут сравниваться по степени приближения к точному решению.
Подвид 1-2. Комбинаторные задачи на перечисление вариантов, в которых требуется описать множество вариантов, используя предикаты, задающие искомые наборы, либо алгоритмы, генерирующие эти наборы.
Тип 5. Комбинаторные задачи на перечисление вариантов, в которых имеется два этапа, первый из которых – конкретный пример перечисления (для небольшого значения n), второй – формула, указывающая искомое сопоставление.
Пример задачи типа 5. В дом отдыха с четырехразовым питанием на 15 дней приехала группа из 60 отдыхающих. За обеденным столом 61 место. На одном месте постоянно сидит директор дома отдыха. Директор хочет сам познакомиться с каждым отдыхающим и познакомить их между собой. Для этого он хочет сажать отдыхающих каждый раз по-новому, чтобы ни один из них не сидел дважды на одном и том же месте и чтобы у всех отдыхающих и у директора каждый раз был новый сосед справа. Как это сделать?
Замечания по реализации. Решение задачи записывается формулой:
на (k+1) день отдыхающие садятся в порядке
k, k–1, k–1+2, … k–1+2–3+4–…+(-1)^(i-1), … (mod 60),
где все отдыхающие занумерованы числами от 0 до 60, а номера мест нумеруются от директорского места по часовой стрелке. В решении задачи можно выделить два этапа: этап частных примеров с небольшим числом отдыхающих 2-3 человека. На этом этапе ответ вводится в графической форме – перемещением кружков по кругу. Второй этап – формализация ответа и переход к общему случаю. Для ввода ответа предлагается изоморфное описание ответа в виде правила сопоставления (номера отдыхающих – номера стульев). Для ввода формулы служит виртуальная клавиатура, включающая операцию суммирования конечной последовательности, операцию вычисления остатка, а также стандартные арифметические операции, вместе с операцией возведения в степень. Операции выполняются над целыми числами произвольной длины.
Параметризация. Естественная параметризация: параметр n – число отдыхающих. Можно ввести «камуфлирующий» параметр s – число мест за столом (s>n). Число отдыхающих будет s-1. Камуфлирующим будем называть параметр, не усложняющий решения задачи, но позволяющий сделать ее многовариантной.
Замечания по верификации ответа. Поскольку решений задачи может быть много, проверка ведется не сравнением с эталонным ответом, а проверкой выполнения условий задачи.
Подвид 1-3. Описание множества через использование глобальных характеристик по описанию локальными характеристиками.
Тип 6. Описание языков предикатами по заданной грамматике.
Пример задачи типа 6. Назовем словом любую конечную последовательность букв А и Б. Есть две операции над словами: первая – в любом месте слова вставить А и в конце слова приписать Б, вторая – в любом месте слова вставить АБ. Докажите, что слова, которые можно получить из слова АБ, используя только первую операцию – это те же слова, которые можно получить из слова АБ, используя только вторую операцию.
Указание. Описать каждое из множеств слов, используя предоставленные инструментальные средства.
Замечания по реализации. Решением в обоих случаях является множество слов, у которых среди любых первых букв количество букв А не меньше, чем количество букв Б. Таким образом, для описания языка нужны средства подсчета числа букв. Например, функция A(n,m), определяющая число букв А на промежутке от n-ой до m-ой букв. Кроме этого нужны кванторы, чтобы записать предыдущее высказывание. Кроме этого, нужны «камуфлирующие» функции, расширяющие описательные возможности языка, например SAB(n,m) - если на n-ом месте стоит буква А, то на m-ом месте стоит буква Б.
Параметризация. Разные правила генерации слов и разные начальные слова.
Замечания по верификации ответа. Ответ проверяется на правилах грамматики, по которым генерируются слова, а затем проверяются подстановкой в предикат. Нужна обратная проверка, поэтому лучше сгенерировать все возможные слова заданной длины и проверить совпадение множеств.
Подвид 1-4. Конструирование геометрических объектов с заданными свойствами.
Тип 7. Геометрические задачи, решение которых определяется графом.
Пример задачи типа 7. Найдите на клетчатой бумаге фигуру, составленную из наименьшего числа клеток и обладающую тем свойством, что если двое играют в крестики-нолики, то на клетках этой фигуры, то начинающий всегда может первым поставить три крестика подряд.
Замечания по реализации. Решением задачи является фигура из клеток. Внутренне представление ответа – граф, который определяется вершинами, стоящими в выбранных клетках и ребрами, соединяющими вершины в смежных (по сторонам клеток) клетках.
Параметризация. Задача параметризуется неочевидно, например, изменением правил игры.
Замечания по верификации ответа. Можно организовать полный перебор вариантов игры с эвристическим выбором приоритета очередного хода.
Тип 8. Задачи на конструирование отношения на множестве с заданными свойствами (решение определяется некоторым графом).
Пример задачи типа 8. На площади собралось 50 гангстеров. Они одновременно стреляют друг в друга, причем каждый стреляет в ближайшего к нему или в одного из ближайших. Каково минимальное количество убитых? [Расположите на плоскости 50 точек, изображающих стреляющих, задайте расстояния между ними и укажите, кто в кого стреляет].
Замечания по реализации. Интерфейс задачи – интерфейс для изображения ориентированного взвешенного графа.
Параметризация. Естественный параметр – число стреляющих гангстеров. Другие, менее очевидные, возможности для варьирования – изменение правил, по которым идет стрельба.
Замечания по верификации ответа. Верификация простая – просто проверить условия задачи.
Подвид 1-5. Конструирование многочленов с заданными свойствами.
Тип 9. Конструирование целых чисел с заданными свойствами в форме значений конкретных заданных многочленов.
Тип 10. Конструирование целых чисел с заданными свойствами в форме значений n многочленов, коэффициенты которых заданы функцией a(n;k).
Пример задачи типа 9 и 10. F1, F2, F3,…, Fn – многочлены с целыми коэффициентами. Докажите, что при некотором целом a [постройте a] все числа F1(a), F2(a), F3(a),…, Fn(a) составные.
Замечания по реализациии 9. Ввод ответа через виртуальную клавиатуру, включающую возможность использования функций – заданных конкретных многочленов.
Замечания по реализациии 10. Ввод ответа через виртуальную клавиатуру, включающую возможность использования конечных сумм, зависящих от n и общего члена последовательности Fn, который рассматривается как функция.
Параметризация 9. Параметризация осуществляется по числу многочленов n и коэффициентам многочленов.
Параметризация 10. Параметризация осуществляется по общим формулам коэффициентов многочленов.
Замечания по верификации ответа. Для введенного a, являющегося функцией значений многочленов, программа проверяет, являются ли все значения составными числами.
Вид 2. Составление алгоритмов решения математических задач.
Подвид 2-1. Задачи, решение которых описывается линейным алгоритмом.
Тип 11. Задача на геометрическое построение (линейный алгоритм построения циркулем и линейкой).
Пример задачи типа 11. В правильном треугольнике разместить треугольник с заданными углами так, чтобы он имел наибольшую площадь.
Замечания по реализации. Прототипом интерфейса может служить среда «The Geometer’s Sketchpad». Решающему предоставлена среда, имитирующая построения циркулем и линейкой.
Параметризация. Для генерации различных вариантов можно менять углы треугольника, который надо разместить в правильном треугольнике.
Замечания по верификации ответа. Можно использовать метод Монте-Карло. При этом, его надо применить так, чтобы уменьшить число генерируемых треугольников. (Например, выбирать точку на отрезке, затем выбирать угол, под которым проводить луч, на котором лежит вторая вершина, второй луч определиться автоматически и т.д.).
Подвид 2-2. Задачи, решение которых описывается ветвящимся алгоритмом. Комбинаторные задачи на перечисление, решение которых задается ветвящимся алгоритмом.
Тип 12. Задачи на взвешивания.
Пример задачи типа 12. Есть N чеканщиков. Некоторые из них изготовляют только фальшивые монеты, а другие – только настоящие. Вес фальшивой монеты отличен от веса настоящей. Имеются весы с полным набором гирь и одна заведомо настоящая монета. У каждого чеканщика можно взять сколь угодно монет. Как с помощью минимального количества взвешиваний (трех) определить всех фальшивомонетчиков.
Замечания по реализации. Решение задачи записывается в виде нескольких шагов – взвешиваний, на каждом из которых задается (указанием функции от n – номера чеканщика) число монет каждого чеканщика, участвующее во взвешивании, и ветвление, указывающее номер следующего шага в зависимости от результата взвешивания.
Параметризация. Естественная параметризация – от N – количества чеканщиков. Возможно введение различных ограничений (на число апробируемых монет, количество фальшивомонетчиков)
Замечания по верификации ответа. Алгоритм проверяется на множестве тестов – различных способах распределения чеканщиков (фальшивомонетчик или нет).
Подвид 2-3. Задачи, решение которых описывается рекурсивным алгоритмом. Рекурсивное описание конструкций из бесконечного числа элементов.
Тип 13. Геометрические конструкции с рекурсией.
Пример задачи типа 13. Разложением квадрата называется разбиение его на конечное число прямоугольников, стороны которых параллельны сторонам квадрата. Разложение называется примитивным, если оно не является разбиением более крупного разложения. (При каких n существует примитивное разложение квадрата на n прямоугольников). [Для n>6 построить рекурсивное описание разбиения].
Замечания по реализации. Решение должно описываться рекурсивным алгоритмом. Интерфейс геометрической рекурсии можно сделать аналогичным интерфейсу скриптов в «The Geometer’s Sketchpad. V. 2».
Параметризация. В этом сюжете прямая параметризация неочевидна. Можно поэкспериментировать с фигурами, составленными из прямоугольников. Возможно, это приведет к камуфлирующей параметризации.
Замечания по верификации ответа. Структура интерфейса ограничивает все решения только разбиением на прямоугольники со сторонами, параллельными сторонам квадрата. Проверять нужно только примитивность разбиения для различных значений n. Это, на первый взгляд, отнюдь не простая верификация.
Вид 3. Геометрическое конструирование.
Подвид 3-1. Конструирование геометрического инварианта.
Тип 14. Конструирование по заданному множеству подмножества (траектории) инвариантного, относительно формы исходного множества.
Пример задачи типа 14. В лесу, имеющем форму выпуклого многоугольника площади 1 кв. км, заблудился человек. Докажите, что он всегда может выйти из леса, пройдя путь, меньший 2507 м.
Указание. Для доказательства укажите траекторию движения, которая всегда приведет к выходу из леса независимо от его формы.
Замечания по реализации. Решением является полуокружность радиуса 2507/. Таким образом, для задания траектории удобен геометрический ввод с набором примитивов для описания кривых на плоскости.
Параметризация. Камуфлирующая параметризация возможна изменением площади леса и, соответственно, длины пути. Содержательная параметризация может быть связано с описание параметрического семейства областей, формы которых может иметь лес. Это может привести к изменению стратегии выхода и, соответственно, изменению длины кратчайшего пути. Для подтверждения достаточно рассмотреть лес в форме круга, прохождение которого можно сделать по любой прямой и расстояние при этом будет меньше, чем в задаче.
Замечания по верификации ответа. Траектория проверяется по двум признакам:
не превышает ли ее длина заданного значения,
на различных примерах областей на признак – содержится ли она в этой области.
Подвид 3-2. Конструирование минимаксного геометрического решения.
Тип 15. Минимаксное расположение геометрических фигур.
Пример задачи типа 15. В квадрат площади 5 поместить 9 многоугольников каждый площади 1 так, чтобы наибольшая площадь пересечения двух многоугольников была наименьшей.
Замечания по реализации. Среда реализации аналогична «The Geometer’s Sketchpad». Произвольные многоугольники площади 1 генерируются по числу сторон. Форма их меняется мышкой с сохранением площади. Далее, построенные многоугольники как твердые тела располагаются в заданном квадрате.
Параметризация. Можно менять параметры исходной области, ее площадь, число размещаемых фигур и их площадь. Можно добавлять ограничения на размещаемые фигуры (выпуклые, с заданным числом вершин, равные и пр.).
Замечания по верификации ответа. Проверяется попадание фигур внутрь заданной области. Вычисляется наибольшая площадь пересечения, которая сравнивается с эталонной (либо с той, которая получается случайным разбросом фигур внутри области). Если достигается эпсилон-равенство, задача принимается. Возможно, на последнем этапе следует запускать скрытую локальную оптимизацию и, если расположение фигур при этом принципиально не меняется, что можно проверять отношением зацепления между фигурами, то ответом считается минимакс после локальной оптимизации решения.
|
