Принцип Дирихле (Pigeonhole Principle, Dirichlet's Box Principle) в формулировке с кроликами и клетками:
Если в n клетках сидит n+1 кролик, то найдётся по крайней мере одна клетка, в которой сидят не менее двух кроликов.
1. Докажите, что если 21 кролик или больше посажены в 10 клеток, то в какой-то клетке находится по крайней мере 3 кролика.
2. В классе учится 25 учеников. Докажите, что найдутся 2 ученика, родившиеся в одном и том же месяце. Обязательно ли найдутся 3 таких ученика?
3. Из чисел 1, 2, ... , 49, 50 выбрали 26 чисел. Обязательно ли среди них найдутся два числа, отличающиеся друг от друга на 1?
4. Докажите, что из любых 11 натуральных чисел можно выбрать 2 числа, разность которых делится на 10.
Подсказка. Чисел 11 (это кролики), а возможных последних цифр (это клетки) только 10.
5. Докажите, что из любого 21 натурального числа можно выбрать 3 таких, разности которых делятся на 10.
6. Докажите, что из любых 10 натуральных чисел, ни одно из которых не делится на 10, можно выбрать такие 2 числа, разность которых делится на 10.
7. Докажите, что из любых 10 натуральных чисел можно выбрать несколько (возможно, одно), сумма которых делится на 10.
8. 15 ребят собрали 100 орехов. Докажите, что какие-то 2 из них собрали одинаковое число орехов.
9. Можно ли накрыть равносторонний треугольник двумя меньшими равносторонними треугольниками?
10. В равносторонний треугольник со стороной 1 бросили 5 точек. Докажите, что среди них найдутся две точки, расстояние между которыми не превышает 1/2.
11. В квадрат со стороной 4 бросили 5 точек. Докажите, что найдутся две точки, расстояние между которыми меньше 3.
Подсказка. Измерения показывают (и можно доказать), что в квадрате со стороной 2 диагональ меньше 3.
12. В квадрат со стороной 2 бросили 10 точек. Докажите, что найдутся две точки, расстояние между которыми меньше 1.
13. Докажите, что в квадратную коробочку со стороной 3 нельзя положить 10 монет диаметра 1 без наложений.
Подсказка. Допустим, что можно. Заметьте, что центры монет находятся в квадрате со стороной 2 и примените предыдущую задачу.
14. Докажите, что в данный момент на Земле живут два человека, которые родились в одну секунду.
Alpha (10–12 лет): задачи 1–5, 8–10; Beta (13–14 лет): все задачи.
Кузнечик
Кузнечик прыгает по целым точкам числовой прямой и всегда начинает свое путешествие из точки 0.
1. Кузнечик может прыгать на 3 и на 5 единиц длины как вперед, так и назад. Покажите, что он может попасть как в точку 1, так и в точку −1.
2. Покажите, что в ситуации задачи 1 Кузнечик может попасть в любую целую точку (то есть в точку числовой прямой, координата которой — целое число).
3. Что можно сказать про путешествия Кузнечика (см. задачи 1 и 2), если у него прыжки длиной: а) 4 и 6; б) 5 и 7; в) 6 и 9? Докажите свои утверждения.
Далее Кузнечик начинает свое путешествие из точки 0, но прыгает по числовой прямой только вперед (в положительном направлении). Точки, в которые он может попасть, называются достижимыми, а остальные — недостижимыми. Начальная точка 0 считается достижимой. Все отрицательные целые точки оказываются недостижимыми.
4. Кузнечик может прыгать вперед на 3 и на 5 единиц длины. Отметьте все достижимые точки. Докажите, что все точки, начиная с 8, оказываются достижимыми.
Пометим достижимую точку буквой A, а недостижимую — буквой B. Вот как расположатся пометки вблизи точки 0:
Первая слева буква A отмечает точку старта (точку 0). До нее слева буквы B отмечают недостижимые отрицательные точки. Нужно продолжить пометки вправо. Интересно, как там расположены буквы?
5. Кузнечик может прыгать вперед на 5 и на 7 единиц длины. Отметьте все достижимые точки (приведите слово из букв A и B). Начиная с какой достижимой точки все следующие за ней также будут достижимые?
6. Кузнечик может прыгать вперед на a и на b единиц длины, где a и b — взаимно простые числа (их наибольший общий делитель равен 1). Докажите, что есть замечательная точка, которая достижимая, стоит после недостижимой, а все следующие за ней точки тоже достижимые. Найдите формулу замечательной точки (зависимость ее координаты от a и b).
Интересно, как устроены множества достижимых и недостижимых точек?
7. Проверьте в случаях 4 и 5, что множества достижимых и недостижимых точек симметричны друг другу относительно некоторой точки. Докажите это утверждение в общем случае 6.
8. Опираясь на результат 7, подсчитайте в случае 6 количество положительных недостижимых точек.
О задачах. Кузнечик — исполнитель из учебника "Алгоритмика" для 5-7 классов. Близкая тема: алгоритм Евклида. Задача 4 в формулировке с трехкопеечными и пятикопеечными монетами — часто используемый пример на метод математической индукции: "Если первая в очереди женщина и за каждой женщиной стоит женщина, то все в очереди женщины".
Alpha (10-12 лет): задачи 1, 2, 3 и какое-то продвижение в задачах 4 и 5.
Beta (13-14 лет): задачи 4 и 5 и продвижения в задачах 6-8.
1. Кузнечик может прыгать на 3 и на 5 единиц длины как вперед, так и назад. Покажите, что он может попасть как в точку 1, так и в точку −1.
2. Покажите, что в ситуации задачи 1 Кузнечик может попасть в любую целую точку (то есть в точку числовой прямой, координата которой — целое число).
3. Что можно сказать про путешествия Кузнечика (см. задачи 1 и 2), если у него прыжки длиной: а) 4 и 6; б) 5 и 7; в) 6 и 9? Докажите свои утверждения.
Далее Кузнечик начинает свое путешествие из точки 0, но прыгает по числовой прямой только вперед (в положительном направлении). Точки, в которые он может попасть, называются достижимыми, а остальные — недостижимыми. Начальная точка 0 считается достижимой. Все отрицательные целые точки оказываются недостижимыми.
4. Кузнечик может прыгать вперед на 3 и на 5 единиц длины. Отметьте все достижимые точки. Докажите, что все точки, начиная с 8, оказываются достижимыми.
Пометим достижимую точку буквой A, а недостижимую — буквой B. Вот как расположатся пометки вблизи точки 0:
...BBBABBA...
Первая слева буква A отмечает точку старта (точку 0). До нее слева буквы B отмечают недостижимые отрицательные точки. Нужно продолжить пометки вправо. Интересно, как там расположены буквы?
5. Кузнечик может прыгать вперед на 5 и на 7 единиц длины. Отметьте все достижимые точки (приведите слово из букв A и B). Начиная с какой достижимой точки все следующие за ней также будут достижимые?
6. Кузнечик может прыгать вперед на a и на b единиц длины, где a и b — взаимно простые числа (их наибольший общий делитель равен 1). Докажите, что есть замечательная точка, которая достижимая, стоит после недостижимой, а все следующие за ней точки тоже достижимые. Найдите формулу замечательной точки (зависимость ее координаты от a и b).
Интересно, как устроены множества достижимых и недостижимых точек?
7. Проверьте в случаях 4 и 5, что множества достижимых и недостижимых точек симметричны друг другу относительно некоторой точки. Докажите это утверждение в общем случае 6.
8. Опираясь на результат 7, подсчитайте в случае 6 количество положительных недостижимых точек.
О задачах. Кузнечик — исполнитель из учебника "Алгоритмика" для 5-7 классов. Близкая тема: алгоритм Евклида. Задача 4 в формулировке с трехкопеечными и пятикопеечными монетами — часто используемый пример на метод математической индукции: "Если первая в очереди женщина и за каждой женщиной стоит женщина, то все в очереди женщины".
Alpha (10-12 лет): задачи 1, 2, 3 и какое-то продвижение в задачах 4 и 5.
Beta (13-14 лет): задачи 4 и 5 и продвижения в задачах 6-8.
Неравенства с фиксированной суммой
∗ В трёх пакетах находится 1 кг муки, причём в первом пакете муки не больше, чем во втором, а во втором — не больше, чем в третьем. Может ли во втором пакете быть 2/5 кг муки? 3/5 кг муки?
∗ (продолжение) Докажите, что в первом пакете, самое большее, 1/3 кг муки, а во втором, самое большее, — 1/2 кг муки.
∗ Какие значения может принимать средний по величине угол треугольника? Подсказка: сумма углов треугольника равна 180 градусам.
∗ Докажите, что в выпуклом пятиугольнике не может быть больше трёх острых углов.
∗ В четырёх мешках находится 12 кг муки, причём в первом мешке муки не больше, чем во втором, во втором мешке — не больше, чем в третьем, а в третьем — не больше, чем в четвёртом.
a) Докажите, что в третьем мешке не больше 6 кг муки.
b) Сколько, самое меньшее, может быть муки в четвёртом мешке?
c) Докажите, что во втором и третьем мешках вместе, самое большее, 8 кг муки.
d) Сколько, самое меньшее, может быть муки в первом и четвёртом мешках вместе?
Источник — статья В.Л.Гутенмахера Неравенства с фиксированной суммой в журнале Квант. Задание для детей 13–14 лет.
∗ (продолжение) Докажите, что в первом пакете, самое большее, 1/3 кг муки, а во втором, самое большее, — 1/2 кг муки.
∗ Какие значения может принимать средний по величине угол треугольника? Подсказка: сумма углов треугольника равна 180 градусам.
∗ Докажите, что в выпуклом пятиугольнике не может быть больше трёх острых углов.
∗ В четырёх мешках находится 12 кг муки, причём в первом мешке муки не больше, чем во втором, во втором мешке — не больше, чем в третьем, а в третьем — не больше, чем в четвёртом.
a) Докажите, что в третьем мешке не больше 6 кг муки.
b) Сколько, самое меньшее, может быть муки в четвёртом мешке?
c) Докажите, что во втором и третьем мешках вместе, самое большее, 8 кг муки.
d) Сколько, самое меньшее, может быть муки в первом и четвёртом мешках вместе?
Источник — статья В.Л.Гутенмахера Неравенства с фиксированной суммой в журнале Квант. Задание для детей 13–14 лет.
Занимательная арифметика
∗ На какие (натуральные) числа делятся числа (a) 1001, (b) 10101, (c) 10001, (d) 111111 ? Как можно упростить подсчёты?
∗ Вычислите: 111111111 × 111111111.
∗ Назовём действие простым, если это сложение или вычитание, умножение на 10 (приписывание справа нуля) или применение правила
12345678 × 9 + 9 = 111111111
123456789 × 8 + 9 = 987654321
объяснив, как можно посчитать левую часть с помощью простых действий.
∗ Поделите число 999999 на 7 и умножьте результат на числа 1, 2, 3, 4, 5, 6, получится 6 чисел. Проверьте, что они отличаются друг от друга перестановкой цифр по кругу.
∗ Аня может любой кусок хлеба поделить на две равные (по весу) части. Как ей поделить 7 хлебов между 8 людьми поровну?
Источник — книга Я.И.Перельмана "Занимательная арифметика". Задание для детей 10-12 лет.
∗ Вычислите: 111111111 × 111111111.
∗ Назовём действие простым, если это сложение или вычитание, умножение на 10 (приписывание справа нуля) или применение правила
a×c + b×c = (a + b)×c, a×c − b×c = (a − b)×c
(слева направо или наоборот). Докажите красивые равенства12345678 × 9 + 9 = 111111111
123456789 × 8 + 9 = 987654321
объяснив, как можно посчитать левую часть с помощью простых действий.
∗ Поделите число 999999 на 7 и умножьте результат на числа 1, 2, 3, 4, 5, 6, получится 6 чисел. Проверьте, что они отличаются друг от друга перестановкой цифр по кругу.
∗ Аня может любой кусок хлеба поделить на две равные (по весу) части. Как ей поделить 7 хлебов между 8 людьми поровну?
Источник — книга Я.И.Перельмана "Занимательная арифметика". Задание для детей 10-12 лет.
Subscribe to:
Posts (Atom)