Олимп 8 класс
Готовься к олимпиаде по математике
Этот базовый курс олимпиадной математики для учащихся 8 класса включает в себя темы: разнобой; логика; движение; формула включений-исключений; комбинаторика: число перестановок, размещения, число сочетаний; разные задачи.
Олимпиадная математика — штука особенная, можно сказать, отдельная дисциплина. Ведь здесь на первое место выходят не аккуратность и умение считать, а нестандартные методы и подходы. Предлагаемые ниже материалы предназначены для учителей, а также для учащихся, которые желают стать настоящими чемпионами и не боятся нестандартных задач.
Задачи для знакомства
1. В бассейн размерами 20×100 метров налили 1000000 литров воды. Можно ли в нем устроить соревнования по плаванию? Ответ Решение5. Каждый день в 12:00 из Москвы во Владивосток и из Владивостока в Москву отправляется скорый поезд. Поезд идет ровно 7 суток. Пассажир выезжает из Владивостока. Сколько встречных поездов «Москва–Владивосток» он насчитает, пока приедет в Москву? Ответ Решение
Примечание: расписание движения поездов дальнего следования на всей территории России привязано к московскому времени.
Разнобой
1. Найти наименьшее натуральное число, которое после умножения на 2 становится квадратом, а после умножения на 3 — кубом целого числа. Решение Ответ- Поклоняетесь ли Вы богу Солнца?
- Поклоняетесь ли Вы богу Луны?
- Поклоняетесь ли Вы богу Земли?
Решение
6. На поле стояли 777 гангстеров, и все они находились на попарно различных расстояниях друг от друга. Гангстеры одновременно выхватили пистолеты и каждый выстрелил в ближайшего. Докажите, что хотя бы в одного гангстера никто не стрелял. Решение
Логика1.Кого больше: котов, кроме тех котов, которые не Васьки, или Васек, кроме тех Васек, которые не являются котами? Ответ Решение
«В этой тетради ровно одно неверное утверждение».
«В этой тетради ровно два неверных утверждения».
...
«В этой тетради ровно сто неверных утверждений».
Какие из написанных утверждений верные? Ответ Решение
6.Часть жителей некого острова всегда говорят правду, а остальные всегда лгут. Путешественник, оказавшийся на острове, в совершенстве владеет языком островитян, только не помнит, какое из двух слов «пиш» и «таш» означает «да», а какое — «нет». Путешественник дошёл до места, где дорога раздваивалась, причём одна из дорог ведёт в деревню, а другая — в болото. На распутье он встретил аборигена. Сможет ли путешественник, задав всего один вопрос (предполагающий ответ «да» или «нет», то есть «пиш» или «таш»), узнать, какая из двух дорог ведёт в деревню? Ответ Решение
7. a) Перед вами трое — лжец, честняга и хитрец (говорит правду или ложь по своему усмотрению), которые знают, кто из них кто. Как и вам это узнать? Вопросы можно задавать в любом количестве любому из троих.b) Перед вами четверо — лжец, честняга и два хитреца (все четверо знают, кто из них кто). Докажите, что хитрецы могут договориться отвечать так, что вы, спрашивая этих четверых, ни про кого из них не узнаете наверняка, кто он. Решение
Движение
При решении задач на движение лучше всего сразу обозначить все неизвестные величины переменными и записать условие при помощи уравнений. Помочь в этом может схема движения (пример ее составления приведен в решении задачи 5). Единственная формула, которая может понадобиться при составлении уравнений, — это определение скорости V = S/t (V — скорость, S — пройденный путь, t — время), а также получающиеся из него формулы S = V·t и t = S/V.
Следите за тем, чтобы все величины были выражены в одной системе единиц измерения. Если расстояния измеряются в метрах, а время в секундах, то скорость должна измеряться в метрах в секунду. Если же расстояния измеряются в километрах, а время в часах, то скорость должна измеряться в километрах в час. При составлении уравнений проверяйте, что в левой и правой частях стоят величины, измеряемые в одних и тех же единицах (чтобы не приравнивать, скажем, секунды и километры). При переводе величин из одной системы единиц в другую полезно помнить, что 10 м/с = 36 км/ч (проверьте это самостоятельно).
1. Водитель маршрутки знает: чтобы успеть доехать из Москвы в аэропорт «Шереметьево–2», не отстав от расписания, он должен ехать без остановок со скоростью 50 км/ч. Но поскольку на первой половине пути он попал в пробку, ему пришлось ехать со скоростью 25 км/ч. Однако на второй половине пути движение было свободное, и ему удалось проехать её со скоростью 100 км/ч. Успел ли он вовремя? Ответ РешениеФормула включений-исключений
1. Пусть P – множество прямоугольных треугольников, R – множество равнобедренных треугольников и S – множество равносторонних треугольников. Изобразите эти множества с помощью кругов Эйлера. Ответ
3. Докажите формулу включений – исключений для двух множеств:
|A∪B|=|A|+|B|-|A∩B|Решение
|A∪B∪C|=|A|+|B|+|C|-|A∩С|-|A∩B|-|C∩B|+|A∩B∩C|Решение
Комбинаторика
I. Перестановки n элементовДопустим, мы выбираем все n элементов из множества, содержащего n элементов, упорядоченным образом. Такие размещения n элементов называются перестановками n элементов. Число перестановок n элементов обозначается через Pn.
Утверждение. Pn = n!, где n! = 1·2·…·n — произведение всех натуральных чисел от 1 до n (читается «эн факториал»).
Доказательство. Будем строить произвольную перестановку n элементов. На первое место мы можем поставить любой из n элементов. После того, как первый элемент выбран, остается (n-1) способ выбрать второй элемент из оставшихся. Для каждого способа выбрать первый и второй элементы есть (n-2) способа выбрать третий элемент, и так далее. Если уже выбран (n-1) элемент перестановки, остается единственный способ выбрать последний элемент. Таким образом, чтобы посчитать количество возможных перестановок n элементов, нужно все эти числа перемножить: Pn = n·(n-1)·(n-2)·…·2· 1 = n!. Утверждение доказано.
1. Пусть у нас есть множество из n элементов, из которых мы хотим выбрать упорядоченные k различных элементов (то есть выбрать первый элемент, второй элемент и так далее вплоть до k-го). Каждый способ это сделать называется размещением без повторений. Способы считаются различными, если хотя бы на одном месте в них стоят различные элементы. Число таких способов называется числом размещений без повторений и обозначается Ank(читается: «а из эн по ка»).
Утверждение.
Ank | = | n·(n-1)·…·(n-k+1) | = | n! |
(n-k)! |
Докажите это утверждение самостоятельно по аналогии с предыдущим. Его доказательство в частном случае фактически проводится при решении задачи 3.2.
Следствие. Pn = Ann.
2. Число способов выбрать упорядоченные k элементов из n, если им разрешено повторяться, называется числом размещений с повторениями и обозначается как Ank. Формула для его нахождения приводится в ответе к задаче 3.7.
III. Сочетания из n элементов по k1. Мы выбираем из n элементов неупорядоченные k различных элементов. Каждый способ это сделать называется сочетанием из n элементов по k. Различные сочетания отличаются друг от друга составом, но не порядком элементов. Число сочетаний из n элементов по k (нетрудно заметить, что это в точности число подмножеств из k элементов в множестве из n элементов) обозначается Cnk. Формула для его нахождения приведена в задаче 4.2.
2. Допустим, что у нас есть n различных типов элементов. Тогда комбинация из k элементов, при условии, что элементы одного типа могут встречаться несколько раз и порядок элементов в комбинации не важен, называется сочетанием с повторениями из n элементов по k. Число сочетаний с повторениями обозначается Cnk. Формула для его нахождения приведена в задаче 4.6.
Задачи
Размещения3.1.На вершину горы ведут пять тропинок.a)Сколько у туриста есть способов подняться на гору и потом спуститься с нее?b)А если турист не хочет спускаться по той же дороге, по которой он поднимался? Ответ Решение3.2.Пираты подняли бунт и захватили корабль. Теперь им нужно выбрать из своих рядов капитана, его первого помощника и боцмана. Сколькими способами они могут это сделать, если пиратов:а) 4.b) 6.c) 20 и им ещё нужно выбрать кока? Ответ Решение3.3. Сколькими способами 15 пронумерованных бильярдных шаров могут распределиться по шести лузам? Ответ Решение
3.4. В комнате студенческого общежития живут трое студентов. У них есть 4 чашки, 5 блюдец и 6 чайных ложек (все чашки, блюдца и ложки отличаются друг от друга). Сколькими способами они могут накрыть стол для чаепития (то есть дать каждому студенту чашку, блюдце и ложку)? Ответ Решение
3.5.Сколькими способами можно выбрать на шахматной доске белое и черное поля, не лежащие на одной горизонтали или вертикали? Ответ Решение
3.6. Четверо студентов сдавали экзамен.a)Сколькими способами им могли быть выставлены оценки, если известно, что все студенты экзамен сдали (то есть получили 3, 4 или 5)?b)А если студентов было 10? Ответ Решение
3.7.Выведите формулу для нахождения Ank. Ответ Решение
3.8.Сколько слов (не обязательно осмысленных: «ьщерук» тоже считается словом), состоящих иза) трех;b) пяти;c) семи букв, можно составить из тридцати трех букв русского алфавита так, чтобы любые две стоящие рядом буквы были различны? Ответ Решение
3.9. Сколько можно составить из тридцати трех букв русского алфавита шестибуквенных слов, содержащих хотя бы одну букву «а»? Ответ РешениеПерестановки3.10. Сколько пятизначных чисел содержат все цифрыа) 1, 2, 3, 4, 5?b) 0, 2, 4, 6, 8? Ответ Решение3.11. В азбуке Морзе используются два типа символов: точки (·) и тире (—). Можно ли сопоставить каждой букве русского алфавита такой код, чтобы каждая буква оказалась зашифрована не более чем четырьмя символами азбуки Морзе? Ответ Решение
3.12. a) Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не били друг друга?b) А n ладей на доске размера n×n? Ответ Решение
3.13.Каких семизначных чисел больше: тех, в записи которых есть единица, или всех остальных? Ответ РешениеСочетания без повторений4.1.Сколькими способами можно выбрать баскетбольную команду (5 человек) иза) шести человек?b) семи человек?c) Сколько способов набрать две команды по пять человек из десяти претендентов? Ответ Решение4.2.Проверьте формулу
Cnk | = | Ank | = | n! | . |
k! | (n-k)! k! |
4.10. У Мальвины шестеро друзей, и в течении пяти дней она приглашает к себе в гости каких-то трех из них так, чтобы компания ни разу не повторилась. Сколькими способами она может это сделать? Ответ Решение4.11. Докажите, что в любой компании из шести человек обязательно найдутся трое, которые знакомы между собой, или трое, которые друг с другом не знакомы. Решение