20Числа и их свойства

Заключительная задача высокого уровня сложности — «олимпиадного» характера. Обычно состоит из трёх пунктов: (а) привести пример, удовлетворяющий условию; (б) показать, что некоторая величина не может принимать определённое значение (контрпример или доказательство невозможности); (в) найти наибольшее или наименьшее значение этой величины.

Что проверяется

• Свойства натуральных, целых и рациональных чисел.
• Делимость, признаки делимости на 3, 9, 11 и др., деление с остатком.
• Наибольший общий делитель, наименьшее общее кратное, взаимная простота.
• Методы доказательств: перебор, от противного, принцип Дирихле, инвариант.
• Умение приводить примеры и контрпримеры, строить доказательные рассуждения.

Типичные сюжеты

• Дана последовательность чисел с правилом построения. (а) Привести последовательность заданного вида; (б) доказать, что сумма не может равняться определённому числу; (в) найти наибольшую возможную сумму/произведение/длину.
• Набор чисел с определённым свойством (например, все делятся на предыдущее, или сумма каждых двух делится на 3). Исследовать, какие значения может принимать параметр набора.
• Дробь p/q, несократимая, с ограничениями — найти все возможные значения.
• Задача на разбиение натурального числа на слагаемые с дополнительными условиями.

Как оценивается

• 4 балла — все три пункта (а, б, в) обоснованы полностью.
• 3 балла — пункты (а) и (б) — верно и полностью; в (в) указан правильный ответ, но доказательство его наибольшести/наименьшести с пробелом.
• 2 балла — верно решены два из трёх пунктов.
• 1 балл — верно решён только пункт (а) — обычно самый простой.
• 0 баллов — решение не соответствует условию.

На что обратить внимание

Пункт (а) почти всегда можно «угадать» подбором — не пропускайте его. Пункт (б) — это именно доказательство: один пример не годится. Используйте остатки по модулю (обычно mod 3, 5, 9, 11), чётность, или принцип Дирихле. В пункте (в) сначала найдите ответ перебором на маленьких примерах, затем докажите его оптимальность: сверху — оценкой, снизу — примером. Эта задача требует времени — оставляйте на неё не меньше 40 минут и не начинайте её, пока не сделаны более «предсказуемые» задания.