Математические задачи для продвинутых. Знакомимся
Опровержение некоторых законов в любой области жизни или науки на практике осуществляется обычно приведением соответствующего примера. Например, утверждение: "все мужчины изменяют" лично опровергается верным мужем.
Намного сложнее доказать утверждение, претендующие на универсальность, где уже требуется некоторое подобие доказательства. В математике они бывают конструктивными, дающими рецепт построения нужного объекта, а бывают абстрактными, не дающими конкретного правила построения или нахождения объекта. К таким неконструктивным методам относится метод Дирихле. Звучит он совершенно очевидно: "Если n+1 зайцев посажены в n клеток, то хотя бы в одной клетке будет 2 зайца".
Самой простой задачей на эту тему является утверждение, что в Москве найдется по крайней мере 4 человека имеющих равное количество волос на голове. С юмором одна девочка из 7-го класса ответила так: "Юрий Михайлович, мой папа, учитель физики и младший братик абсолютно лысые (конструктивное доказательство утверждения во времена Лужкова). А реально надо вспомнить, что в Москве не менее 10 млн жителей, а на голове любого человека не более 3 млн волос. В данном случае клетки - это волосы, а зайцы - это люди, попадающие в клетки по числу волос. Если в каждой клетке не более чем по три человека, то лишнему придется присоединиться и быть 4-м.
Вот более серьезная задача, но с бытовым содержанием: "На склад привезли 60 ботинок по 20 штук каждого размера 41-го, 42-го и 43-го. Причем из этой обуви 30 штук левых и 30 штук правых. Как доказать, что в такой ситуации найдется не менее 10 пар правильной обуви, т.е. левых и правых одного размера? Вроде бы все очень просто, но доказать надо строго, без примеров возможных расстановок, которые не дадут ответа на общий вопрос. Если вы хотите проверить свою голову на изощренную, живую логику, то не читайте решение, приведенное ниже.
Итак, решение. Пусть есть какая-то раскладка обуви, отвечающая условиям задачи. В идеальном случае будет равное число ботинок левых и правых по всем размерам, тогда парной обуви окажется целых 30 штук. Если же в каком-то размере, например, левых ботинок не хватает, то в двух остальных размерах ботинок этого же типа (левого) совокупно будет больше, чем нужно. Это принцип Дирихле: размеров 3, а типа всего 2. Даже если предположить самое невероятное - что в каком-то из размеров будут только правые ботинки - в оставшихся двух размерах их в совокупности не может быть меньше 10 штук - ведь всего правых, как мы помним, 30. Таким образом, ботинок правого типа в двух размерах останется не меньше 10 штук, а уже левых с избытком хватит для этих правых. Задача решена.
Совсем невероятной по условию кажется следующая задача: доказать, что найдется 2 простых числа, у которых последние 6 цифр в десятичной записи совпадают.
Давайте рассуждать.
Известно, что простых чисел бесконечное множество. По клеткам разложим числа, дающие одинаковые остатки от деления на 1000000. В одну из клеток попадут не менее 2-х простых чисел: р1 и р2, разность которых р1-р2 делится на 1000000. А это значит, что на конце числа р1-р2 находится не менее 6 нулей, что говорит об одинаковых последних цифрах р1 и р2.
Если заинтересовались, подумайте над следующими задачками:
1) Доказать, что среди любых трех целых чисел найдется комбинация, связанная знаками + или - (алгебраическая сумма), которая делится на 7. (В комбинацию могут входить не все три числа)
2) На новогоднем празднике присутствует 20 детей. Каждый получает в подарок 3 разные игрушки, причем состав этих игрушек для разных детей разный хотя бы по одному наименованию. Какое наименьшее число наименований игрушек должно быть у организаторов, чтобы такое стало возможно?
3) В некоторой компании присутствуют люди, как знакомые друг с другом, так и не знакомые. Докажите, что не менее чем у двух человек имеется одинаковое число знакомых.
Решение этих задач может говорить о ваших высоких интеллектуальных способностях, но даже если не удалось их решить, не расстраивайтесь. Дайте их попробовать решить детям.
Намного сложнее доказать утверждение, претендующие на универсальность, где уже требуется некоторое подобие доказательства. В математике они бывают конструктивными, дающими рецепт построения нужного объекта, а бывают абстрактными, не дающими конкретного правила построения или нахождения объекта. К таким неконструктивным методам относится метод Дирихле. Звучит он совершенно очевидно: "Если n+1 зайцев посажены в n клеток, то хотя бы в одной клетке будет 2 зайца".
Самой простой задачей на эту тему является утверждение, что в Москве найдется по крайней мере 4 человека имеющих равное количество волос на голове. С юмором одна девочка из 7-го класса ответила так: "Юрий Михайлович, мой папа, учитель физики и младший братик абсолютно лысые (конструктивное доказательство утверждения во времена Лужкова). А реально надо вспомнить, что в Москве не менее 10 млн жителей, а на голове любого человека не более 3 млн волос. В данном случае клетки - это волосы, а зайцы - это люди, попадающие в клетки по числу волос. Если в каждой клетке не более чем по три человека, то лишнему придется присоединиться и быть 4-м.
Вот более серьезная задача, но с бытовым содержанием: "На склад привезли 60 ботинок по 20 штук каждого размера 41-го, 42-го и 43-го. Причем из этой обуви 30 штук левых и 30 штук правых. Как доказать, что в такой ситуации найдется не менее 10 пар правильной обуви, т.е. левых и правых одного размера? Вроде бы все очень просто, но доказать надо строго, без примеров возможных расстановок, которые не дадут ответа на общий вопрос. Если вы хотите проверить свою голову на изощренную, живую логику, то не читайте решение, приведенное ниже.
Итак, решение. Пусть есть какая-то раскладка обуви, отвечающая условиям задачи. В идеальном случае будет равное число ботинок левых и правых по всем размерам, тогда парной обуви окажется целых 30 штук. Если же в каком-то размере, например, левых ботинок не хватает, то в двух остальных размерах ботинок этого же типа (левого) совокупно будет больше, чем нужно. Это принцип Дирихле: размеров 3, а типа всего 2. Даже если предположить самое невероятное - что в каком-то из размеров будут только правые ботинки - в оставшихся двух размерах их в совокупности не может быть меньше 10 штук - ведь всего правых, как мы помним, 30. Таким образом, ботинок правого типа в двух размерах останется не меньше 10 штук, а уже левых с избытком хватит для этих правых. Задача решена.
Совсем невероятной по условию кажется следующая задача: доказать, что найдется 2 простых числа, у которых последние 6 цифр в десятичной записи совпадают.
Давайте рассуждать.
Известно, что простых чисел бесконечное множество. По клеткам разложим числа, дающие одинаковые остатки от деления на 1000000. В одну из клеток попадут не менее 2-х простых чисел: р1 и р2, разность которых р1-р2 делится на 1000000. А это значит, что на конце числа р1-р2 находится не менее 6 нулей, что говорит об одинаковых последних цифрах р1 и р2.
Если заинтересовались, подумайте над следующими задачками:
1) Доказать, что среди любых трех целых чисел найдется комбинация, связанная знаками + или - (алгебраическая сумма), которая делится на 7. (В комбинацию могут входить не все три числа)
2) На новогоднем празднике присутствует 20 детей. Каждый получает в подарок 3 разные игрушки, причем состав этих игрушек для разных детей разный хотя бы по одному наименованию. Какое наименьшее число наименований игрушек должно быть у организаторов, чтобы такое стало возможно?
3) В некоторой компании присутствуют люди, как знакомые друг с другом, так и не знакомые. Докажите, что не менее чем у двух человек имеется одинаковое число знакомых.
Решение этих задач может говорить о ваших высоких интеллектуальных способностях, но даже если не удалось их решить, не расстраивайтесь. Дайте их попробовать решить детям.