К КАКОМУ ПАРИКМАХЕРУ ОТПРАВИТСЯ МАТЕМАТИК?
(ИНВАРИАНТЫ В РЕАЛЬНОЙ ЖИЗНИ)
Работу выполнила: ученица 6 класса Б
Мусаева Ирина
Руководитель: Трофимова
Маргарита Витальевна,
учитель математики
высшей квалификационной категории
2011 год
Содержание.
Введение…………………………………………………………….2
Глава 1. Понятие инварианта……………………………………….3
Понятие инварианта.…………………………………..3 Чётные и нечётные числа………………………………3 Определение чётности………………………………..3 Признак чётности……………………………………………….4 Свойства чётности…………………………………...4 Леммы о чётности…………………………………..5Глава 2. Банк задач………………………………………………….6
Вывод………………………………………………………………..17
Литература…………………………………………………………...19
Введение.
Готовясь к олимпиадам по математике, я столкнулась с проблемой решения задач на инварианты. Эти задачи встречаются не только в математике, но и в информатике. Я собираюсь продолжить и дальше решать олимпиадные задачи по математике, в содержание которых входят различные задачи на использование жизненных ситуаций. Такие задачи я решала, готовясь к очным и заочным олимпиадам, международному конкурсу «Кенгуру», занимаясь в математическом кружке, и поняла, что мне интересна эта тема.
Данная тема является актуальной в современное время, так как сами инварианты появились из практической необходимости. Современная жизнь делает задачи на инварианты актуальными, так как сфера практического приложения инвариантов расширяется. Эти задачи можно использовать при организации досуга с друзьями или на тематических вечерах.
Целями моей работы являются:
В первой главе я рассмотрела понятие инвариантов. Так как сама тема инварианты появилась из практической необходимости и остается актуальной и посей день.
Во второй главе я разобрала задачи на инварианты.
Глава 1. Понятие инварианта.
Понятие инварианта.
Инвариант — это величина, которая остаётся неизменной при тех или иных преобразованиях. В некоторых задачах инвариант — это величина, которая изменяется монотонно, то есть только увеличивается или только уменьшается. В качестве инварианта чаще всего рассматриваются чётность (нечётность) и остаток от деления. Хотя встречаются и другие стандартные инварианты: перестановки, раскраски и т. п. Причём применение чётности — одна из наиболее часто встречающихся идей при решении олимпиадных задач.
Чётные и нечётные числа.
Чётность в теории чисел — характеристика целого числа, определяющая его способность делиться нацело на два. Чётное число — целое число, которое делится без остатка на 2: …−4, −2, 0, 2, 4, 6, 8.… В соответствии с этим определением нуль является чётным числом. Нечётное число — целое число, которое не делится без остатка на 2: …−3, −1, 1, 3, 5, 7, 9.… Если m чётно, то оно представимо в виде m = 2n, а если нечётно, то в виде m = 2n + 1, где n — некоторое целое число.
Если два числа отличаются на 1, то они разной чётности. Например, 97 и 82, то есть число х + 2 имеет ту же чётность, что и число х (или оба чётные, или оба нечётные), а при прибавлении единицы чётность числа меняется.
Признак чётности
Если в десятичной форме записи числа последняя цифра является чётным числом (0, 2, 4, 6 или 8), то всё число так же является чётным, в противном случае — нечётным.
42, 104, 11110, 9115817342 — чётные числа.
31, 703, 78527, 2356895125 — нечётные числа.
Свойства чётности.
Сложение и вычитание: Чётное ± Чётное = Чётное Чётное ± Нечётное = Нечётное Нечётное ± Чётное = Нечётное Нечётное ± Нечётное = Чётное Умножение: ётное = Чётное ечётное = Чётное ечётное = Нечётное Деление: Чётное : Чётное — однозначно судить о чётности результата невозможно (если результат целое число, то оно может быть как чётным, так и нечётным) Чётное : Нечётное = если результат целое число, то оно Чётное Нечётное : Чётное — результат не может быть целым числом, а соответственно обладать атрибутами чётности Нечётное : Нечётное = если результат целое число, то оно НечётноеДалее рассмотрим два важных более общих утверждения, на которых основано применение идеи чётности и нечётности:
Лемма 1. Чётность суммы нескольких целых чисел совпадает с чётностью количества нечётных слагаемых.
Например:
Число 1 + 2 + .. . + 10 — нечётное, так как в сумме 5 нечётных слагаемых. Число 3 + 5 + 7 + 9 + 11 + 13 — чётное, так как в сумме 6 нечётных слагаемых.Лемма 2. Знак произведения нескольких (отличных от нуля) чисел определяется чётностью количества отрицательных сомножителей.
Например:
Число (—1) • (—2) • (—3) • (—4) положительно, так как в произведении чётное число отрицательных сомножителей. Число (—1) • 2 • (—3) • 4 • (—5) отрицательно, так как в произведении нечётное число отрицательных сомножителей.Глава 2. Банк задач.
Часто фразу "можно ли" следует читать как "докажите, что это невозможно". В любом случае, в "можно ли" – задачах имеет смысл попытаться доказать невозможность существования решения — это может помочь найти его, если решение всё-таки существует.
В задачах, где необходимо доказать невозможность достичь чего-либо в результате некоторого процесса (например, последовательного выкладывания фигур домино), инварианты являются мощным инструментом в руках умелого математика.
Задача № 1.
Математик, оказавшись в небольшом городке, решил подстричься. В городке было лишь две парикмахерских. Заглянув к одному мастеру, он увидел, что в салоне грязно, сам мастер одет неряшливо, плохо выбрит и небрежно подстрижен. В салоне второго мастера все было чисто, а сам владелец был безукоризненно одет, чисто выбрит и аккуратно подстрижен. К какому парикмахеру отправился стричься математик? Почему?
Решение. Так как в городе всего две парикмахерских, а второй мастер хорошо выбрит и аккуратно подстрижен, то подстриг его первый мастер. Значит, математик отправился стричься к первому парикмахеру.
Ответ: к первому.
Рассмотрим решение следующих задач №2 и №3, в которых инвариантом является чётность суммы чисел (нечётная).
Задача № 2.
Ведущий написал на листке бумаги число 10. 15 игроков передают листок друг другу, и каждый прибавляет к числу или отнимает от него единицу — как хочет. Может ли в результате получиться число 0?
Решение. Заметим закономерность: после каждого хода характер чётности меняется: после первого игрока число становится нечётным; после второго чётным; после третьего — нечётным. Тогда после пятнадцатого число будет нечётным. Поэтому нуль в конце получиться не может.
Ответ: не может.
Задача № 3.
На доске записано число, состоящее из 15 цифр: 8 нулей и 7 единиц. Вам предлагается 14 раз подряд выполнить такую операцию: зачеркнуть любые две цифры, и если они одинаковые, то допишите к оставшимся цифрам нуль, а если разные — то единицу. Какое число останется на доске?
Решение. Сумма 15 исходных цифр равна 7. А 7 — число нечётное. Рассмотрим, какая сумма цифр будет получаться после выполнения операции. Если вычеркнем 2 нуля, то после дописывания нуля на доске будет 7 нулей и 7 единиц. Сумма этих 14 цифр будет нечётная. Если вычеркнем 2 единицы, то на доске останется после дописывания нуля 9 нулей и 5 единиц. Сумма данных 14 цифр будет нечётной. Наконец, вычеркивая нуль и единицу и приписывая единицу, мы получим на доске 7 нулей и 7 единиц, сумма которых снова является нечётным числом. Таким образом, мы замечаем, что после выполнения данной операции на доске получается на 1 цифру меньше, причем сумма оставшихся цифр всё время остается нечётной. Далее продолжаем эту операцию, то есть переходим от 14 цифр к 13 и т. д. Так как 1 — нечётное число, а 0 — чётное, то на доске после выполнения 14 раз указанной операции получается нечётное число, то есть 1.
Ответ: 1.
Задача № 4.
Все костяшки домино выложены в цепь (по правилам домино). На одном конце цепи оказалось 3 очка. Сколько очков на другом конце?
Решение. Всего имеется семь костяшек с тройкой на конце: 0-3, 1-3, 2-3, 3-3, 4-3, 5-3, 6-3. Костяшка 3-3 имеет «тройку» на обоих концах. Всего получается восемь «троек». Так как при игре в домино в цепи они должны располагаться парами, то на другом конце цепи будет 3 очка. Инвариантом здесь является чётность количества троек на всех костяшках.
Ответ: 3.
Задача № 5.
Квадрат 5x5 заполнен числами так, что произведение чисел в каждой строке отрицательно. Доказать, что найдется столбец, в котором произведение чисел также отрицательно.
Решение. Так как произведение чисел в каждой строке квадрата отрицательно, то и произведение всех чисел в этом квадрате будет отрицательно. Но с другой стороны, произведение всех чисел равно и произведению чисел в столбцах. А так как произведение всех чисел отрицательно, то найдется столбец, в котором произведение чисел является отрицательным. Задача доказана. Инвариант — знак произведения чисел (он отрицательный).
Задача № 6.
Какие часы чаще показывают точное время: те, которые отстают на 1 минуту в день, или те, которые стоят?
Решение. Вторые, так как первые показывают верное время 1 раз в 2 года, а вторые 2 раза в год.
Ответ: те, которые стоят.
Задача № 7.
На дереве сидело 20 ворон. Охотник выстрелил и убил двух ворон. Сколько ворон осталось на дереве?
Решение. В принципе могло остаться на дереве и 1 и 2 вороны, если при падении на землю они застряли в ветвях дерева. Остальные вороны улетели. Значит, ни одной.
Ответ: 0.
Задача № 8.
Можно ли разменять купюру достоинством 100 рублей с помощью 25 монет достоинством 1 и 5 рублей?
Решение. Нет, так как сумма 25 нечётных чисел – число нечётное 100 — число чётное.
Ответ: нет.
Задача № 9.
Конь вышел с поля а1 шахматной доски и через несколько ходов вернулся на него. Докажите, что он сделал чётное число ходов.
Решение. При каждом своем ходе конь меняет цвет поля, поэтому при возвращении обратно он должен сделать чётное число ходов. Задача доказана.
Задача № 10.
2010 человек выстроились в шеренгу. Всегда ли можно их расставить по росту, если за один ход разрешается переставлять только 2 людей, стоящих через одного?
Решение. При перестановке сохраняется чётность номера места. Поэтому если самый высокий человек, например, стоит вторым, то он никогда не станет первым. Здесь число 2010 роли не играет. Поэтому, не всегда можно их расставить по росту.
Ответ: не всегда.
Задача № 11.
16 корзин расположили по кругу. Можно ли в них разложить 55 арбузов так, чтобы количество арбузов в любых двух соседних корзинах отличалось на 1?
Решение. Так как число арбузов в соседних корзинах отличается на 1, то чётность числа арбузов в этих корзинах будет разной. Тогда чётность числа арбузов в корзинах будет чередоваться, поэтому в половине корзин будет чётное число арбузов, а в половине нечётное. Тогда общее число арбузов в 8 корзинах с чётным числом арбузов и в 8 корзинах с нечётным числом арбузов будет чётным. По условию же всего арбузов — 55, нечётное число. Значит, разложить нельзя.
Ответ: нельзя.
Задача № 12.
На столе стоят 6 стаканов. Из них 5 стоят правильно, а один перевернут вверх дном. Разрешается переворачивать одновременно 4 любых стакана. Можно ли все стаканы поставить правильно?
Решение. Нет, так как в любом случае число перевернутых вверх дном стаканов будет числом нечётным.
Ответ: нельзя.
Задача № 13.
Мише учитель математики поставил в дневник отметку «2». Миша, желая скрыть от мамы данный факт, порвал свой дневник на 4 части. Этого ему показалось мало, поэтому некоторые из этих частей (может быть, и не все) он порвал на 4 части и так далее. Мама нашла 20 «кусочков» дневника. Все ли куски нашла мама?
Решение. (1 способ) Так как число кусков могло быть 4; 7; 10; 13; 16; 19; 22, то мама нашла не все куски.
(2 способ) Число кусков, которые могли получиться, записываются в виде Зр + 1, а число 20 = 6 ∙ 3 + 2. Получаются разные остатки от деления на 3. Остаток от деления также может быть инвариантом.
Ответ: не все.
Задача № 14.
Разрежьте квадрат на 4 части одинаковой формы и размера так, чтобы в каждую часть попало ровно по одному заштрихованному квадрату.
Решение. Два решения приведены на рисунках.
Задача № 15. Задача о «доминошках».
Имеется шахматная доска, из которой вырезали два противоположных угловых поля. Можно ли покрыть ее целиком фигурами домино (размером 2 Ч 1 поля шахматной доски) таким образом, чтобы каждое поле было полностью покрыто одной и только одной фигурой домино?
Решение. Шахматная доска состоит из темных и светлых полей. Одна положенная на доску фигура домино покрывает одно тёмное и одно светлое поле. Следовательно, необходимым (но далеко не достаточным) условием возможности замощения некоторой клетчатой фигуры при помощи фигур домино является равное количество темных и светлых полей на исходной доске. Шахматная доска с вырезанными противоположными угловыми полями не удовлетворяет этому условию, так как оба вырезанных поля — одного цвета. Мы пришли к противоречию, таким образом, задача решена.
Ответ: нельзя.
Задача № 16.
На столе лежат сто спичек. Играют двое, ходят по очереди. За один ход игрок может взять одну, две или три спички. Забравший последнюю спичку выигрывает. Кто выиграет при правильной игре — первый или второй игрок?
Решение. Если на столе осталась одна, две или три спички, выигрывает игрок, который ходит первым, так как он забирает все спички. Если на столе лежат четыре спички, первый игрок проигрывает, так как при любом его ходе соперник забирает все. Если на столе лежат пять, шесть или семь спичек, первый игрок снова выигрывает, оставив сопернику четыре спички. Несложно увидеть ответ — если число спичек на столе не делится на 4, при правильной игре выигрывает тот, кто ходит первым, иначе — второй игрок.
Для доказательства этого утверждения обратимся к инвариантам. В нашем случае инвариант — это остаток при делении на 4.
Требуется доказать два утверждения. Первое: «ход, оставляющий противнику число спичек, кратное четырём, является оптимальным и ведёт к выигрышу». Второе: «если такой ход сделать нельзя, то позиция является проигрышной». Первое утверждение эквивалентно утверждению «если число спичек на столе не делится на четыре», второе — «если делится».
Пусть на очередном ходе игроку досталось кратное четырём число спичек. Тогда, при любом его ходе, число спичек уже не будет кратно четырём. Его противник же всегда может сделать такой ход, что число спичек вновь станет кратно четырём. Выиграет при такой игре второй игрок, поскольку число спичек изначально положительно и постоянно уменьшается, а значение инварианта в конечном состоянии — ноль — делится на четыре, и, следовательно, будет достигнут на ходе второго игрока. Если изначально число спичек не кратно четырём, то первый игрок всегда может оставить второму число спичек, кратное четырем, поставив его в проигрышную позицию.
Ответ: второй игрок.
Задача № 17. «Игра Ним».
Игра Ним — это игра двух игроков, основанная на поочередном взятии камешков из одной или нескольких кучек. В свой ход игрок может взять любое ненулевое количество камешков из любой кучки, но только из одной. Игрок, которому не осталось камешков, проигрывает.
Кто выиграет в игре Ним для случаев:
две кучи по два камня — {2, 2}; {3, 1}?Решение. Существует множество игр, подобных игре Ним, отличающихся правилами взятия камней и условиями выигрыша. Но «исходная» игра Ним является ключевой, так как другие игры, в определённом смысле, к ней сводятся.
Выигрышную стратегию в игре Ним можно найти с помощью одного нехитрого инварианта. Ясно, что если кучка с камнями всего одна, то выигрывает первый игрок, забирая из неё все камни. Если кучек две и в них одинаковое число камней, то выигрывает второй, постоянно симметрично повторяя ходы первого. Если же в двух кучках различное число камней, то первый игрок выиграет, если первым ходом уровняет число камней в двух кучках. Ещё можно заметить, что если число кучек чётно, и кучки разбиваются на пары одинаковых (например, {3, 3, 5, 2, 2, 5}), то снова выигрывает второй игрок.
Ответ:
второй игрок; первый игрок.Вывод.
Все поставленные первоначально цели в моей исследовательской работе на тему «К какому парикмахеру отправится математик? (Инварианты в реальной жизни)» мною достигнуты. В данной работе я рассмотрела понятие инвариантов, разобрала задачи на инварианты.
Инварианты также можно использовать и в задачах, где начальных состояний больше одного. Нужно только подобрать такой инвариант, чтобы его значения для всех возможных начальных состояний были одинаковыми.
Если найден инвариант, который даёт различные значения для различных начальных и конечных состояний, такой инвариант тоже полезен — можно отсечь часть потенциальных решений, которые невозможны, и (или) часть начальных состояний, из которых решение заведомо недостижимо.
Хочется отметить, что тема моей исследовательской работы полезна и очень актуальна, тем более в наше время, когда олимпиады стали не только очными, но и заочными, а задачи на инварианты приобрели широкое распространение в нашей жизни.
При подготовке данной работы я обратила внимание, что ещё много нерешённых задач на инварианты.
В заключение хочется сказать, что есть задачи по программированию, в частности задача на динамическое программирование. Эти задачи отнесены к категории сложных, способы их решения пока мне не известны. Для успешного решения различных задач по математике и программированию необходимо уметь пользоваться инвариантами. Найти инвариант в сложной задаче непросто, однако это очень мощный, а часто и наиболее быстрый способ получить решение. Из литературы мне стало известно, что в программировании владение инвариантами открывает дорогу в мир динамического программирования, одного из наиболее интересных и эффективных методов решения задач.
Этой работой могут пользоваться учащиеся не только 5 – 6 классов, но и других классов при подготовке к олимпиадам, конкурсам, вечерам, учителя математики, а также учащиеся младших классов, для которых приведены задачи в виде рассказов, картинок.
При написании данной исследовательской работы я узнала много нового и интересного, и данный материал, я постараюсь использовать при подготовке к не только к олимпиадам, но и при организации досуга в кругу друзей, на тематических вечерах.
