Каникулярная школа для одаренных детей по математике


Т.А. Матукова, учитель математики МБОУ «Лицей города Юрги»
Юрга 2014
Программа каникулярной школы для одарённых детей по математике
Пояснительная записка.
Математические олимпиады и дистанционные конкурсы – прекрасный способ не только выявления, но и обучения одарённых детей. Чем чаще участвует ученик в подобного рода мероприятиях, тем больше он приобретает опыта, который играет не последнюю роль в достижении им хороших результатов. Олимпиады и конкурсы требуют от участников не только владения стандартными школьными приемами решения задач, но и смекалки, изобретательности, умения нестандартно мыслить и строго логически рассуждать, умения работать самостоятельно. При решении олимпиадных задач используются типичные методы научных исследований, такие, как полный перебор вариантов, переход от частного к общему, построение математических моделей на основе строгих логических рассуждений.Однако в реальных условиях учебного процесса практически отсутствует возможность преподавания математики с организацией серьезного творчества. Кроме того, проводимые олимпиады и конкурсы показывают, что у учащихся недостаточно навыков и умений, необходимых для успешного участия в таких мероприятиях. Поэтому дополнительное математическое образование для одаренных детей необходимо. Именно соединение классных и внеклассных форм математического творчества даст наибольшую результативность. Поэтому занятия в школе для одарённых детей позволят развить творческие способности обучающихся, проявляющих особый интерес в области математики.Цели данного курса:- развитие интеллекта и творческого потенциала,- обучение школьников методам и приемам решения олимпиадных задач,- формирование исследовательских навыков и умений,- повышение интереса школьников к решению нестандартных задач.Задачи:
Углубить и расширить знания в области математики
Подготовить к предметным олимпиадам по математике
Сформировать устойчивую положительную мотивацию к изучению математики
Курс рассчитан на учеников 8-11 классов, которые объединяются в группы в количестве 10-15 человек. Занятия проходят в каникулярное время. Проводят занятия преподаватели математики лицея. Предлагаемая форма проведения занятий – лекционно-семинарская (при постоянном активном участии школьников, во взаимно активном диалоге). Учащиеся знакомятся с новыми типами задач, новыми взглядами на ранее известное, учатся использовать новые методы при решении нестандартных задач. Часть материала курса можно преподнести в проблемном стиле, предлагая учащимся обдумать, каким методом решить ту или иную задачу.
Выделены три темы для изучения:
Математические игры. Стратегии.
Игровые задачи являются одним из самых мощных инструментов развития человеческого интеллекта. Человеку в течение всей жизни приходится не один раз оказываться в затруднительном положении, выход их которого можно найти с помощью логических рассуждений. А способность логически мыслить, и отрабатывается на решении нестандартных занимательных задач, при решении которых развивается интеллект человека. Эти задачи проверяют не знания, а умение логически рассуждать, ориентироваться в необычных ситуациях, предвидеть и действовать.Чтобы успешно решать задачи такого вида, надо уметь выделять их общие признаки, подмечать закономерности, выдвигать гипотезы, проверять их, строить цепочки рассуждений, делать выводы. Игровые задачи от обычных отличаются тем, что не требуют вычислений, а решаются с помощью рассуждений. Теория игр — это раздел прикладной математики, точнее — исследования операций. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках — социологии, политологии, психологии, этике и других. Задача, связанная с теорией игр, включена в ЕГЭ по информатике.
Теория чисел.
Теория чисел — это раздел математики, изучающий свойства чисел. В школьном курсе математики теория чисел изучается в младших классах, в старших классах подобные задачи встречаются, в основном, в заданиях олимпиады. Кроме этого, являются основой для выполнения самой сложной задачи ЕГЭ по математике – С6. Такие задачи имеют нестандартный характер и рассчитаны на людей с интуицией и логическим мышлением. При изучении данной темы можно показать, как простые понятия могут быть использованы при решении сложных задач. Кроме этого, познакомить с более сложной темой – «Сравнения», выходящей за рамки школьной программы.
Инварианты и раскраски.
Инвариант в математике — это свойство некоторого класса (множества) математических объектов оставаться неизменными при преобразованиях определённого типа. Нахождение нужного инварианта – это часто основная идея доказательства невозможности достижения чего-либо. Такие задачи часто можно выделить даже по самому условию: обычно речь в них идёт о каких-либо позициях, действиях и т.д. Эти задачи оказываются очень сложны уже тем, что инвариант бывает достаточно трудно найти. Поэтому необходима практика решения таких задач, развитие математической интуиции. Обучающиеся должны понять, насколько понятие инварианта может оказаться полезным.

Программа занятий рассчитана на 18 часов.

Содержание программы
Математические игры. Стратегии (6 ч)
Понятие математической игры. Принцип дополнения и принцип симметрии. Классификация позиций. Выигрышные стратегии. Изоморфизм игр. Понятие бесконечной игры и игры с неполной информацией.
Теория чисел (6 ч)
Делимость. НОД и НОК. Алгоритм Евклида. Решение уравнений в целых числах. Десятичная запись числа. Сравнения.
Инварианты и раскраски (6 ч)
Чётность суммы чисел. Применение делимости. Вспомогательные раскраски на клетчатых досках. Раскраска куба. Раскраска плоскости.
Список литературы
Формирование универсальных учебных действий в основной школе: от действия к мысли. Система заданий: пособие для учителя / [ А.Г. Асмолов, Г.В. Бурменская, И.А. Володарская и др.]; под ред. А.Г. Асмолова. – 2-е изд. – М.: Просвещение, 2011. – 159 с.
Фундаментальное ядро содержания общего образования / Рос. акад. образования; под ред. В.В. Козлова, А.М. Кондакова. – 4-е изд., дораб. – М.: Просвещение, 2011. – 79 с. – (Стандарты второго поколения).


Т.А. Матукова, учитель математики МБОУ «Лицей города Юрги»
Юрга 2014
Пособие для каникулярной школы по математике
Математические игры. Стратегии.
Под понятием математической игры мы понимаем игру двух соперников, обладающую следующим свойством. В каждый момент игры состояние характеризуется позицией, которая может изменяться только в зависимости от ходов игроков. Некоторые позиции являются выигрышными для одного из игроков. Добиться выигрышной для себя позиции и есть цель каждого. Иногда игры допускают ничью. Это означает, что ни один из игроков не может добиться выигрышной для себя позиции, или некоторые позиции объявляются ничейными.
Например, шахматы, шашки, крестики-нолики являются математическими играми. А игра в кости (домино), большинство карточных игр математическими не являются, так как состояние игры зависит не только от ходов соперника, но и от расклада.
В математических играх существуют понятия выигрышной стратегии, то есть набора правил (можно сказать, инструкции или алгоритма), следуя которым, один из игроков обязательно выиграет (не зависимо от того, как играет его соперник) и ничейной стратегии, следуя которой один из игроков обязательно добьётся либо выигрыша, либо ничьей.
В любой математической игре существует либо выигрышная стратегия для одного из игроков, либо ничейные стратегии для обоих (если игра допускает ничью). В зависимости от этого игра называется выигрышной для первого или второго игрока, или ничейной.
Например, крестики-нолики (на доске 3х3) являются ничейной игрой. К какому из перечисленных случаев относятся шахматы и шашки, неизвестно. Хотя стратегия (либо выигрышная, либо ничейная) в этих играх существует, она не найдена, поэтому соревнования по этим играм пока представляют интерес.
В задачах обычно задается один и тот же вопрос: кто из двух игроков выиграет при правильной игре? Слова «правильная игра» означают, что если у кого-то из игроков есть стратегия, позволяющая выигрывать при любых ходах другого игрока, то он не делает "глупых" ходов, а стремится выиграть и следует своей выигрышной стратегии. В каждой задаче необходимо придумать такую стратегию для одного из игроков.
В играх чаще всего используются 2 принципа – принцип дополнения и принцип симметрии. Ещё один сильный метод - метод выигрышных позиций.
Принцип дополнения и принцип симметрии
Пример. Играют двое. Игра начинается с числа 0. За ход разрешается прибавить к имеющемуся числу любое натуральное число от 1 до 9. Выигрывает тот, кто получит число 100.

Задача 1.
На столе лежит 25 спичек. Играющие по очереди могут взять от одной до четырёх спичек. Кто не может сделать ход (спичек не осталось), проигрывает. Кто выигрывает при правильной стратегии? А что будет, если изначально не 25 спичек, а 24?
Решение:
В этой игре второй игрок может гарантировать себе выигрыш. Для этого он должен дополнять ход первого до пяти спичек (если первый взял одну, второй берёт четыре и т. п.). Тогда после хода второго сначала останется 20 спичек, затем 15, затем 10, 5 и, наконец, 0, первый проиграл.
Если 24 спички, то выигрывает первый: он должен взять четыре спички, останется 20, а затем дополнять ход противника до 5 спичек.
Легко понять, что будет в общем случае для N спичек. Если N делится на 5 без остатка, то второй может гарантировать себе выигрыш, дополняя ход противника до 5. Если же N не делится на 5 без остатка, то выигрывает первый. Он должен сначала взять столько спичек, каков остаток, а потом дополнять ход противника до 5.
Задача 2.
Двое игроков кладут одинаковые круглые монеты на прямоугольный лист бумаги; монеты могут выходить за край, но не могут перекрываться. Кто не может положить монету, проигрывает. (Сдвигать ранее положенные монеты нельзя.). Кто выигрывает при правильной стратегии?
Решение:
В этой игре первый игрок может выиграть, положив свою монету в центр листа, а затем повторяя ходы второго симметрично относительно центра. (Симметрия относительно точки - поворот вокруг неё на 180 градусов.) Если второму игроку удалось положить монету на пустое место, то есть и пустое симметричное место, куда тоже можно положить монету. И так далее.
Это рассуждение кажется совсем простым, но в нём есть тонкий момент. Представим себе, что кто-то объясняет нам, что в этой игре есть выигрышная стратегия не для первого, а для второго. И состоит она в том, что второй должен класть монеты симметрично ходам первого (относительно центра листа). Что в этих объяснениях неверно?
Дело в том, что симметричное положение монеты может перекрываться с исходным, и уже положенная монета может мешать положить симметричную.
Задача 3.
На столе лежат две кучки спичек: в одной 10, в другой - 7. Игроки ходят по очереди. За один ход можно взять любое число спичек (1; 2; 3; ... ) из одной из кучек (по выбору игрока). Кто не может сделать ход (спичек не осталось), проигрывает. Кто выигрывает при правильной стратегии?
Решение:
Здесь первый игрок может гарантировать выигрыш, если сначала уравняет кучки, взяв три спички из большей. После этого он должен повторять ходы второго, но брать из другой кучки, восстанавливая нарушенное равенство.
Задача 4.
В строчку написано несколько минусов. Два игрока по очереди переправляют один или два соседних минуса на плюс; выигрывает переправивший последний минус. Кто выигрывает при правильной игре: начинающий или его партнёр? А если минусы написаны по кругу?
Решение:
В этой игре выигрывает первый игрок, независимо от числа минусов в строке. Для этого он должен переправить на плюс средний минус (если минусов нечётное число и средний есть) или два средних минуса (если минусов чётное число). После этого игра разбивается на две независимые части, и остаётся лишь повторять ходы противника в другой части, поддерживая симметрию. Если минусы написаны по кругу и их не два, то выигрывает второй, так как первый своим ходом приводит игру к предыдущей и второй становится первым. Если минусов не более двух, то первый исправляет все и выигрывает.
Задача 5 (муниципальный этап олимпиады, 2012)
Жираф и Жирафиха играют в следующую игру. Они по очереди стирают буквы во фразе «ДЛИННОШЕЕЕ ЖИВОТНОЕ». За один ход стирается либо только одна буква, либо одна буква и все такие же буквы, остающиеся к этому моменту нестёртыми. Выигрывает тот, кто сотрёт последнюю букву. Начинает Жираф. Кто выигрывает при правильной игре?
Решение:
Если пока не рассматривать четыре буквы «Е» и две буквы «И», остальные буквы можно расположить следующим образом: ДЖШООО / НННЛТВ. К выписанным буквам второй игрок может применить симметричную стратегию: стирать буквы, симметричные тем (относительно середины), которые только что стёр первый игрок.
Опишем, как должен поступать второй игрок с буквами «Е» и «И», чтобы выиграть.
Если первый игрок на каком-то шаге полностью стёр одну из групп (все буквы «Е» или «И»), то второй игрок стирает полностью оставшуюся из указанных групп, а к остальным буквам применяет симметричную стратегию, как было указано выше.
Если первый игрок стёр одну одну букву «Е»,второй стирает тоже одну букву «Е». тогда оставшиеся буквы «Е» и «И» образуют симметричную конструкцию ЕЕ / ИИ, к которой второй игрок применяет симметричную стратегию.
Если первый игрок стёр одну букву «И», второй стирает одну букву «Е». Если в дальнейшем первый игрок стирает ещё одну букву «Е», второй стирает тоже «Е» и приходит опять к симметричной конструкции Е / И.
Таким образом, выигрывает игрок, который ходит вторым – Жирафиха.
Классификация позиций
Назовем позицию выигрышной, если, начиная из неё, игрок выигрывает при правильной игре. Назовем позицию проигрышной, если, начиная из неё, игрок проигрывает при правильной игре противника при любой своей стратегии. Позиция невыигрышна, если и только если она проигрышна. Это нужно для анализа игр с конца. Решение задачи методом выигрышных позиций разбивается на две части:
Определение выигрышности / проигрышности конечной позиции.
«Обратный ход» с использованием следующих двух тезисов:
Если из данной позиции достижимы только выигрышные позиции, то данная позиция является проигрышной;
Если из данной позиции достижима хотя бы одна проигрышная позиция, то данная позиция является выигрышной.
После этого нужно посмотреть тип начальной позиции. Если она выигрышна, то выигрывает первый игрок со стратегией: «Хожу в проигрышные позиции». Если она проигрышна, то выигрывает второй игрок, так как любой ход первого приводит в выигрышную позицию, начиная с которой, второй игрок может использовать стратегию «Хожу в проигрышные позиции». Помните: после хода текущий игрок меняется.
Задача 1.
На клетчатой бумаге нарисован прямоугольник 5x9. В левом нижнем углу стоит фишка. Коля и Серёжа по очереди передвигают ее на любое количество клеток либо вправо, либо вверх. Первым ходит Коля. Выигрывает тот, кто поставит фишку в правый верхний. Кто выигрывает при правильной игре?
Решение:
Вопрос на понимание: «В данной игре правая верхняя (конечная) клетка - выигрышная или проигрышная?» Ответ: проигрышная, так как если игрок начинает из неё, то предыдущий игрок уже выиграл. Это нужно для анализа игр с конца. Нетрудно описать выигрышные и проигрышные позиции данной игры.
В В В В В В В В П(конец)
В В В В В В В ПВ
В В В В В В ПВ В
В В В В В ПВ В В
В(начало) В В В ПВ В В В
Таким образом, победит первый игрок, каждый раз помещая фишку в проигрышную позицию.
Ответ: Выигрывает первый (Коля), стратегия: «Ставить на проигрышную позицию».
Задача 2. На столе лежит 25 спичек. Играющие по очереди могут взять от одной до четырёх спичек. Кто не может сделать ход (спичек не осталось), проигрывает. Какой игрок выигрывает при правильной игре?
Решение:
Решая эту задачу в прошлый раз, мы использовали принцип дополнения. Теперь посмотрим на позиции. В качестве позиций выступают количества спичек на столе.
0 – проигрышная позиция (конченая)
1,2,3,4 - выигрышные
5 – проигрышная
И т.д. Легко видеть, что любое число спичек, которое делится на 5, есть проигрышная позиция. Отсюда и стратегия видна: ходить в проигрышные позиции. Иными словами – дополнять до кратного пяти.
Задача 3.
Шахматный король стоит в левом нижнем углу шахматной доски. Участвуют два игрока, которые ходят по очереди. За один ход его можно передвинуть на одно поле вправо, на одно поле вверх или на одно поле по диагонали "вправо-вверх". Выигрывает игрок, который поставит короля в правый верхний угол доски. Кто выиграет при правильной игре и как ему для этого надо действовать?
Решение: нетрудно описать выигрышные и проигрышные позиции данной игры.
В ПВ ПВ ПВ П (конец)
В В В В В В В В
В ПВ ПВ ПВ ПВ В В В В В В В
В ПВ ПВ ПВ ПВ В В В В В В В
В ПВ ПВ ПВ ПВ (начало) В В В В В В В
Таким образом, победит первый игрок, каждый раз помещая фишку в проигрышную позицию.
Есть и более простой способ, который виден по таблице: «Первый ход первый игрок делает по диагонали, а далее повторяет ходы противника.» Эта стратегия дает, что только на ходах первого игрока обе координаты текущей клетки будут четными.
Задача 4.
Двое играют в двойные шахматы: все фигуры ходят как обычно, но каждый делает по два шахматных хода подряд. Докажите, что первый может как минимум сделать ничью (либо просто бесконечную партию).
Решение:
Если бы первый этого не смог сделать, то для второго существовала бы строго выигрышная стратегия, но первый, сделав два ходя конем, может стать вторым, что есть противоречие. Это верно для любой игры, где первый может пропустить ход и занять позицию второго игрока.
Задача 5.
На доске написано число 60. За один ход разрешается уменьшить число на любой из его целых положительных делителей (в том числе на единицу или на само это число). Если при этом получается нуль, игрок проиграл.
(Указание. Начав составлять таблицу выигрышных и проигрышных позиций, легко угадать закономерность и доказать её.)Решение:
Разбор первых нескольких чисел наводит на мысль, что все четные позиции выигрышные, а нечетные проигрышные. Доказательство индукцией: из нечетных позиций можно попасть только в четные, ибо все делители нечетного числа нечетны. Из четной позиции можно попасть в нечетную, отняв единицу. Далее - предположение индукции.
Задача 6.
Двое играют в такую игру. Первый называет любое натуральное число от 2 до 9, второй умножает его на любое натуральное число от 2 до 9, первый умножает результат на любое натуральное число от 2 до 9 и т. д. Выигрывает тот, у кого впервые получится число больше 1000.
Решение:
Опишем выигрышные и проигрышные позиции: ясно, что, начиная с 1001 идут проигрышные. Далее В: 112-1000, П: 56-111, В: 55 - 7, П: 6-2. Поэтому первому надо называть число от 2 до 6 и уходить в проигрышные позиции. Выигрывает первый.
Задача 7.
Часы показывают полдень. Двое играющих по очереди переводят часовую стрелку на два или три часа вперёд. Если после хода игрока стрелка указывает на 6, он выиграл.
Решение:
Выиграет первый. Первый ходит на 2 часа. Второй не может пойти на 4 (сразу проиграет), поэтому идет на 5. Первый идет на 8. Второй - либо на 10, либо на 11. Первый - на 1. Второй на 3 или на 4. Первый на 6. Здесь есть тонкий момент. При разборе выигрышный и проигрышных состояний, может возникать зацикливание, поэтому лучше решать непосредственно.
Задача 8.
На квадратную доску 8 × 8 двое по очереди ставят коней на поля, не находящиеся под боем ранее поставленных (все равно кем) коней. Кто выигрывает при правильной игре?
Решение:
Второй игрок выиграет, если будет ставить коней симметрично относительно центра доски. Другими словами, позиции, в которых кони делятся на пары симметричных, являются проигрышными. Если в такой позиции игрок ставит коня на пустое место, то и симметричное ему место пусто. Более того, если поставленный конь не попал под бой, то и симметричный под бой не попадёт. Последнее утверждение основано на том, что конь не может побить клетку, симметричную той, где он стоит (хотя бы потому, что она того же цвета, а конь бьёт только клетки другого цвета). В этой задаче можно вместо центральной симметрии использовать осевую (относительно средней линии доски).
В разобранных примерах мы следовали таким правилам:
если из позиции х можно попасть в проигрышную, то позиция х – выигрышная;
если все ходы из позиции х ведут в выигрышные позиции, то позиция х – проигрышная;
выигрышная стратегия: ставить противника в проигрышную позицию.
Изоморфизм игр
Научное слово «изоморфизм» означает, что две с виду разные игры по существу одинаковы (изоморфны). Приведём несколько примеров.

Задача 1.
Имеются фишки с цифрами 1; 2; 3; 4; 5; 6; 7; 8; 9 (как в игре «лото»). Два игрока по очереди берут фишки (за каждый ход по одной фишке). Выигрывает тот игрок, который первым соберёт у себя три фишки с суммой 15. (Если ни у одного игрока таких фишек не будет, фиксируется ничья.) Может ли один из игроков обеспечить себе победу? ничью?
Решение: чтобы установить нужный изоморфизм, вспомним популярный сюжет из книг по «занимательной математике» - магические квадраты. Числа от 1 до 9 можно расставить в квадрате 3х3так, чтобы сумма в каждой строке, каждом столбце и по каждой из двух диагоналей равнялась 15:
4 9 2
3 5 7
8 1 6
Других комбинаций из трёх чисел с суммой 15 (кроме горизонталей, вертикалей и диагоналей) не бывает. Теперь уже понятно, что если мы будем отмечать взятые первым игроком фишки крестиками в этой таблице, а фишки второго игрока отмечать ноликами, то игра превратится в обычные крестики-нолики. Игроки по очереди ставят свои знаки (на языке фишек - берут фишки), а выигрывает тот, кто первым наберёт три фишки с суммой 15 (поставит три своих знака в один ряд). Любители крестиков-ноликов знают, что обе стороны при правильной игре могут гарантировать себе как минимум ничью.
Задача 2.
На 9 карточках написаны слова: рыба, клин, нить, небо, сок, бусы, рот, сеть, река. Двое по очереди берут со стола карточки, и выигрывает тот, у кого первого окажутся три слова, имеющие общую букву.
Решение: Данная игра изоморфна крестикам-ноликам. Составим таблицу:
сок клин река
бусы небо рыба
сеть нить рот
Любые 3 слова, стоящие в одной строке, одном столбце или на одной большой диагонали таблицы, имеют общую букву, в то же время у других троек слов общих букв нет.
Теория чисел
Делимость
Признаки делимости
Признак делимости на 2. Число делится на 2, если его последняя цифра - ноль или делится на 2. Числа, делящиеся на два, называются чётными, не делящиеся на два – нечётными.Признак делимости на 4. Число делится на 4, если две его последние цифры - нули или образуют число, которое делится на 4.
Признак делимости на 7. Число делится на 7 тогда и только тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7.
Признак делимости на 8. Число делится на 8, если три его последние цифры - нули или образуют число, которое делится на 8.
Признаки делимости на 3 и 9. Число делится на 3, если его сумма цифр делится на 3. Число делится на 9, если его сумма цифр делится на 9.
Признак делимости на 5. Число делится на 5, если его последняя цифра - ноль или 5.
Признак делимости на 25. Число делится на 25, если две его последние цифры - нули или образуют число, которое делится на 25.
Признак делимости на 11. На 11 делятся только те числа, у которых сумма цифр, стоящих на нечётных местах, либо равна сумме цифр, стоящих на чётных местах, либо отличается от неё на число, делящееся на 11.
Теоремы о делимостиТеорема 1. Если оба числа а и b делятся на m, то и их сумма а+b и их разность а-b делятся на m.
Следствие 1. Если сумма нескольких слагаемых делится на m и известно, что все слагаемые, кроме одного, делятся на m, то и оставшееся слагаемое также делится на m.
Теорема 2. Если а делится на m и b делится на n, то ab делится на mn.
Следствие 1. Если а делится на m, то аn делится на mn (здесь n — любое натуральное число).
Следствие 2. Если хотя бы один из множителей делится на m, то и произведение делится на m.
Деление с остатком
Определение. Пусть а и b — два целых числа, причем b>0. Если число а можно записать в виде где a=bq+r, где 0≤r<b, то говорят, что а дает при делении на b частное q и остаток r.
Задача 1.
Даны два трехзначных числа, причем ни одно из них не делится на 37, а сумма их делится на 37. Приписав одно из чисел к другому, получаем некоторое шестизначное число. Докажите, что оно делится на 37.
Решение. Пусть abc и def - данные числа. Тогда abcdef = 1000abc + def = 999abc + abc + def = 37 ∙ 27abc + (abc + def).
Задача 2.
Найти все такие а ∈ N, что 2a+1a-2 - целое число.
Выделим целую часть
2a+1a-2=2+ 5a-2 .
Чтобы это число было целым, необходимо и достаточно, чтобы второе слагаемое было целым, то есть 5 должно делиться на (а-2). У числа 5 есть всего два натуральных делителя — это 1 и 5. Делителю 1 соответствует решение а = 3, а делителю 5 — решение а = 7.
У числа 5 есть еще два отрицательных делителя, необходимо проверить еще и делители -1 и -5. В первом случае получаем, что а = 1 является решением, а во втором a = -3 решением не является.
Ответ: 1, 3, 7.
Задача 3.
Найти цифру X, при которой число 5X793X4 делится нацело на 3.
Решение. Воспользуемся признаком делимости на 3:
5 + X +7 + 9 + 3 + X +4 = 2X +28 = 2(X + 14) ⋮ 3.
Непосредственной подстановкой вместо X цифр 0, 1, ... 9 получаем, что при X = 1, 4, 7 указанное число делится нацело на 3.
Ответ: 1,4,7
Задача 4.
Остаток от деления некоторого натурального числа и на 6 равен 4, остаток от деления на 15 равен 7. Чему равен остаток от деления числа на 30?
Решение. По условию
n=6k+4, n=15m+7 ⟺ 5n=30k+20,4n=60m+28 ⇒n=30k-2m- 8=30k-2m-1+ 22=30l+22.Ответ: 22.
Задача 5.
Доказать, что сумма квадратов двух последовательных целых чисел при делении на 4 дает в остатке 1 .
Решение. Пусть m — произвольное целое число. Тогда
m2 +(m +1)2 = 2 m 2+m+1 = 2mm + 1+ 1.
Первое слагаемое содержит произведение двух последовательных целых чисел т(т +1), которое, как известно, всегда делится на 2. Следовательно, первое слагаемое делится нацело на 4 и при этом остаток равен 1.
НОД и НОК
Наибольший общий делитель
Определение. Наибольшее натуральное число, являющееся общим делителем чисел а и b, называется наибольшим общим делителем чисел а и b и обозначается, как НОД(а, b).
Теорема 1. Пусть m иn- два целых числа, хотя бы одно из которых отлично от нуля, и d = НОД(m,n) - их наибольший обилий делитель. Тогда существуют такие целые числа xQ и у0, что mx0+ny0 = d.
Теорема 2. Пусть m и n — два целых числа, хотя бы одно из которых отлично от нуля, и d = НОД(m,n) - их наибольший общий делитель. Число с в том, и только в том случае является общим делителем чисел m и n, если оно является делителем числа d.
Лемма. Пусть а и b —натуральные числа и r - остаток от деления а на b. Тогда наибольший общий делитель чисел а и b равен наибольшему общему делителю чисел b и r, т.е. НОД(a,b) = НОД(b,r).
Алгоритм Евклида. Даны два натуральных числа a, b, причем а>b. Разделив а на b с остатком, получим:
а = q1b + r1.
Теперь, разделив b на r1 с остатком, получим:
b = q2r1 + r2.
Разделив далее r1 на r2 с остатком, найдем:
r1 = q3r2 + r3.
и т. д. В результате мы получим убывающую последовательность натуральных чисел а > b > r1 > r2 > r3... Т.к. натуральных чисел, меньших, чем а, имеется лишь конечное число, то на каком-то шаге эта последовательность убывающих чисел оборвется, т. е. какое-то rk-1 разделится на rk без остатка. Следовательно, rk и будет наибольшим общим делителем чисел rk-1 и rk т. е. (rk-1,rk) = rk. Но в силу доказанной леммы мы имеем:
НОД(а, b) = НОД(b, r1) = НОД(r1, r2) = НОД(r2, r3) =...= НОД(rk-1, rk).
Значит, НОД(a, b) = НОД(rk-1,rk) = rk. Таким образом, если мы будем шаг за шагом проводить указанным способом деление с остатком, то последний отличный от нуля остаток и будет наибольшим общим делителем чисел а и b.
Построенная последовательность называется последовательностью Евклида.
Задача 1.
Найдите НОД(42598, 2014).
1156970425450Решение. C помощью алгоритма Евклида найдём НОД(42598, 2014). Последовательные деления с остатком удобно проводить по следующей схеме:
Получили: НОД(42598, 2014) = 38.
Ответ: 38.
Задача 2.
Сократите дробь 2112030720 .
Решение. НОД(21120, 30720) = 1920, следовательно 2112030720=1116Ответ: 1116 .
Задача 3.
Докажите, что НОД(a,b) = НОД(5a + 3b, 13a + 8b).
Решение. Алгоритм Евклида:
13a+8b=5a+3b∙2+3a+2b,5a+3b=3a+2b∙1+2a+b,3a+2b=2a+b∙1+a+b,2a+b=a+b∙1+a,a+b=a∙1+b. ⇒ НОД(a,b) = НОД(5a + 3b, 13a + 8b).
Наименьшее общее кратное
Определение. Наименьшее натуральное число, являющееся общим кратным чисел а и b, называется наименьшим общим кратным чисел а и b и обозначается, как НОК(а, b).
Теорема. Для любых двух натуральных чисел а, b произведение их наибольшего общего делителя на их наименьшее общее кратное равно произведению самих чисел.
НОД(a, b)∙ НОК(a, b) = ab.
Следствие 1. Наименьшее общее кратное двух натуральных чисел а, b можно находить по формуле:
НОК(a, b) = abНОД(a, b)Следствие 2. Пусть а и b — два натуральных числа n0=НОК(а,b) - их наименьшее общее кратное. Натуральное число n в том и только в том случае является общим кратным чисел а и b, если оно является кратным числа n0.
Задача 1.
Найдите НОК(462,252,91).
Решение. Найдем сначала НОК(462,252), для этого найдем НОД(462,252):
462 = 252 ∙ 1 + 210,
252 = 210 ∙ 1 + 42,
210 = 42 ∙ 5.
Следовательно, НОД(462, 252) = 42 , а значит,
НОК(462, 252) = 462 ∙25242 = 2772.Найдем теперь НОК(2772, 91):2772 = 91 ∙ 30 + 42,
91 = 42 ∙ 2 + 7,
42 = 7 ∙ 6.
Следовательно, НОД (2772,91) = 7 , а значит,НОК(2772,91) = 2772 ∙ 917= 36036.Итак, НОК(462,252,91) = 36036.Ответ: 36036.Задача 2.
Сложите дроби 7192 и 1871620 .
Решение.
1620 = 192 ∙ 8 + 84,
192 = 84 ∙ 2 + 24,
84 = 24 ∙ 3 + 12,
24 = 12 ∙ 2.
Итак,
НОД(192, 1620) = 12, НОК(192, 1620) = 25920.
Тогда 7192 + 1871620 = 7 ∙135+187 ∙1625920=393725920 . Эта дробь несократима.
Ответ: 393725920 .
Задача 3.
Найдите натуральные числа а и b, если известно, что они не делятся друг на друга и НОД(а, b) = 6 , НОК(а , b) = 90 .
Решение.
а ∙ b = НОД(а , b) ∙ HOK(a, b),
поэтому а ∙ b = 6 ∙ 90 = 540. Но а = 6т , b = 6n , поэтому 36 ∙ т ∙ n = 540, или т ∙ n = 15 . С учетом симметрии возможны два случая:
1) т = 1, n = 15; 2) т = 3 , n = 5.
Первый случай невозможен, т.к. одно из чисел будет делиться на другое. Во втором случае получаются числа 18 и 30.
Ответ: (18,30), (30,18).
Решение уравнений в целых числах
Определение. Уравнение вида f(х,у,...) = 0, переменные в котором считаются целочисленными, называется уравнением в целых числах, или диофантовым уравнением.
Уравнение вида
аx +bу=сназывается линейным диофантовым уравнением. Очевидно, что такое уравнение имеет решения в целых числах только тогда, когда с : (а, b). Однако верно и обратное утверждение: если с : (а, b), то уравнение имеет целочисленные решения. В этом случае можно разделить оба коэффициента и свободный член уравнения на (а, b) и решать полученное, более простое уравнение.
Если пара чисел (x0; у0) является решением такого уравнения, то все его решения можно получить по формулам
x= x0+ k∙ ba,b,y= y0 – k∙ aa,b k ∈ZОбычно указанную пару решений находят подбором, подставляя вместо одной переменной остатки от деления на коэффициент при другой.
Задача 1.
Решить уравнение 3x-4y = 1 в целых числах
Решение. Перепишем уравнение в виде 3x = 4у +1. Поскольку левая часть уравнения делится на 3, то должна делиться на 3 и правая часть. Рассмотрим три случая
Если у = Зm, где m∈Z , то 4у + 1 = 12т + 1 не делится на 3.
Если у = 3m + 1, то 4y + 1 = 4(3m + 1) + 1 = 12m + 5 не делится на 3.
Если y = 3m + 2, то 4у + 1 = 4(Зm + 2) + 1 = 12m + 9 делится на 3, поэтому Зx = 12m + 9 => x = 4т + 3, откуда следует
x=4m+3,y=3m+2, где m∈Z-произвольное.Ответ: x=4m+3,y=3m+2, где m∈Z-произвольное.Задача 2.
Найдите решения в целых числах уравнения Зx + 6у = 22
Решение. Так как НОД(3, 6) = 3 и 22 не делится на 3, то уравнение не имеет целочисленных решений.
Ответ: уравнение не имеет целочисленных решений.
Задача 3.
Найдите решения в целых числах уравнения 7x + 11y = 13
Решение.
11 = 7 ∙ 1 + 4,
7 = 4 ∙ 1 + 3,
4 = 3 ∙ 1 + 1.
1 = 4 - 3 = 4 - (7 - 4) = 2 ∙ 4 - 7 = 2(11 - 7) - 7 = 2 ∙ 11 – 3 ∙ 7,
7 ∙ (-3) + 11 ∙ 2 = 1, отсюда 7 ∙ (-39) + 11 ∙ 26 = 13.
Частное решение: (х0 ; y0) = (-39; 26).
Общее решение:
x= -39-11t,y=26+7t, где t∈Z.Задача 4.
Найдите все натуральные числа а и b, удовлетворяющие уравнению 200а + 3b = 2003 .
Решение. Так как НОД(200, 3) = 1 , уравнение разрешимо в целых числах. Подбором находим частное решение: (a0 ; b0) = (10; 1) .
Тогда общее решение: a=10-3t,b=1+200t, где t∈Z. В силу того, что необходимо найти натуральные числа а и b, удовлетворяющие уравнению 200а + 3b = 2003, получаем систему неравенств:
10-3t>0,1+200t>0; ⟺ t< 103,t> - 1200 .Так как t∈Z, то системе неравенств удовлетворяют только четыре значения t: t1 = 0 , t2 = 1, t3 = 2 и t4 = 3 . При t1 = 0 получаем решение (a1;b1) = (10;1). При t2 = 1 получаем решение (a2;b2) = (7;201). При t3 = 2 получаем решение (a3;b3) = (4;401). При t4 = 3 получаем решение (a4;b4) = (1;601).
Ответ: (10;1), (7;201), (4;401), (1;601).
Задача 5.
Выясните, сколькими способами и как можно разменять 20 копеек монетами по 2 и 3 копейки.
Решение. Пусть x — количество монет по 2 копейки, у - количество монет по 3 копейки. Условие задачи приводит к уравнению 2x + 3у = 20 , причем х ≥ 0, у ≥ 0. Одним из решений этого уравнения является (x0;y0) = (-20; 20). Все решения находятся по формулам:
x= -20-3t,y=20+2t, где t∈Z. При этом -20-3t≥0,20+2t ≥0.
Значит, -10 ≤ t ≤ -7 , т.е. t = -10,-9,-8,-7, и поэтому возможны лишь четыре способа размена, которые осуществляются согласно найденным значениям t.
При t = -10: (х; у) = (10; 0); при t = -9: (x; у) = (7; 2); при t = -8: (x; у) = (4; 4); при t = -7: (x; у) = (1; 6).
Ответ: (10; 0), (7; 2), (4; 4), (1; 6).
Десятичная запись числа
Всякое натуральное число N единственным образом представимо в виде
N = an ∙ 10n + an-1 ∙ 10n-1 + an-2 ∙ 10n-2 + … + a2 ∙ 102 + a1 ∙ 101 + a0,
где n — натуральное число или 0, an, an-1, an-2, …, a2, a1, а0 — цифры от 0 до 9, причем цифра аn ≠ 0.
Это представление натурального числа в десятичной системе счисления называют десятичной записью числа. Для краткости мы будем записывать это (n + 1)-значное число в виде:
N = anan-1an-2…a2a1a0 (черта, как правило, ставится, чтобы отличить десятичную запись числа от произведения цифр an, an-1, an-2, …, a2, a1, а0).
Натуральное число M является n-значным в том и только в том случае, когда оно удовлетворяет неравенству 10n-1 ≤ М < 10n.
Всякая правильная дробь mn представима в виде конечной десятичной дроби или бесконечной периодической десятичной дроби. Дробь называется чисто периодической, если ее период начинается сразу после запятой, отделяющей целую и дробную часть числа.
Несократимая правильная дробь mn представляется в виде конечной десятичной дроби в том и только в том случае, когда ее знаменатель n не делится на простые числа, отличные от 2, 5.
Задача 1.
В примере на умножение двузначных чисел одинаковые цифры заменили одинаковыми буквами, а разные цифры — разными. Докажите, что при вычислении была допущена ошибка: ab ∙ cd = eeff.
Решение. Равенство невозможно, потому что для различных цифр a, b, c и d левая часть ab ∙ cd не делится на 11, а правая часть
eeff = 1000e + 100e + 10f + f = 1100e + 11f = 11 - (100е + f) - делится.
Задача 2.
Найдите все двузначные числа, которые равны сумме цифры десятков и квадрата цифры, стоящей в разряде единиц.
Решение. Из уравнения ab = a + b2 следует, что
10 a+b=a+ b29a = b(b - 1),
откуда а = 8, b = 9.
Ответ: 89.
Задача 3.
Может ли произведение всех цифр десятичной записи натурального числа равняться 2010?
Решение. 2010 = 2 ∙ 3 ∙ 5 ∙ 67, а простое число 67 нельзя представить в виде произведения цифр.
Ответ: не может.
Задача 4.
Докажите, что десятичная запись числа 2300 содержит более 90, но не более 100 цифр.
Решение. 2300 = 8100 < 10100, поэтому 2300 имеет не более 100 цифр. С другой стороны, 2300 = 102430 > 100030 = 1090, откуда следует, что 2300 имеет более 90 цифр.
Задача 5.
Пусть а и b — натуральные трехзначные числа, причем а ≠ b. Из них составили два шестизначных числа, приписав а к b сначала справа, а затем слева. Доказать, что разность этих шестизначных чисел не делится на 2012.
Решение. Пусть а и b — данные трехзначные числа. Шестизначные числа, составленные из них, равны соответственно 1000а + b и 1000b + а, и по условию,
(1000а + b) - (1000b + а) = 999(а - b),
и так как разность неравных друг другу трехзначных чисел может быть равна любому числу от 1 до 899 (отрицательные разности в данном случае полностью аналогичны положительным), то надо доказать, что ни при каких натуральных k от 1 до 899 число 999k не делится на 2012.Посмотрим, какие у этих чисел есть делители:
999k = 9 ∙ 111k = 9 ∙ 37 ∙ 3k = 27 ∙ 37k ;2012 = 4 ∙ 503,
дальше возникает подозрение, что число 503 простое, но мы не будем выяснять, так ли это на самом деле, - нам достаточно проверить, имеет ли оно общие делители с первым числом. Устроим проверку: по признаку делимости 503 не делится на 3, а так как 503 = 4 ∙ 111 + 63, то оно не делится и на 37. Поэтому числа 999 и 2012 взаимно просты, и если число 999k делится на 2012, то на 2012 делится число k, но так как k - число от 1 до 899, то это невозможно, значит, разность полученных в задаче шестизначных чисел не делится на число 2012.
Сравнения
Определение. Если два числа а и b имеют одинаковые остатки при делении на m, то говорят, что а и b сравнимы по модулю m, и пишут: a ≡ b (mod m), читают так: a сравнимо с b по модулю m.
Теорема 1. Сравнение a ≡ b (mod m) имеет место в том и только в том случае, если разность а-b делится на m.
Теорема 2. Сравнения можно почленно складывать и вычитать, т. е. если a ≡ b (mod m) и c ≡ d (mod m), то a+c=b+d (mod m) и а-с=b-d (mod m).
Теорема 3. Сравнения можно почленно умножать, m. е. если a ≡ b (mod m), c ≡ d (mod m), то ас ≡ bd (mod m).
Следствие 1. Сравнения можно возводить в степень, т. е. если a ≡ b (mod m), то аn ≡ bn (mod m).
Задача 1.
Найдите остаток отделения 14256 на 17.
Решение. 14256 ≡ (-3)256 = З256 = 8164 ≡ (-4)64 = 464 = 1632 ≡ (-1)32 = 1 (mod 17).
Ответ: 1.
Задача 2.
Найдите последнюю цифру числа 199820012004Решение. Необходимо найти остаток от деления на 10:
199820012004 ≡ 820012004 (mod 10)Составим таблицу для последней цифры степеней числа 8:
1 2 3 4 5
8 4 2 6 8
Получилось повторение: 81 = 85 (mod 10). Следовательно, последняя цифра будет повторяться через 4. тогда 8 20012004≡8(4∙500+1)2004=84n+1=8∙84n=8∙42n≡8∙6n≡8 (mod 10),
т.к. 6n всегда оканчивается на цифру 6 для любого n∈N.
Ответ: 8.
Задача 3.
Докажите, что числа вида 12n + 5 не могут быть квадратами целых чисел.
Решение. Предположим, что 12n + 5 = m2. Тогда 5≡m2 (mod 12). Составим таблицу квадратов по модулю 12 числа т:
m 0 1 2 3 4 5 6 7 8 9 10 11
m2 0 1 4 9 4 1 0 1 4 9 4 1
Из таблицы видно, что ни одно из них не сравнимо с 5 по модулю 12.
Задача 4.
Доказать, что при любом натуральном n число 122n + 1 + 11n+2 делится на 133.
Решение. Мы имеем:
122n+1 = 12 ∙ 122n = 12 ∙ 144n.
Но 144 ≡ 11 (mod 133), и потому 144n= 11n (mod 133). Умножая на 12, получаем 12 ∙ 144n ≡ 12 ∙ 11n (mod 133), так что 122n+1 ≡ 12 ∙ 11n (mod 133). Далее, 11n+2= 121 ∙ 11n. А так как 121 ≡ -12 (mod 133), то 121 ∙ 11n = -12 ∙ 11n (mod 133), т. е. 11n+2 ≡ -12 ∙ 11n (mod 133). Складывая сравнения
122n+1 ≡ 12 ∙ 11n (mod 133)
11n+2 ≡ -12 ∙ 11n (mod 133)
получаем 122n+1 + 11n+2 = 0 (mod 133), т. е. число 122n+1 + 11n+2 делится на 133.
Задача 5.
Доказать, что всякое натуральное число n сравнимо по модулю 9 со своей суммой цифр.
Решение. Пусть
a= anan-1…a0,
Где a0,a1,…,an - цифры числа а. Имеем
a = an ∙ 10n + an-1 ∙ 10n-1 + … + a0
Запишем теперь следующие очевидные сравнения:
1 ≡ 1 (mod 9), 10 ≡ 1 (mod 9)10n ≡ 1 (mod 9).
Умножая эти сравнения соответственно на a0,a1,…,an и складывая, получаем
a0 + 10a1 + … + 10nan = a ≡ (a0 + a1 + … + an) (mod 9).
Задача 6.
Найдите остаток от деления на 3 числа N=(12 +1)(22 + 1)(32 + 1)...(10002 + 1).
Решение. N ≡ (12 + 1)333 ∙ (22 + 1)333 ∙ (32 + 1)333 ≡ 2333 ∙ 2333 ∙ 1333 ≡ 2666 ≡ (22)333 ≡ 1333 ≡ 1.
Ответ: 1.
Инварианты и раскраски
Чётность суммы чисел. Применение делимости.
Инвариант (от лат. invarians - неизменяющийся), в математике - величина, остающаяся неизменяемой при тех или иных преобразованиях.
В ряде задач встречается следующая ситуация. Некоторая система последовательно изменяет своё состояние, и требуется выяснить нечто о её конечном состоянии. Полностью проследить за всеми переходами может оказаться делом сложным, но иногда ответить на требуемый вопрос помогает вычисление некоторой величины, характеризующей состояние системы и сохраняющейся при всех переходах (такую величину называют инвариантом для рассматриваемой системы). Ясно, что тогда в конечном состоянии значение инварианта будет то же самое, что и в начальном, т.е. система не может оказаться в состоянии с другим значением инварианта. На практике этот метод сводится к тому, что некоторая величина вычисляется двумя способами: сначала она просто вычисляется в начальном и конечном состояниях, а затем прослеживается её изменение при последовательных мелких переходах.Наиболее простым и часто встречающимся инвариантом является четность числа; инвариантом может быть также и остаток от деления не только на 2, но и на какое-нибудь другое число. Для построения инвариантов иногда бывают полезны вспомогательные раскраски, т.е. разбиения рассматриваемых объектов на несколько групп (каждая группа состоит из объектов одного цвета).Многие задачи легко решаются, если заметить, что некоторая величина имеет определённую чётность. Из этого следует, что ситуации, в которых эта величина имеет другую чётность, невозможны. Иногда эту величину (функцию) надо сконструировать, например, рассмотреть чётность суммы или произведения, разбить объекты на пары, заметить чередование состояний, раскрасить объекты в 2 цвета. Отметим, что часто для нахождения идеи решения задачи можно использовать «метод маленьких чисел», т. е. начинать поиск решения с небольших чисел.
Олимпиадные задачи на инварианты можно условно разбить на два вида: те, в которых требуется доказать некий инвариант, т. е. он явно определен, и те, в которых инвариант используется при решении и сразу не очевиден. Существует также класс задач, при решении которых используются полуинварианты – значения точной верхней и нижней граней для некоторой величины. Наиболее часто они используются в задачах на доказательство экстремума какой - либо величины. Рассмотрим способ решения задач по методу “Инвариант”.
В некоторых задачах по математике дается набор преобразований исходного объекта и спрашивается: можно ли, используя эти преобразования, получить из одного состояния объекта другое? Перебором вариантов часто легко убедиться в правильности ответа “нельзя”, однако обосновать этот ответ бывает трудно. Методом, позволяющим во многих случаях решать доказательную часть таких задач, является метод инвариант. Инвариантом называется нечто, не меняющееся в преобразованиях, например, число, набор чисел, четность какого – либо числа и другое. Если значение инварианта в двух состояниях объекта различно, то одно из них нельзя получить из другого. Придумать инвариант должен ученик, самостоятельно решающий задачу; обычно это вызывает у него затруднения. В качестве инварианта чаще всего рассматриваются четность (нечетность) чисел и остаток от деления. Причем применение четности – одна из наиболее встречающихся идей при решении олимпиадных задач. Применение идеи четности и нечетности основано на двух важных утверждениях (леммах):
Лемма 1. Четность суммы нескольких целых чисел совпадает с четностью количества нечетных слагаемых.
Пример. Число 1 +2 + 3 + … + 10 – нечетное, так как в сумме 5 нечетных слагаемых. Пример 2. Число 5 + 7 + 9 + 11 +13 + 15 – четное, так как в сумме 6 нечетных слагаемых.
Лемма 2. Знак произведения нескольких (отличных от 0) чисел определяется четностью количества отрицательных сомножителей.
Пример 1. Число (-1) *(-2) *(-3) *(-4) положительно, так как в произведении четное число отрицательных сомножителей.Пример 2. Число (-1) *2 * (-3) * (-4) отрицательно, так как в произведении нечетное число отрицательных сомножителей.
Задача 1. На листе бумаги написано число 11. Шестнадцать учеников передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу – как хочет. Может ли в результате получиться число 0?
Можно предложить выполнить эту операцию учащимся (результат каждого хода записывается на доске), заметить закономерность: после каждого хода характер четности меняется: после первого ученика число становится четным, после второго нечетным; после третьего - четным; после четвертого – нечетным. Тогда после шестнадцатого число будет нечетным. Поэтому нуль в конце получиться не может.
Задача 2. На вешалке висят 20 платков. 17 девочек по очереди подходят к вешалке и либо снимают, либо вешают платок. Может ли после ухода девочек остаться ровно 10 платков?
Решение. После подхода первой девочки количество оставшихся платков либо 19, либо 21 (нечетное количество); после подхода второй девочки – либо 18, либо 20, либо 22 (четное количество); после подхода третьей девочки – либо 17, либо 21, либо 23, либо 19 (нечетное количество). После подхода 17 девочки остается нечетное количество платков. Получается противоречие. Значит, 10 платков остаться не может.
В первой и во второй задачах инвариантом является четность суммы чисел.
Задача 3. В таблице, где имеются 15 чисел (-1), можно производить следующую операцию: одновременно изменить знак двух (не более, не меньше) чисел в таблице. Можно ли, применяя эту операцию конечное число раз, получить таблицу, состоящую из (+ 1)?
Решение. Ответ: нельзя. Так как число чисел в таблице нечетно, а после каждой операции число чисел (+ 1) в таблице четно. На языке инвариантов это означает: инвариантом таблицы относительно введенной операции является произведение всех чисел в таблице. В начальный момент это произведение равно ( - 1), а нам нужно получить таблицу, инвариант которой равен ( + 1).
Задача 4. Имеется набор чисел а, в, с. Данный набор чисел меняется на тройку чисел: а + в – с, в + с – а, а + с – в. Дан набор чисел 2000, 2002, 2003. Можно ли из него получить набор из чисел 2001, 2002, 2003?
Решение. Ответ: нельзя. Так как (а + в + с) и (а + в - с) +(в +с – а) +(а + с – в) равны, а сумма 2000+2002 +2003 и сумма 2001 + 2002 +2003 различны.
Задача 5. На столе 6 стаканов, Из них 5 стоят правильно, а один перевернут вверх дном. Разрешается переворачивать одновременно 4 любых стакана. Можно ли все стаканы поставить правильно?
Решение. Нет, так как в любом случае перевернутых вверх дном стаканов будет числом нечетным.
Задача 6. Из цифр 2, 3, 4,… 9 составили два натуральных числа. Каждая цифра использовалась один раз. Могло ли одно из этих чисел оказаться вдвое больше другого?
Решение. Ответ: нет. Пусть а и b = 2а – полученные числа, S(a) и S(b) – суммы их цифр. По признаку делимости числа N и S(N) имеют одинаковые остатки при делении на 3. Поскольку число a + b = 3a делится на 3, то сумма S = S(a) + S(b) должна делиться на 3, что неверно, так как S = 2 + 3 + 4 + … + 9 = 44.
Задача 7. На доске написаны числа 1, 2, …, 1998. За один ход разрешается стереть любое количество чисел и вместо них записать остаток от деления их суммы на 11. Через несколько ходов на доске остались два числа, одно из которых – 1000. Чему равно второе число?
Решение. Так как в конечном итоге на доске оказались записанными два числа, то хотя бы одно из них является остатком от деления некоторого числа на 11, т.е. не превосходит 10.Число 1000 не может являться остатком от деления какого-то числа на 11, поэтому искомое число не больше 10. Заметим, что в результате выполнения указанных операций остаток от деления суммы всех написанных чисел не изменится, так как для любых чисел а и в (а + в)(mod p) (a(mod p) + b(mod p))(mod p), где р – произвольное простое число. Первоначально 1 + 2 + … +1998 = 1997001 6 (mod 11) 1000 (mod p) + второе число. Так как 1000 10 (mod 11), то второе число 7.
Задача 8. В некотором государстве было 10 банков. С момента перестройки общества все захотели стать банкирами. Но по закону открыть банк можно только путем деления уже существующего банка на 4 новых. Через некоторое время министр финансов сообщил президенту, что в стране действует 2007 банков, после чего был немедленно уволен за некомпетентность. Что не понравилось президенту?
Решение. Заметим, что в результате превращения одного старого банка в четыре новых общее количество банков увеличится на 3. Таким образом, в любой момент времени число банков равно Б = 10 + 3 k и остаток от деления числа банков на 3 постоянен. (Это и есть инвариант). То есть Б . Первоначально Б ( mod 3) >, а 2007 .
Задача 9. Разместите цифры 0,1,2,3, …, 9 по кругу так, чтобы сумма всех разностей (по модулю) между соседними числами оказалась равна 25.
Решение. Пусть заданные числа каким-то образом проставлены по кругу и a, b, c, d – четыре соседних числа. Поменяем местами числа a >и c. Исследуем, как изменилась сумма рассматриваемых в задаче разностей. Для расстановки a, b, c, d она равна , а для расстановки a , c, b , d – , где – сумма разностей для оставшихся чисел. Изменение общей суммы Если b >и c имеют одинаковую четность, то будет представлять собой сумму двух четных чисел, а если они разной четности, то является суммой двух нечетных чисел, но в любом случае четно. Следовательно, мы получили инвариант – при перестановке двух соседних чисел четность суммы разностей не изменится. Любую расстановку заданных чисел по кругу можно получить, переставляя несколько раз соседние числа, тем самым мы доказали, что для любой расстановки заданных чисел сумма разностей имеет одну и ту же четность. Рассмотрев произвольную расстановку чисел (от одного до девяти), мы получим, что сумма разностей четна, и, значит, требуемая в задаче расстановка невозможно.
Задача 10. На доске написаны числа 1, 2, 3, …, 1998. За один ход разрешается стереть любые два числа и вместо них записать их разность. В результате многократного выполнения таких действий на доске окажется записанным одно число. Может ли оно быть нулем?
Решение. Не может. Так как вначале на доске 999 нечетных чисел. На каждом шаге их количество не меняется, если среди выбранных чисел не более одного нечетного числа. А если выбранные числа оба нечетны, то количество нечетных чисел уменьшается на два. Таким образом, инвариант преобразования: количество нечетных чисел нечетно. Поэтому в конце должно остаться нечетное число. А нуль – четное число.
Задача 11. Числа 0,1,2,3, …, 9 записаны по кругу. За один ход разрешается прибавить к двум соседним числам одно и то же целое число. Можно ли за несколько ходов получить десять нулей?
Решение. Нельзя. При прибавлении одинаковых целых чисел к любым двум из имеющихся не меняет четность общей суммы всех чисел. Первоначально эта сумма равно 1 + 2 + 3 + … 9 = 45, следовательно, после каждого хода общая сумма полученных чисел должна быть нечетна, а нуль – четное число.
Задача 12. В десяти сосудах содержится 1, 2, 3,…, 10 литров воды. Разрешается перелить из сосуда А в сосуд В столько воды, сколько имеется в В. Можно ли добиться, чтобы после нескольких переливаний в 5 сосудах оказалось 3 литра, а в остальных 6, 7, 8, 9, 10?
Решение. Нельзя. Предложенная операция обладает полуинвариантом: при любом переливании число нечетных сосудов (содержащих нечетное число литров воды) не увеличивается. Количество таких сосудов уменьшается при переливании из нечетного сосуда в нечетный, а в остальных случаях не изменяется. Следовательно, переход 1, 2, … 10 —> 3, 3, 3, 3, 3, 6,…,10 невозможен, поскольку увеличивает число нечетных сосудов.
Задача 13. В шести коробках лежат конфеты. В первой – 1, во второй – 2, в третьей – 3, …, в шестой – 6. За один ход разрешается в любые две коробки добавить по одной конфете. Можно ли за несколько ходов уравнять количество конфет в коробках?
Решение. Заметим, что после каждого хода суммарное число конфет в коробках увеличивается на 2. Сначала в коробках была 21 конфета. Это означает, что после каждого хода суммарное число конфет в коробках будет нечётным. А если бы мы смогли уравнять количество конфет в коробках, то суммарное число конфет в коробках равнялось бы 6k – числу чётному.
Вспомогательные раскраски на клетчатых досках.
Очень важный и стоящий несколько особняком класс задач на инвариант - какие-то преобразования на клетчатых досках. Либо мы ходим чем-нибудь по доске, либо замощаем доску фигурами. В любом случае, очень полезной может быть раскраска доски в два или более цветов, обладающая какими-то особыми свойствами. Наиболее распространенные раскраски:- шахматная (два цвета чередуются так, что любые две соседние по стороне клетки - разных цветов);- "матрас" (чередование строк, выкрашенных в два цвета - или столбцов);- укрупненная шахматная (в шахматном порядке красятся не отдельные клетки, а целые блоки 2x2, 3x3 и т.д.);- укрупненный "матрас" (чередуются не строки, а одинаковые по толщине блоки из строк);- "матрас" в N цветов: чередуются строки, выкрашенные в цвета, 1-й, 2-й, ... N-й, 1-й, 2-й и т.д.- шахматная в N цветов - легче показать, чем написать; см. на рис. пример для 3-х цветов; можно и по-другому, чтобы одноцветные диагонали были наклонены в другую сторону.

Обычный инвариант - цвет клеток, по которым мы ходим (или какое-то чередование цветов, или какие-то цвета, на которые мы никогда не попадаем...), либо количества клеток тех и других цветов на всей доске и в фигурах замощения (если не совпадают, то замостить нельзя). Смотрите приведенные ниже примеры.
Задача 1. В каждой клетке доски, размер которой 7×7, сидит жук. В некоторый момент времени все жуки переползают на соседние (по вертикали или горизонтали) клетки. Докажите, что в какой-то клетке не окажется ни одного жука.
Решение.
Раскрасим клетки данной доски в шахматном порядке. Тогда из 49 клеток 25 клеток окажутся черными, 24 – белыми (или наоборот). В некоторый момент 25 жуков с черных клеток переползают на соседние белые клетки, которых оказывается 24, и занимают они не более 24 белых клеток. Другие 24 жука, расположенные на белых клетках, должны занять не более 24 черных клеток. Следовательно, хотя бы одна клетка останется пустой.
Задача 2. Фигура "крокодил" ходит по клетчатой доске на 3 клетки в одном направлении и одну в перпендикулярном (почти как шахматный конь, только конь ходит не на 3, а на 2 клетки). Докажите, что нельзя пройти крокодилом с какого-то поля на соседнее (по стороне) с данным.Решение:
Раскрасим доску в шахматном порядке. Тогда (нетрудно убедиться) крокодил при своем ходе не меняет цвет клетки, на которой стоит. А соседняя клетка, увы, другого цвета, ч.т.д.
Задача 3. Докажите, что шахматную доску нельзя замостить 15-ю прямоугольниками 1x4 и одной фигуркой вида .Решение:
Шахматная раскраска тут не поможет. Она, так скажем, не отличает особую фигурку от прямоугольника: и в ней и в них ровно 2 белых и 2 черных клетки. И ничто не противоречит тому, что доску можно замостить 16-ю фигурами с таким свойством. Попробуем другую раскраску, скажем, "матрас". Тогда в прямоугольнике 1x4 то ли 0, то ли 2, то ли 4 черные клетки (смотря как он лежит). А в особой фигурке - то ли 1, то ли 3. Короче, там - четное, здесь - нечетное. А сумма 15 четных чисел и одного нечетного нечетна и не может поэтому быть равна 32 (числу черных клеток на шахматной доске), ч.т.д.Собственно, инвариантом тут можно назвать четность количества черных клеток. Только мы тут не преобразуем объект или набор объектов, а составляем один объект (доску) из других.
Задача 4. Фишка ходит по доске NxN, сдвигаясь на 1 клетку вверх, вправо или вниз-влево по диагонали. Может ли фишка обойти все клетки доски по разу и закончить путь сверху от начальной клетки.Решение:
Подберем раскраску, при которой фишка будет одинаково менять цвет при любом ходе. Просто шахматная и "матрас" не подойдут. А зато шахматная раскраска в 3 цвета - просто замечательно (см. рис. выше). Наша фишка будет ходить с красного на желтый, с желтого на зеленый, с зеленого на красный и т.д. Пусть, скажем, начальная клетка красная - тогда конечная будет желтая. Цвета чередуются по циклу длины 3, поэтому число ходов: 3k+1 (т.е. =1 по mod 3). Но то же число ходов на доске NxN равно N2-1. Отсюда N2=2 (mod 3), чего, по соображениям теории чисел не бывает. Ответ "нельзя".
Задача 5. На клетчатой бумаге отмечены произвольные п клеток. Доказать, что из них всегда можно выбрать не менее, чем п:4 клеток, попарно не соприкасающихся друг с другом (соприкасающимися считаются клетки, имеющие хотя бы одну общую вершину).
Решение.
Разобьем всю плоскость на одинаковые квадраты, состоящие из четырех клеток каждый. Далее, в каждом из этих квадратов левую верхнюю клетку назовем черной, а правую верхнюю клетку белой, левую правую клетку красной, а правую нижнюю клетку синей. Тогда, с одной стороны, любые две клетки одного цвета не соприкасаются. С другой стороны, среди отмеченных клеток можно выбрать не менее четверти таких, которые имеют одинаковый цвет ( в противном случае всего клеток было бы менее, чем 4∙(п:4)=п
Задача 6 . Доску размером 10х10 клеток разрезать на фигурки в форме буквы Т, состоящие из четырех клеток.Решение:
Предположим, что доска 10х10 клеток разбита на такие фигурки. Каждая фигурка содержит либо 1, либо 3 черные клетки, т.е. всегда нечетное число. Самих фигурок должно быть 100/4=25 штук. Поэтому они содержат нечетное число черных клеток, а всего черных клеток 100/2=50 штук. Получено противоречие.
Задача 7. Мышка грызет куб с ребром 3, разбитый на 27 единичных кубиков. Когда мышка съедает какой-либо кубик, она переходит к другому кубику, имеющему общую грань с предыдущим. Может ли мышка съесть весь куб, кроме центрального кубика?
Решение.
Каждый из 26 единичных кубиков, отличных от центрального, будем считать либо черным, либо белым в шахматном порядке: 12 кубиков, имеющих ровно по две грани на поверхности большого куба, назовем белыми, а остальные 14 – черными. Заметим, что в любой паре таких кубиков, имеющих общую грань, один кубик будет белым, а другой черным. Указанные 26 кубиков мышка съесть не сможет, поскольку в противном случае их можно было бы разбить на 13 пар, каждая из которых состояла бы из белого и черного кубика, а тогда белых и черных кубиков было бы поровну.
(!) Инвариант инвариантом, но и про другие области математики по ходу дела не надо забывать. Часто решение может прийти именно оттуда. Аккуратно нужно подходить к задачам про разные процессы с вопросом "можно ли". Да, большая часть из них - с ответом "нельзя", который доказывается через инвариант. Но попадаются иногда задачи с ответом "можно", где надо строить пример. Иногда, увлекшись поиском инварианта, можно не заметить существования простого.
Список литературы
Агаханов Н.Х. Районные олимпиады. 6-11 классы / Н.Х.Агаханов, О.К.Подлипский. – М.: Просвещение, 2010. – 192 с.
Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П. Основы теории делимости чисел. Решение уравнений в целых числах. Факультативный курс. – М.: МГИЭТ(ТУ), 2003. – 224 с.
Болтянский В.Г., Левитас Г.Г. Делимость чисел и простые числа. В книге: Дополнительные главы по курсу математики. Учебное пособие по факультативному курсу для учащихся 7-8 классов. – М.: Просвещение, 1974. – 65с.
Вольфсон Г.И. Математика. Не так страшна задача на делимость, как её малюют. Учебное пособие для учащихся 11 классов. СПб: СМИО Пресс, 2010. – 64с.
Галкин В.Я., Сычугов Д.Ю., Хорошилова Е.В. Конкурсные задачи, основанные на теории чисел. – М., факультет ВМиК МГУ 2002 – 180 стр.
Гельфонд А.О. Решение уравнений в целых числах. – М.: Наука. Главная редакция физико-математической литературы, 1978. – 63с.
Дорофеев Г.В. ЕГЭ 2009. Математика Суперрепетитор / Г.В. Дорофеев, Е.А. Седова, С.А. Шестаков. – М.: Эксмо, 2009. – 448 с.
Пратусевич М.Я. и др. ЕГЭ 2011. Математика. Задача С6. Арифметика и алгебра / Под ред. А.Л. Семёнова и И.В. Ященко. – М.: МЦНМО, 2011. – 48 с.
Шень А. Игры и стратегии с точки зрения математики. – М.: МЦНМО, 2007. – 40с.

Приложенные файлы

  • docx faiil1.docx
    Размер файла: 21 kB Загрузок: 0
  • docx faiil2.docx
    Размер файла: 140 kB Загрузок: 0

Добавить комментарий