Программа подготовки учащихся к олимпиадам

Государственное  бюджетное  общеобразовательное учреждение Республики Крым «Ливадийская санаторная школа-интернат»

Программа

подготовки учащихся к олимпиадам

Учитель математики Устинова О.В.

 

Пояснительная записка

Главная задача образовательной политики - обеспечение современного качества образования на основе сохранения его фундаментальности и соответствия актуальным и перспективным потребностям личности, общества и государства. Модернизация общеобразовательной школы предполагает ориентацию образования не только на усвоение определенной суммы знаний, но и на развитие личности, ее познавательных и созидательных способностей.

Проведение  олимпиад позволяет выявить учащихся, имеющих интерес и склонности занятиям математикой.

Решение задач является важнейшим средством формирования у школьников системы основных математических знаний, умений, навыков; ведущей формой учебной деятельности учащихся в процессе изучения математики; одним из факторов их математического и личностного развития. Эффективное использование задач в процессе обучения в значительной мере определяет не только качество обучения математике, но и их воспитание, развитие индивидуальных сущностных качеств и степень их практической подготовленности к деятельности в различных сферах экономики, политики, науки, искусства.

Курс  призван способствовать интеллектуальному развитию учащихся; сформировать у учащихся знания и умения, которые необходимы в повседневной жизни.  Он призван повысить мотивацию учащихся в обучении предмету; развивать познавательные интересы; расширение знаний по математике, полученных на уроках, на развитие креативных способностей учащихся и более качественной отработке математических умений и навыков, при решении олимпиадных задач по математике, способности самостоятельно добывать знания.

Преподавание данного курса направлено на достижение следующих целей:

Ø  Создать условия для интеллектуального развития учащихся.

Ø  Оказание помощи в воспитании культуры математического мышления;

Ø  Способствовать повышению интереса  к предмету и накоплению определенного запаса математических фактов и сведений, умений и навыков, приобретаемых  в основном курсе математики

Ø  Научить самостоятельно, добывать знания из дополнительной литературы

Курс «Подготовка учащихся к олимпиаде по математике» решает следующие задачи:

Ø  Создать условия для развития исследовательских навыков в работе;

Ø  Создать условия для систематизации и обобщения знаний, полученных на уроках геометрии по наиболее сложным темам, которые чаще всего встречаются в олимпиадных задачах по геометрии (задачи на построение, подобие фигур, окружность, площади, наименьшее и наибольшее значение величин);

Ø  Создать условия для формирования логических навыков в работе, в том числе умение обобщать, систематизировать полученную в результате исследовательской работы информацию;

Ø  Создать условия для формирования представлений об идеях и методах математики.

Ожидаемые результаты обучения.

Учащиеся должны уметь:

ü  применять нестандартные методы при решении программных задач;

ü  выполнять дополнительные построения на чертеже, способствующие поиску решения геометрических задачи

ü  решать задачи на построение

ü  рассуждать при решении логических задач, задач на смекалку и интуицию;

ü   логически обосновывать суждения, выдвигать гипотезы и понимать необходимость их проверки;

ü   аргументировать собственную точку зрения;

ü  умение оценивать достоверность полученной информации.

В результате изучения курса обучающиеся должны знать :

ü  нестандартные методы решения различных математических задач;

ü  логические приемы, применяемые при решении задач;

ü  широту применения математической теории на практике;

ü  проводить проверку найденных результатов;

ü  смысл идеализации, позволяющей решать задачи реальной действительности математическими методами.

Содержание.

1. Алгебраические методы в олимпиадных задачах

В ходе изучения этого модуля учащиеся отработают навыки по решению оригинальных и интересных олимпиадных задач алгебраическими методами . Решаются основные типы олимпиадных задач по математике: задачи на переливание, различные виды текстовых задач, задачи на применение специальных методов решений (применение принципа Дирихле, метода инвариантов, метода раскрасок, графов и др.); задачи, использующие программный материал, но повышенной трудности (арифметические задачи, алгебраические задачи); комбинированные задачи, задачи на комбинаторику и теорию вероятностей, а так же логические задачи .

2. Геометрические методы в олимпиадных задачах

В ходе изучения этого модуля учащиеся обобщают и систематизируют знания, умения и навыки по решению олимпиадных задач по геометрии. Решают олимпиадные геометрические задачи следующих типов: на разрезания, на построение, на нахождение углов, на доказательство, на вычисление площадей фигур, задачи, в которых используют идею дополнительного построения .

5-6 класс

Тема 1:«Разминка»

 1. Вставьте недостающее число. Ответ: 11

2. Вставьте пропущенное число. Ответ: 21

196 (25) 324

325 (    ) 137

3. Продолжите ряд чисел. Ответ: 3

18 10  6  4  ?

Тема 2: «Магический квадрат».    

 Великие ученые древности считали количественные отношения основой сущности мира. Поэтому числа и их соотношение занимали величайшие умы человечества. «В дни моей юности я в свободное время развлекался тем, что составлял… магические квадраты» - писал Бенджамин Франклин. Магический квадрат – это квадрат, сумма чисел которого в каждом горизонтальном ряду, в каждом вертикальном ряду и по каждой диагоналей одна и та же.       Полного описания всех возможных магических квадратов не получено и до сего времени. Магический квадрат 2x2 не существует.

Задача 1. Расставьте цифры от 1 до 4, так, чтобы цифры в каждой строке и в каждом столбце не повторялись.

2		1
3
			2

Ответ: 

2	4	1	3
3	1	2	4
1	3	4	2
4	2	3	1

Задача 2. В клетках квадрата 3x3 были записаны натуральные числа так, чтобы они образовывали магический квадрат. Некоторые числа стерли, восстановите квадрат.

	15	9
		24

Ответ:            9 + 24 = 15 + х (сходятся с верхней справа ячейке), х = 18; 9 + 15 = 18 + у (сходятся в центральной слева ячейке), у = 6. Таким образом, сумма по диагонали – 45, откуда получаем оставшиеся ячейки.

6	27	12
21	15	9
18	3	24

Задача 3. Разместите в свободных клетках квадрата числа 3, 4, 5, 6, 8, 9 так, чтобы по любой вертикали, горизонтали и диагонали получилось в сумме одно и тоже число.

10
	7
	11

Ответ:

10	3	8
5	7	9
6	11	4

Тема 3: Задачи по арифметике.

Арифметика – раздел математики, занимающийся изучением свойств числа, вопросами происхождения и развития понятия «число», свойствами операций и отношений в числовых множествах и их анализу.

Арифметические задачи таят огромные возможности для того, чтобы научить решающих их школьников самостоятельно думать, анализируя неочевидные жизненные ситуации, приходя к пониманию первопричин разных явлений природы и жизни, а также к оценке возможных последствий принимаемых решений. Обучение арифметике включает в качестве одного из основных элементов воспитание умения ориентироваться в различных по своей природе взаимоотношениях между величинами.

Примеры:

1)   арифметические задачи для простой формулы 3-1=2:

·      Сколько распилов делят бревно на 3 части?

·      На сколько число братьев в Таниной семье больше числа сестёр, если у Тани на 3 брата больше, чем сестёр?

·      Сколько сотен лет назад основан университет, который будет через 100 лет праздновать свой трёхсотлетний юбилей?

2)   Из стакана с молоком перелили ложку в банку с чаем, а потом такую же ложку смеси перелили обратно в стакан. Чего больше в результате: молока в банке с чаем или чая в стакане молока?

3)   Если продать 20 коров, то заготовленного сена хватит на 10 дней дольше, если же прикупить 30, то запас сена исчерпается на 10 днями раньше. Сколько было коров и на сколько дней заготовлено сено?

4)   Пароход идёт вниз по течению 2 часа, вверх – 3 часа. Сколько времени между теми же двумя пунктами вниз по течению проплывёт бревно?

Задача 1. Замените значки * в выражении 13*11*9*7*5*3*1 = 1 на знаки + и – так, чтобы получилось верное равенство.

 Ответ: Три варианта: 13 – 11 + 9 – 7 – 5 + 3 – 1 = 1, 13 – 11 – 9 + 7 + 5 – 3 – 1 = 1 и

13 + 11 – 9 – 7 – 5 – 3 + 1 = 1.

Сумма 13 + 11 равна сумме чисел 9, 7, 5 и 3, поэтому если первая звездочка заменена на «+», то возможен только один вариант (третий). Если эта звездочка заменена на «–», а вторая – на «+», то третья уже не может заменяться на «+», так как 13 – 11 + 9 + 7 > 5+ 3 + 1 + 1, и мы получаем первый вариант. Наконец, если первые две звездочки заменены на «–», то третья должна заменяться на «+», и мы получаем второй вариант.

Задача 2. Найдите все трёхзначные числа, у которых вторая цифра вчетверо больше первой, а сумма всех трёх цифр равна 14.

Ответ: 149 и 284.

Если первая цифра не меньше 3, то вторая – не меньше 12, что невозможно. Значит, первая цифра 1 или 2. Далее число стоится однозначно.

Понятие натурального числа было вызвано потребностью счета предметов. Еще в доисторические времена. Анализ языков первобытных  народностей показывает, что для счета предметов употреблялись различные словесные обороты. Слово «три» передавалось различно,  например, «три человека», «три лодки», а большие числа означали «куча», «толпа» и т.д. Все натуральные числа можно разбить на два множества: множество четных чисел и множество нечетных чисел. Четные числа нацело делятся на 2, а нечетные не делятся.

При решении задач, в которых используются свойства четности, важно помнить следующие правила:

1. Сумма и разность двух нечетных чисел является четным числом.

2. Сумма и разность двух четных чисел является четным числом.

3. Сумма и разность двух чисел, одно из которых четное, а другое нечетное, является нечетным числом.

4. Произведение двух нечетных чисел является нечетным числом.

5. Произведение двух чисел, из которых одно четное, является четным числом.

Задача 3. Вычеркните в числе 4000538 пять цифр так, чтобы оставшееся число стало наибольшим.

Ответ: 58

Задача 4. Коля открыл книгу и обнаружил, что сумма номеров левой и правой страниц – 25. Чему равно произведение этих номеров?

Ответ: Так как левая и правая страницы, то номер правой на 1 больше номера левой. (25 – 1) : 2 = 12. Значит, это страницы 12 и 13, 12 ∙ 13 = 156.

Задача 5. Света выполнила действия: 1997 ∙ 1999 ∙ 2001 – 1998 ∙ 2000. Какова последняя цифра ответа?

Ответ: Произведение 1997 ∙ 1999 ∙ 2001 оканчивается цифрой 3, поскольку 7 ∙ 9 ∙1 = 63. Произведение 1998∙2000 оканчивается 0, следовательно, результат оканчивается цифрой 3.

 Задача 6. Маша выбрала двузначное число, не делящееся на 10, поменяла его цифры местами и вычислила разность полученных чисел. Какое самое большое число она могла получить?

Ответ: Уменьшаемое должно быть наибольшим, а вычитаемое наименьшим. Это будет для чисел 90 – 9 = 81. В этом решении, меняя цифры числа 90, получаем 09,  т.е. 9. Но число не должно делиться на 10, значит это число 91 и 19, 91 – 19 = 72.

Тема 4: Математические ребусы.

Математическими ребусами называют задания на восстановление записей вычислений. Условие математического ребуса содержит либо целиком зашифрованную запись (цифры заменены буквами), либо только часть записи (стертые цифры заменены точками или звездочками). Записи восстанавливаются на основании логических рассуждений. При этом нельзя ограничиваться отысканием только одного решения. Испытание нужно доводить до конца, чтобы убедиться, что нет других решений, или найти все решения. Есть математические ребусы, имеющие несколько решений.

Задача 1. Расшифруйте два ребуса, в которых одинаковым буквам соответствуют одинаковые цифры, а разным буквам – разные цифры в обоих примерах.

   АБВ                          АБВ

⁺    ВВ                         ВВ        

   ААБ                         АБВ

                                ⁺АБВ   

                                 АГАВ  

Ответ:   А = 3, Б = 2, В = 1, Г = 5. Получим 321 + 11 = 332, 321∙ 11 = 3531.

Задача 2. Восстановите поврежденную запись

Ответ. 99 + 9 = 108

Задача 3. Решите ребус

Решение:

Очевидно, Д≤4. В разряде сотен имеем А + А = А, значит, А = 0 (без перехода) или А = 9 (с переходом). Значение А = 0 не подходит, так как в разряде единиц А + А = Р (получаем А = Р = 0). Значит, А = 9, Р = 8, Е = 7. Тогда 2М + 1 = 10 + Т, Т < 9, значит М = 5 или 6 (так как получается переход), а значения 7 и 8 уже заняты буквами Е и Р. При М = 6 получается решение:18969+18969=37938.
Ответ. 18969 + 18969 = 37938.

Задача 4. Решите ребус

Ответ.54271 + 54271 = 108542

Тема 5: Задачи на разрезание и складывание фигур.

 «Семь раз отмерь, один раз отрежь!» Эта пословица предостерегает вас от поспешности в решении задач. Заданную фигуру, которая для облегчения работы часто разделена на  равные клеточки, надо разрезать на две или несколько одинаковых частей. Если эти части можно наложить одну на другую так, что они совпадут (при этом разрешается переворачивать их наизнанку), то задача решена верно.

Задача 1. Попробуйте разрезать изображенную на рисунке фигуру на 3 равные по форме части:

                                                          Ответ: Маленькие фигуры очень похожи на букву Т.
                 

Задача 2. Разрежьте теперь эту фигуру на 4 равные по форме части:
                                        

Ответ:     Легко догадаться, что маленькие фигурки будут состоять из 3 клеточек, а фигур из трех клеточек не так много. Их всего два вида: уголок и прямоугольник 1×3. 

Комментарий: подсчитаем количество клеток в маленькой фигуре. Оно равно 12:4=3. Но из трех клеток можно составить только лишь 2 вида фигур: прямоугольник размером 1×3 и уголок из трех клеток. Недолгим перебором легко убедимся, что на четыре прямоугольника данную фигуру разрезать не получится. Поэтому нам необходим уголок из трех клеток. Именно с такими частями и будем искать разбиение. Если эта часть не будет упираться в угол целой фигуры, то в самой ее крайней точке останется одна клетка. Это недопустимо. Следовательно, уголки нужно вставить в три больших угла первоначальной фигуры, а последний уголок вставить в ее середину. Получим:

Задача 3. Разрежьте данную фигуру на 5 равных по форме частей:

Ответ: Найдите количество клеточек, из которых состоит каждая такая фигура. Эти фигурки, похожи на букву Г.

Задача 4. А теперь нужно разрезать фигуру из десяти клеток на 4 неравных друг другу прямоугольника (или квадрата).

Указание: Выделите какой-нибудь прямоугольник, а затем в оставшиеся клетки попробуйте вписать еще три. Если не получается, то смените первый прямоугольник и попробуйте еще раз.

Ответ:

Задача 5. Разрежьте эту фигуру на 5 фигур из четырех клеток разной формы таким образом, чтобы в каждой их них была закрашена только одна зеленая клетка.
 Указание: Попробуйте начать разрезание с верхнего края данной фигуры и вы сразу поймете, как действовать.

Ответ:

Задача 6. Разрежьте квадрат из 16 клеток на 4 равные по форме части так, чтобы в каждой из четырех частей была ровно одна зеленая клетка.
 Указание: Вид маленьких фигурок не квадрат и не прямоугольник, и даже не уголок из четырех клеток. Так на какие же фигуры надо попытаться разрезать?

Ответ:

Тема 6:Логические задачи. Задачи, решаемые с конца.

Задача 1. Задуманное число.

 Я задумала число, умножила его на два, прибавила три и получила 17. Какое число я задумала?

Решение:

17 – 3 = 14 – число до прибавления 3.
14 : 2 = 7 – искомое число.
Ответ. 7 – искомое число.

Задача 2. Алла Пугачева и Кристина Орбакайте.

 Алле Пугачевой и ее дочери Кристине Орбакайте вместе 98 лет. Кристина родилась, когда Алле Пугачевой было 22 года. Какого возраста обе певицы?

Решение:

Так как Кристина родилась тогда, когда Алле Пугачевой было 22 года, то разница в их возрасте будет 22 года. Тогда 98 – 22 = 76 (лет) – будет удвоенный возраст Кристины, а значит, Кристине Орбакайте 38 лет, а Алле Пугачевой 60 лет.
Ответ. Алле Пугачевой 60 лет, Кристине Орбакайте 38 лет.

Задача 3. Маша и медведи.

 Маша принесла своим друзьям медведям торт. Известно, что старший медведь съедает торт за 2 дня, средний медведь – за 3 дня, младший медведь – за 6 дней. За сколько дней три медведя вместе съедят торт?

Решение:

Так как старший медведь съедает торт за 2 дня, то за 1 день он съедает 12 торта.
Так как средний медведь съедает торт за 3 дня, то за 1 день он съедает 13 торта.
Так как младший медведь съедает торт за 6 дней, то за 1 день она съедает 16 торта.
Вместе все три медведя за 1 день съедят 12+13+16=1, то есть один торт.
Ответ. За 1 день.

Задача 4. Яблоки.

Трое мальчиков имеют по некоторому количеству яблок. Первый мальчик дает другим столько яблок, сколько каждый из них имеет. Затем второй мальчик дает двум другим столько яблок, сколько каждый из них теперь имеет; в свою очередь и третий дает каждому из двух других столько, сколько есть у каждого в этот момент. После этого у каждого из мальчиков оказывается по 8 яблок. Сколько яблок было у каждого мальчика вначале?

Решение:

Решаем задачу с конца с помощью таблицы.

Номер мальчика	1	2	3
Число яблок в конце	8	8	8
Число яблок до передачи их третьим мальчиком	8 : 2 = 4	8 : 2 = 4	8 + 8 + 4 = 16
Число яблок до передачи их вторым мальчиком	4 : 2 = 2	4 + 2 + 8 = 14	16 : 2 = 8
Число яблок первоначально	2 + 4 + 7 = 13	14 : 2 = 7	8 : 2 = 4

Таким образом, первоначально яблок у первого, второго и третьего мальчиков было соответственно 13, 7 и 4.
Ответ. 13 яблок, 7 яблок, 4 яблока.

Задача 5. Туристы.

Группа туристов отправилась в поход. В первый день они прошли 1/3 пути, в второй - 1/3 остатка, в третий - 1/3 нового остатка. В результате им осталось пройти 32 км. Сколько километров был маршрут туристов?

Решение:

Решаем задачу с конца.
Так как осталось 32 км, а в третий день туристы прошли остаток, то 32 км будут составлять последнего 2/3 остатка, тогда сам последний остаток будет равен 32 : 2/3 = 48 (км). Эти 48 км будут составлять 2/3 длины маршрута, оставшегося пройти после первого дня. Тогда весь маршрут, который осталось пройти, будет равен 48 : 2/3 = 72 (км). Эти 72 км составляют вновь 2/3, но уже всего маршрута туристов, а значит, весь маршрут будет равен 72 : 2/3 = 108 (км). Задача решена.
Ответ. 108 км

Задача 6. Крестьянин и царь.

Крестьянин пришел к царю и попросил: «Царь, позволь мне взять одно яблоко из твоего сада». Царь ему разрешил. Пошел крестьянин к саду и видит: весь сад огорожен тройным забором. Каждый забор имеет только одни ворота, и около каждых ворот стоит страж. Подошел крестьянин к первому стражу и сказал: «Царь разрешил мне взять одно яблоко из сада». «Возьми, но при выходе должен будешь отдать мне половину яблок, что возьмешь, и еще одно», - поставил условие страж. Это же повторили ему второй и третий, которые охраняли другие ворота. Сколько яблок должен взять крестьянин, чтобы после того, как отдаст положенные части трем стражам, у него осталось одно яблоко?

Решение:

Решаем задачу с конца. Перед последними воротами у крестьянина должно остаться (1 + 1) ∙ 2 = 4 яблока, перед вторыми – (4 + 1) ∙ 2 = 10, и перед первыми – (10 + 1) ∙ 2 = 22 яблока.
Ответ. 22 яблока.

Тема 7: Задачи типа "Кто есть кто?"

Задачи типа «Кто есть кто?» - это самые что ни на есть логические задачи. Льюис Кэрролл очень любил создавать такие, и непрерывно потчевал ими своих студентов, так как был профессором математики. Но вы можете сколько вашей душе угодно решать логические задачи, развивая свою память и интеллект.
Смысл задач под кодовым названием «Кто есть кто?» довольно прост. Вам даны отношения между предметами и следуя по цепочке этих отношений, вы приходите к правильному результату. Существует несколько методов решения задач типа «Кто есть кто?». Один из методов решения таких задач – метод графов. Второй способ, которым решаются такие задачи – табличный способ. Граф – это несколько точек, часть которых соединены друг с другом отрезками или стрелками (в этом случае граф называется ориентированным).
Рассмотрим метод графов на примере решения задачи.

Задача.  Любимые мультфильмы.

Жила-была одна дружная семья: мама, папа и сын. Они все любили делать вместе. Но вот мультфильмы любили разные: «Ну, погоди!», «Покемоны», «Том и Джерри». Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам?

Решение. Рассмотрим множество людей: мама, папа, сын и множество мультфильмов «Ну, погоди!», «Покемоны», «Том и Джерри». Обозначим элементы этих двух множеств точками:

Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует – то штриховой.
Заметим, что по условию задачи у человека только один любимый мультфильм.
Учитывая данные задачи, получаем следующую схему:

Из условия задачи следует, что нужно найти единственно возможное соответствие между элементами двух множеств.

Правило: если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной. Поэтому граф на рисунке будет выглядеть следующим образом:

Теперь мы установили, что папа любит мультфильм «Ну, погоди!», сын – «Покемоны». В обеих множествах остается только по одной точке, следовательно мама любит мультфильм «Том и Джерри». Задача решена. Таким же способом можно находить соответствие между тремя множествами. Тогда при решении мы можем получить треугольники трех видов:

а) все стороны являются сплошными отрезками (решение задачи);
б) одна сторона – сплошной отрезок, а две другие – штриховые;
в) все стороны – штриховые отрезки.

Таким образом, нельзя получить треугольник, у которого бы две стороны были сплошными отрезками, а третья – штриховой отрезок. Второй способ, которым решаются такие задачи - табличный способ.

Табличный способ решения логических задач также прост и нагляден, но его можно использовать только в том случае, когда требуется установить соответствие между двумя множествами. Он более удобен, когда множества имеют по пять-шесть элементов. Рассмотрим табличный способ на примере решения задачи. Рассмотрим табличный способ на примере решения задачи.

Задача. Футбол.

Четыре футбольных команды: итальянская команда «Милан», испанская – «Реал», российская – «Зенит», английская – «Челси» встретились в групповом этапе лиги чемпионов по футболу. Их тренировали тренеры из этих же четырех стран: итальянец Антонио, испанец Родриго, русский Николай, англичанин Джон. Известно, что национальность у всех четырех тренеров не совпадала с национальностью команд. Требуется определить тренера каждой команды, если известно:

а)Зенит не тренируется у Джона и Антонио.
б)Милан обещал никогда не брать Джона главным тренером.
Решение.
Решая задачу, мы заведомо знаем, что у каждой команды только один тренер.
Чтобы решить задачу табличным способом, нужно знать следующие правила:
1.В каждой строке и в каждом столбце таблицы может стоять только один знак соответствия (например«+»).
2.Если в строке (или столбце) все «места», кроме одного, заняты элементарным запретом (знак несоответствия, например «-»), то на свободное место нужно поставить знак «+»; если в строке (или столбце) уже есть знак «+», то все остальные места должны быть заняты знаком «-». Таким образом, решение будет доведено до конца, когда мы сумеем разместить по одному плюсу в каждом ряду и колонке, обозначив, таким образом, тренеров всех четырех команд.
А теперь приступаем к решению задачи. Нам известно, что ни у одной из команд национальность тренера и команды не совпадали, а также, что «Зенит» не тренируется у Джона и Антонио, значит у этой команды тренер не Джон и не Антонио; а «Милан» обещал никогда не брать Джона тренером, значит у команды «Милан» тренер не Джон. Если проставить соответствующие минусы, то таблица будет выглядеть так:

Команда	Италия – «Милан»	Испания – «Реал»	Россия – «Зенит»	Англия – «Челси»
Тренер
Итальянец Антонио	-		-
Испанец Родриго		-
Русский Николай			-
Англичанин Джон	-		-	-

Таким образом, становится ясно, что у «Зенита» тренер Родриго (методом исключения). Поставим «+» напротив Родриго в колонке «Зенит» и заполним свободные клетки в его ряду минусами:

Команда	Италия – «Милан»	Испания – «Реал»	Россия – «Зенит»	Англия – «Челси»
Тренер
Итальянец Антонио	-	-	-	+
Испанец Родриго	-	-	+	-
Русский Николай	+	-	-	-
Англичанин Джон	-	+	-	-

Теперь можно сделать вывод, что тренер «Милана» – Николай. Поставим «+» напротив Николая и заполним свободные клетки в его ряду минусами. Теперь видно, что «Челси» тренирует Антонио, а «Реал» - Джон.

Ответ. Российская команда «Зенит» тренируется у испанца Родриго; итальянская команда «Милан» тренируется у русского Николая; английская команда «Челси» тренируется у итальянца Антонио; испанская команда «Реал» тренируется у англичанина Джона.

Задача 1. В кругу сидят Иванов, Петров, Марков и Карпов. Их имена Андрей, Сергей, Тимофей и Алексей. Известно, что:

1. Иванов не Алексей и не Андрей.

2. Карпов не Сергей и не Алексей.

3. Сергей сидит между Марковым и Тимофеем.

4. Петров сидит между Карповым и Андреем.

Назовите имя и фамилию каждого.

Ответ:

	Андрей	Сергей	Тимофей	Алексей
Иванов	-	+	-	-
Петров	-	-	-	+
Марков	+	-	-	-
Карпов	-	-	+	-

Задача 2.

 В компьютерном классе на уроке информатики, во время отсутствия учителя, пять ребят – Максим, Настя, Саша, Рома, Сережа – отвлеклись от нужной работы и стали играть в такие игры: пасьянс «Паук», гонки, сапер, «Марио», тетрис. Каждый из них играл только в одну игру.
• Саша думал, что в «Марио» играет Настя.
• Настя предполагала, что Рома играет в тетрис, а Максим – в гонки.
• Рома считал, что Сережа играет в гонки, а Саша – в сапера.
• Максим думал, что Настя раскладывает пасьянс «Паук», а в «Марио» играет Рома.
В результате оказалось, что все они ошиблись в своих предположениях. Кто и во что играл?

Решение:

Имя	Максим	Настя	Саша	Рома	Сережа
Игра
Пасьянс «Паук»	-	-	-		-
Гонки	-	-	+	-	-
Сапер			-	-	-
«Марио»	-	-	-	-	+
тетрис		-	-	-	-

Теперь становится ясно, что в пасьянс «Паук» играл Рома, в сапера – Настя, а в тетрис Максим. Задача решена.
Ответ. Сережа играл в «Марио»; Рома – в пасьянс «Паук»; Саша – в гонки; Настя – в сапера; Максим – в тетрис.

Задача 3.

Жили-были на свете три поросёнка, три брата: Ниф-Ниф, Наф-Наф, Нуф-Нуф. Построили они три домика: соломенный, деревянный и кирпичный. Все три брата выращивали возле своих домиков цветы: розы, ромашки и тюльпаны. Известно, что Ниф-Ниф живет не в соломенном домике, а Наф-Наф – не в деревянном; возле соломенного домика растут не розы, а тот, у кого деревянный домик, выращивает ромашки. У Наф-Наф аллергия на тюльпаны, поэтому он не выращивает их. Узнайте, кто в каком домике живет и какие цветы выращивает.

Решение: Из условий задачи получаем граф:

Можно сделать вывод, что возле кирпичного домика растут розы, а возле соломенного – тюльпаны. А так как Наф-Наф живет не в деревянном домике, то он и не выращивает ромашки. А так как на тюльпаны у него аллергия, то он может выращивать только розы. Внесем эти данные в чертеж и получим:

Теперь стало ясно и то, что Ниф-Ниф живет в деревянном домике и выращивает ромашки. Методом исключения получаем, что Нуф-Нуф живет в соломенном домике и выращивает тюльпаны.
Ответ. Наф-Наф живет в кирпичном домике и выращивает розы; Ниф-Ниф живет в деревянном домике и выращивает ромашки; Нуф-Нуф живет в соломенном домике и выращивает тюльпаны.

Задача 4. Атос, Портос, Арамис и Д’Артаньян – четыре талантливых молодых мушкетёра. Один из них лучше всех сражается на шпагах, другой не имеет равных в рукопашном бою, третий лучше всех танцует на балах, четвертый без промаха стреляет с пистолетов. О них известно следующее:

1. Атос и Арамис наблюдали на балу за их другом – прекрасным танцором.

2. Портос и лучший стрелок вчера с восхищением следили за боем рукопашника.

3.Стрелок хочет пригласить в гости Атоса.

4. Портос был очень большой комплекции, поэтому танцы были не его стихией.
Кто чем занимается?

Ответ:

Занятие	шпажист	рукопашник	танцор	стрелок
Имя
Атос	-	+	-	-
Портос	+	-	-	-
Арамис	-	-	-	+
Д’Артаньян	-	-	+	-

Теперь можно сделать вывод, что стрелок – это Арамис, рукопашник – Атос.
Ответ. Арамис – стрелок; Д’Артаньян – танцор; Портос – шпажист; Атос – рукопашник.

Тема 8:Принцип Дирихле.

При решении задач на доказательство применяется специальный метод, получивший название: принцип Дирихле. Петер Густав Лежен Дирихле (1805 – 1859) – великий немецкий математик, изучал арифметику, математический анализ, механику и математическую физику. В самой несерьезной и простой форме принцип Дирихле выглядит так: «Нельзя посадить семерых зайцев в три клетки так, чтобы в каждой клетке находилось не больше двух зайцев». Действительно, если в каждую клетку посадить не больше двух зайцев, то всего будет не больше 6 зайцев, что противоречит условию. 

Однако в каждой задаче не всегда удается легко понять, что играет роль «зайцев», а что выступает в роли «клеток». И почему надо, чтобы «зайцев» было больше, чем «клеток».

Задача. В классе 20 человек. Вася Кроликов в диктанте сделал 8 ошибок, остальные – меньше. Докажите, что, по крайней мере, 3 ученика сделали ошибок поровну (может быть по 0 ошибок).

Решение: В этой задаче «зайцы» - ученики, «клетки» - количество сделанных ошибок. Посадим в клетку «0» всех, кто не сделал ни одной ошибки, в клетку «1» - кто сделал одну ошибку, и так до клетки «8», куда попал Вася.

Теперь применим принцип Дирихле. Докажем утверждение от противного. Пусть никакие три ученика не сделали по одинаковому количеству ошибок. Тогда в клетки «0», «1», …, «7» попало меньше трех учеников (два или меньше). Всего ребят не более 14, добавив Васю, все равно не наберем 20 учеников. Противоречие. Значит, предположение «никакие три ученика не сделали по одинаковому количеству ошибок» неверно. Т.е. по крайней мере трое учеников сделали ошибок поровну.

Задача 1. В классе 22 ученика. Можно ли утверждать, что среди них найдутся хотя бы два ученика, фамилии которых начинаются с одной буквы.

Решение: Пусть «зайцы» - это ученики, «клетки» - буквы. В алфавите 33 буквы. Фамилии не могут начинаться с мягкого и твердого знаков, значит, остается 31 буква. Получается, что «клеток» (31) больше, чем «зайцев» (22). Принцип Дирихле нельзя применить. Поменяем «клетки» и «зайцев». По принципу Дирихле найдутся две буквы, с которых может начинаться фамилия какого-нибудь ученика, следовательно, каждый ученик имеет свою собственную букву. Ответ на вопрос задачи – «нет».

Задача 2. В классе 30 человек. Саша Иванов в диктанте сделал 13 ошибок, а остальные – меньше. Докажите, что по крайней мере 3 ученика сделали ошибок поровну (работа может быть и безошибочной).

0

1

2

3

4

5

6

7

8

9

10

11

12

13

Решение: Предположим, что никакие  3 ученика не сделали одинаковое число ошибок, т.е. в каждую клетку от 0 до 12 попало меньше трех школьников. Тогда в классе не больше 2*13+1=27, а в классе 30 учеников. Значит, наше предположение неверно. Поэтому найдутся три ученика, сделавшие одинаковое число ошибок.

Задача 3. В хвойном лесу 800 000 елей, и ни на одной из них не более 500 000 игл. Докажите, что по крайней мере у двух елей число игл одинаковое.

Решение: Пусть в одну клетку попали ели с одинаковым числом иголок 0; 1; 2; … 500 000. Если в каждой клетке по одной ели, то их 1*500 000=500 000, а  в лесу – 800 000. Значит, хотя бы у двух елей число игл одинаковое.

Задача 4. В городе 15 школ. В них обучается 6015 школьников. В концертном зале городского Дворца культуры 400 мест. Докажите, что найдется школа, ученики которой не поместятся в этом зале.

Решение: Предположим, что в каждой школе не более 400 учеников. Значит, в 15 школах не более 15*400=6000 школьников. Но, по условию, в школах обучается 6015 человек. Значит, найдется школа, в которой  больше 400 учеников. Поэтому ученики этой школы не поместятся в зале на 400 мест.

Задача 5. У мальчика 9 медных монет. Докажите, что у него есть хотя бы три монеты одинакового достоинства.

Решение: Всего различных медных монет 4. Пусть мальчик имеет набор по 2 монеты каждого вида, всего будет 8 монет. Оставшаяся  монета из 9 имеющихся,  будет третьей монетой одного из видов. Значит, у мальчика есть хотя бы 3 монеты одинакового достоинства.

Тема 9:Задачи на переливание.

Задача. Имеется 2 сосуда – 3 л и 5 л. Нужно, пользуясь ими, налить 1 л воды.

Решение: Наполним 3 л, перельем в сосуд 5 л, затем нальем ещё раз 3 л в сосуд и перельем 2 л в сосуд 5 л до полного. В трехлитровом сосуде остался один литр.

Задача 1. Имеются 2 сосуда – 3 л и 5 л. Как с их помощью получить 4 л воды?

Решение:

 1 способ

Сосуд 5 л	5 л	2 л	2 л	-	5 л	4 л
Сосуд 3 л	-	3 л	-	2 л	2 л	3 л

2 способ

Сосуд 3 л	3 л	-	3 л	1 л	1 л	-	3 л	-
Сосуд 5 л	-	3 л	3 л	5 л	-	1 л	1 л	4 л

Задача 2. Имеются 2 сосуда вместимостью 8 л и 5 л. Как с их помощью отмерить 7 л воды?

Решение:

Сосуд 8 л	-	5 л	5 л	8 л	-	2 л	2 л	7 л
Сосуд 5 л	5 л	-	5 л	2 л	2 л	-	5 л	-

Задача 3.Как, имея сосуды 5 л и 7 л, отмерить 6 л воды?

Решение:

Сосуд 5 л	-	5 л	-	2 л	2 л	5 л	-	4 л	4 л	5 л
Сосуд 7 л	7 л	2 л	2 л	-	7 л	4 л	4 л	-	7 л	6 л

Задача 4. Как с помощью 7-литрового ведра и 3-литровой банки налить в кастрюлю 5 л воды?

Решение:

Ведро 7 л	7 л	4 л	4 л	1 л	1 л	-	7 л	5 л
Банка 3 л	-	3 л	-	3 л	-	1 л	1 л	3 л

Задача 5. Имеются сосуды – 17 л и 5 л. Как отмерить 13 л?

Решение:

1-й шаг: налить в сосуд 17 л 3 раза по 5 л, т.е. 15 л.

2-й шаг: наполнить 5-литровый сосуд и 2 литра вылить в сосуд 17 л, там будет 17 л, а в 

5-литровом останется 3 л.

3-й шаг: вылить воду из сосуда 17 л, а туда слить 3 л и налить 2 раза по 5 л.

7-8 класс

Задача 1.

Можно ли из цифр 1, 2, 3, 4, 5 составить одно двузначное и одно трехзначное число так, чтобы второе делилось на первое? Каждая цифра должна быть использована ровно один раз.
Решение: 
Можно. 532 делится на 14, а 215 делится на 43.

Задача 2.

Самолет вылетел из Москвы в час ночи 15 декабря по московскому времени и прибыл в город N в семь утра того же дня по местному времени. В полдень 15 декабря по N-скому времени он вылетел в город P и прибыл туда в 13.00 того же дня по P-скому времени.
Через два часа он вылетел в Москву и вернулся туда в 18.00 15 декабря по московскому времени. Сколько времени самолет находился в воздухе? Ответ обязательно должен быть обоснован.
Решение: 
Самолет отсутствовал в Москве 17 часов с 1.00 до 18.00, при этом он находился на земле всего 7 часов с 7.00 до 12.00 по местному времени в городе N и с 13.00 до 15.00 местного времени в городе P. Следовательно, все остальное время он летел.

Задача 3.

У Васи и Пети по 55 гирь весом 1, 2,…, 55 кг. Они по очереди подкладывают свои гири каждый на свою чашу двухчашечных весов. Первым ходит Вася. Петя выигрывает, если разность масс гирь на чашах окажется равной 50 кг. Сможет ли он этого добиться?
Решение: 
1. Петя может просто повторять ходы Васи. В какой-то момент Вася вынужден будет сходить гирей 50 кг и немедленно проиграет.
2. Петя откладывает в сторону свою 50-килограммовую гирю и ходит как угодно остальными гирями. В конце игры Вася выложит все гири, а Петя все, кроме 50-килограммовой. Следовательно, чаша Васи будет весить на 50 кг тяжелее.
Ответ. Да.

Задача 4.

Пусть S(n) сумма цифр числа n. Найдите все n, для которых

Решение: 
Доказательство. Все n слагаемых в левой части дают одинаковый остаток при делении на 3, совпадающий с остатком от деления на 3 самого числа n. Перебирая три различных случая, получаем, что остаток от деления левой части на 3 равен либо 0, либо 1. Но правая часть число 2555555 при делении на 3 дает в остатке 2.
Ответ. Таких n не существует.

Задача 5.

В треугольнике ABC  ∠ A = 3 ∠ C. Точка D на стороне BC обладает тем свойством, что  ∠ ADC = 2 ∠ C. Доказать, что AB + AD = BC.
Решение: 
Продолжим отрезок BA за точку A и отложим на нем отрезок AE = AD.
Заметим, что  ∠ EAC = 180 –  ∠ BAC = 180 – 3 ∠ C, поэтому треугольники ADC и AEC равны (по сторонам AC, AD = AE и углу между ними).
Отсюда находим углы треугольника AEC:  ∠ AEC =  ∠ ADC = 2 ∠ C,  ∠ ACE =  ∠ C, т.е.  ∠ BCE = 2 ∠ C, поэтому треугольник BEC равнобедренный.
Таким образом, AB + AD = AB + AE = BE = BC.

Задача 6

Целые числа a, b, c и d удовлетворяют равенству a² + b² + c² = d². Доказать, что число abc делится на 4.

Решение:

Квадрат четного числа делится на 4, а квадрат нечетного числа дает при делении на 4 остаток 1. Если числа a, b, c — нечетные, то d² должен давать при делении на 4 остаток 3, что невозможно. Если среди чисел a, b, c два нечетных и одно четное, то d2 должен давать при делении на 4 остаток 2, что также невозможно. Значит, среди чисел a, b, c есть два четных числа, откуда произведение abc делится на 4. Такое возможно, например, 32 + 42 + 122 = 132.

Задача 7

Найдется ли такое натуральное число n, при котором 2n + n² оканчивается цифрой 5?

Решение:

Число 2n может оканчиваться одной из цифр 2, 4, 8, 6 (с периодом 4), а число n² — одной из цифр: 1, 4, 9, 6, 5, 6, 9, 4, 1, 0 (с периодом 10). Отсюда число 2n + n² будет оканчиваться на 5, если 2n оканчивается на 4 или на 6, то есть когда число n — четно,
но тогда 2n + n² — четно, значит, не может оканчиваться на цифру 5.

Задача 8

Два совершенно одинаковых катера, имеющих одинаковую скорость в стоячей воде,
проходят по двум различным рекам одинаковое расстояние (по течению) и возвращаются обратно (против течения). В какой реке на эту поездку потребуется больше времени:
в реке с быстрым течением или в реке с медленным течением?

Решение

Пусть скорость катеров v км/ч, скорость течения в первой реке v₁ км/ч, а скорость течения во второй реке v₂ км/ч. Пусть v₁>v₂ . Если обозначить расстояние, проходимое в одном направлении катерами, через S ,то время, затраченное первым катером на весь путь, 
t₁ = S/(v+v₁) + S/(v-v₁) = 2Sv/(v²-v₁²),  а время, затраченное вторым катером, t₂ = 2Sv/(v²-v₂²). Поскольку числители у обоих выражений одинаковы, то большей будет дробь с меньшим знаменателем, а так как знаменатели есть разности с равными уменьшаемыми,
то знаменатель меньше у первой дроби, у которой вычитаемое v₁² больше.

Ответ: Больше времени потребуется на поездку в реке с более быстрым течением.

Задача 9

Найти скорость и длину поезда, если известно, что он проходит мимо неподвижного наблюдателя в течение 7 с и затратил 25 с, чтобы проехать вдоль платформы длиной в 378м.

Решение

Пусть x (м) - длина поезда, y (м/с) - его скорость. Тогда x/y = 7 и (x + 378)/y = 25 , откуда x = 147 (м), y = 21 (м/с). Скорость можно определить сразу: для проезда мимо платформы поезду потребовалось 25 - 7 = 18 (с). Следовательно, его скорость 378 : 18 = 21 (м/с),
длина его 21 х 7 = 147 (м). 

Ответ  21 м/с, 147 м. 

Задача № 10
Когда Винни-Пух пришел в гости к Кролику, он съел 3 тарелки меда, 4 тарелки сгущенки и 2 тарелки варенья, а после этого не смог выйти наружу из-за того, что сильно растолстел от такой еды. Но известно, что если бы он съел 2 тарелки меда, 3 тарелки сгущенки и 4 тарелки варенья или 4 тарелки меда, 2 тарелки сгущенки и 3 тарелки варенья, то спокойно смог бы покинуть нору гостеприимного Кролика. От чего больше толстеют: от варенья или от сгущенки?

Решение :
По условию 3м + 4с + 2в > 2м + 3с + 4в,  откуда м + с > 2в. (*) По условию же

3м + 4с + 2в > 4м + 2с + 3в,  откуда 2с > м + в.  Складывая последнее неравенство с неравенством (*), получаем м + 3с > м + 3в, откуда с > в.

Задача № 11
В каждой клетке клетчатой доски размером 50  х  50 записано по числу. Известно, что каждое число в 3 раза меньше суммы всех чисел, записанных в клетках, соседних с ним по стороне, и в 2 раза меньше суммы всех чисел, записанных в клетках, соседних с ним по диагонали. Докажите, что каждую клетку доски можно покрасить в красный или синий цвет так, что сумма всех чисел, записанных в красных клетках, равна сумме всех чисел, записанных в синих клетках.
Решение :
Покажем, что подойдет раскраска клеток доски в шахматном порядке. Заметим, что сумма данного числа и его соседей по диагоналям равна сумме соседей этого числа по сторонам: обе суммы втрое больше данного числа. Поэтому в квадрате 2 х 2, находящемся в углу доски, суммы чисел в красных и синих клетках совпадают: обе они втрое больше числа, стоящего в угловой клетке доски. Также совпадают суммы чисел в красных и синих клетках любого прямоугольника 3 х 2, примыкающего длинной стороной к краю доски: обе они втрое больше числа, стоящего в средней клетке стороны, примыкающей к краю доски. Наконец, совпадают суммы чисел в красных и синих клетках любого квадрата 3 х 3: обе они втрое больше числа, стоящего в центре квадрата.

Разобьем доску 50 х 50 на квадрат 48 х 48, квадрат 2 х 2 и два прямоугольника 2 х 48, как показано на рисунке. Квадрат 48 х 48 разобьем на квадраты 3 х 3, а прямоугольники 2 х 48 — на прямоугольники 3 х 2, примыкающие длинной стороной к краю доски. В каждом из этих квадратов и прямоугольников суммы чисел, стоящих в красных и синих клетках, равны. Значит, они равны и на всей доске.

Задача 12.

Докажите, что ребус: ЗАДАЧА + ЗАДАЧА = ТУРНИР не имеет решений.
Решение: 
Сложение А + А должно быть выполнено в трех различных разрядах, при этом результаты записываются тремя различными буквами У, Н и Р.
Но это невозможно, так как А + А может принимать только два разных значения эта сумма является либо некоторым четным числом (если нет переноса из предыдущего разряда), либо следующим за ним нечетным (если есть перенос единицы из предыдущего разряда).
Переноса двух единиц быть не может.

Задача 13.

Имеется n дискеток и n этикеток, раскрашенные в несколько цветов. Дубль это дискета, к которой приклеена этикетка того же цвета. Докажите, что можно добиться того, что все дубли будут одного цвета.
Решение: 
1. Наклеим сначала этикетки на дискетки в произвольном порядке. Предположим, что у нас образовались дубли нескольких различных цветов. Возьмем по одной дискетке-дублю двух разных цветов и обменяем их этикетки. После этого каждая из дискеток перестанет быть дублем, так что общее число дублей уменьшится на 2. Далее будем повторять эту операцию до тех пор, пока дублей различных цветов не останется.
2. Докажем нужный факт индукцией по числу дискеток (при этом можно даже не обращать внимание на соответствие цветов дискеток и этикеток!). База индукции (одна дискетка) очевидна. Переход: если все k + 1 дискеток одноцветны, то и доказывать нечего.
Если же есть дискетки разных цветов, то возьмем одну из них и наклеим на нее этикетку другого цвета, а для остальных k дискеток применим предположение индукции.

Задача  14.

Принцип Дирихле гласит : « Пусть в n клетках сидит не менее чем n+ 1 кроликов. Тогда найдется клетка, в которой сидит не менее двух кроликов». Попробуйте применить этот принцип  к следующей задаче:

« Шесть школьников съели семь конфет

а) Докажите, что один  из них съел не менее двух конфет.

б ) Верно ли, что кто-то съел ровно две конфеты?».

Решение:

а ) пусть конфеты- это «кролики», а школьники – это « клетки». Так как 7>6, то по принципу Дирихле найдется школьник, который съел не менее 2 конфет.

б) Нет, так как все конфеты мог съесть один школьник или один съесть 3, а второй -4 конфеты.

Задача 15.

Квадрат АВСD со стороной 2 см и квадрат DEFK со стороной 1 см стоят рядом на верхней стороне АК квадрата AKLM со стороной 3 см. Между парами точек А и Е, В и F,C и K, D и  L  натянуты паутинки. Паук поднимался снизу вверх по маршруту AEFB и спускался по маршруту CKDL. Какой маршрут короче?

Решение:

Прямоугольные треугольники с гипотенузами АЕ и СК,FB и DL равны по двум катетам, значит, АЕ=СК и FB=DL. Так как EF=KD, как стороны квадрата. тоAE+EF+FB=CK+KD+DL. Значит, оба маршрута будут одинаковы.  

B                     C

                  EEE            F

A                                 K

M                                 L

Задача 16.

Найдите все пары натуральных чисел, удовлетворяющих уравнению      х² - у ² = 69.

Решение .( х – у )· (х+ у)=69 = 1·3·23 = 69 · 1 = 23 ·3; х > у. Тогда

  или       

Решая  данные системы, находим два решения: х = 35; у = 34 или х = 13,  у = 10.

Задача 17.

Одну овцу лев съедает за 2 дня, волк – за 3 дня, а собака – за 6 дней. За сколько дней они вместе съедят овцу?

Решение. Лев съедает за сутки  овцы, волк  -  овцы, собака -  овцы. Тогда вместе они съедят  = 1 ( овцу).

Ответ : за один день.

9-11 класс

Тема1 : Планиметрия

Точка пересечения медиан

Точка пересечения биссектрис

Точка пересечения высот

Ортотреугольник

Определение

Ортотреугольником называют треугольник, образованный основаниями высот некоторого треугольника.

Например, на рисунке треугольник A₁B₁C₁ является ортотреугольником треугольника ABC.

Свойства ортотреугольника

Пусть треугольник  ABC является остроугольным, тогда:

1.      Точка пересечения высот H  треугольника ABC является точкой  пересечения биссектрис треугольника A₁B₁C₁.

2.      Точки A, B, C являются центрами вневписанных окружностей треугольника A₁B₁C₁.

3.      Для остроугольного треугольника ABC треугольник A₁B₁C₁ является треугольник с наименьшим периметром среди треугольников, у которых вершины расположены на сторонах треугольника ABC.

4.      Треугольник A₁B₁C₁  является ортотреугольником треугольников ABC,  ABH, BCH, CAH

Доказательство свойства 1

Четырехугольник AB1A1B  является вписанным, так равны углы ∠AB1B=∠AA1B=90∘. Значит, что ∠ABC=180∘−∠AB1A1=∠CB1A1.

Аналогичным образом мы можем получить, что ∠ABC=∠AB1C1  (для этого нужно рассматривать четырехугольник BC1B1C ).

Тогда ∠C1B1H=90∘−∠AB1C1=90∘−∠ABC=90∘−∠CB1A1=∠A1B1H . Значит, что луч B1H  является биссектрисой угла ∠A1B1C1 .

Аналогично можно доказать, что H  лежит на биссектрисах углов ∠C1A1B1  и ∠B1C1A1 , т.е. является точкой пересечения биссектрис этого треугольника.

Свойство 1 доказано.

Удвоение медианы 

Идея удвоения медианы очень простая. Её можно сформулировать в виде простого утверждения.

Теорема

Пусть в треугольнике ABC точка B₁ является серединой стороны AC. Если отразить точку B симметрично относительно B₁ и получить точку D (по сути мы удваиваем медиану BB1), то мы получаем, что четырехугольник ABCD является параллелограммом.

Доказательство

Так как в четырехугольнике ABCD диагонали пересекаются в точке B1 и при этом делятся точкой B1 пополам, то при признаку параллелограмма получаем, что ABCD — параллелограмм.

Неравенство треугольника

Утверждение

В треугольнике против большей стороны лежит больший угол, против большего угла лежит большая сторона.

Доказательство

Утверждение

Сумма любых двух сторон треугольника больше третьей стороны.

Доказательство

Что и требовалось доказать.

Неравенство геометрии

Утверждение

Против большей стороны треугольника лежит больший угол.

Доказательство

Утверждение

Против большего угла треугольника лежит большая сторона.

Метод вспомогательной площади

Часто в задачах на площадь используется так называемый метод вспомогательной площади. Например, равенство площадей двух каких-либо фигур можно доказывать следующим образом. К обеим фигурам прикладывается какая-то фигура (или наоборот, вырезается) таким образом, что площади полученных двух фигур оказывается легко сравнивать. Если площади полученных фигур оказались равны, то, вернув обратно эту общую вспомогательную фигуру (ее площадь как раз и есть вспомогательная), легко установить, что и изначальные фигуры равны по площади.

Формулы площади используют также для решения задач, которые на первый взгляд никак с площадью не связаны. В таком случае удобно бывает рассматривать площадь какой-то фигуры, благодаря чему можно получить следствия, полезные для решения задачи.

ПРИМЕР

Пусть диагонали трапеции ABCD  с основаниями AD  и BC  пересекаются в точке O . Докажите, что S_ABO=S_CDO

Докажем, что S_ABC=S_DBC, отсюда будет следовать, что S_ABO=S_CDO, поскольку S_ABC−S_BOC=S_ABO, S_DBC−S_BOC=S_CDO. Здесь мы как раз пользуемся методом вспомогательной площади, мы добавили к обоим треугольникам общий треугольник BOC, докажем, что полученные большие треугольники равны по площади, а значит, равны по площади и части без общей площадь.

 Площадь треугольника BOC и есть та самая вспомогательная площадь.

Остается доказать, что площади ABC и DBC равны. Заметим, что у этих треугольников общая сторона BC и равные высоты, опущенные из точек A и D на прямую BC. Высоты равны, поскольку прямые параллельны. Отсюда по формуле площади через основание и высоту мы получаем, что S_ABC=S_DBC, а  из сказанного ранее следует равенство площадей треугольников AOB и COD.

Пример

Докажите, что площади параллелограммов ABCD и AFGH равны. (см. рисунок)

Задача 1

Найдите углы треугольника, если известно, что медиана и высота, выходящие из вершины одного из его углов, делят этот угол на три равные части. В ответе укажите отношение величин максимального угла к минимальному.

 Решение задачи

Пусть высота CD и медиана CM делят угол C треугольника ABC на три равные части. Предположим, что точка D расположена между B и M. Обозначим ∠BCD=∠DCM=∠ACM=α  Поскольку в треугольнике BCM высота CD является биссектрисой, то этот треугольник равнобедренный, поэтому CD — медиана треугольника BCM и BD=DM. 

Пусть K - проекция точки M на AC. Тогда из равенства прямоугольных треугольников CKM и CDM (по гипотенузе и острому углу) следует, что MK=DM=1/2BM=1/2AM. Значит, ∠MAK=30∘ (этот треугольник прямоугольный и против этого угла лежит катет, в два раза меньший гипотенузы).

Следовательно, 2α=∠ACD=90∘−∠MAK=90∘−30∘=60∘,α=30∘,∠ACB=3α=90∘,∠ABC=60∘.

Ответ:3

Задача 2

В треугольнике две высоты равны 12 и 20. Найдите максимальное возможное целое значение длины третьей высоты.

Решение задачи

Ответ:29

Задача 3

Медианы треугольника равны 3, 4 и 5. Найдите площадь треугольника.

Ответ:8

Задача4

Две стороны треугольника равны 34 и 32, а медиана, проведенная к третьей, равна 17. Найдите площадь треугольника.

Решение задачи

Ответ:480

Задача5

Решение задачи

Ответ: 1,75

Тема2:  Функции

Определение

Пусть даны два множества X и Y (вообще говоря, произвольной природы), и каждому элементу x∈X поставлен в соответствие некоторый элемент y∈Y, тогда говорят, что задана функция из X в Y, и записывают f: X→Y, где f — название функции.

 При этом если элементу x∈X ставится в соответствие элемент y∈Y, то пишут y=f(x). 

Определение

Пусть задана функция f: X→Y. Множество X называется областью определения функции f.

Если числовая функция задана формулой, то можно ставить вопрос о нахождении наибольшей области определения, то есть отыскания всех точек числовой прямой, для которой эта функция определена.

Такое множество точек обозначается D(f). 

Например, D(1/x)=(−∞;0)∪(0;+∞), D(√x)=[0;+∞).

Определение

Множеством значений функции называется множество

E(f)={y: ∃x∈X: y=f(x)}⊂Y.

Определение

Рассмотрим функцию f: X→Y, где X и Y — некоторые подмножества множества действительных чисел. 

Графиком такой функции называется множество всех точек (x;y) координатной плоскости, для которых справедливо равенство y=f(x).

Определение.

 Функция f называется периодической с периодом T, если ее область определения такова, что для любого x из области определения x+T и x−T тоже из области определения, и для любого x справедливо равенство f(x+T)=f(x).

Задание №1

Решите уравнение: 2^x+3^x=97.

Решение

 

Ответ:4

Задание №2

Дана функция f:R→R, удовлетворяющая уравнению  f(x)−f(y)=y−x

Известно, что f(1)=1. Найдите значение f(2015).

Решение                   

Пусть х=2015, у=1. Тогда из определения функции f(2015)-f(1) = 1- 2015, откуда f(2015) = 1-2015+f(1) = -2013

Ответ: -2013

Задание №3 

Про функцию f:R→R известно, что f(2015)≠0, а также, что для любых x и y

f(x)⋅f(y)=f(x−y).

Найдите возможные значения f(100500).

Решение

Подставив в уравнение x=2015, y=0 получаем, что f(0)=1.

Подставив y=x получаем, что  f(x)²=1.

Отсюда f(x) для любого x либо 1 либо −1. Взяв теперь y=x/2 видим, что

f(x)f(x/2)=f(x/2).

Так как f(x2) равно ±1, то на него можно сократить и получить, что функция f тождественно равна 1.

Ответ:1

Задание №4

Про квадратный трёхчлен f(x)=ax2+bx+c известно, что f(c)=3, а f(1/a)=8. Найдите, чему равно a⋅c. Ответ запишите десятичной дробью.

Решение

Заметим, что

f(c)=ac²+bc+c=ac(c+b/a+1/a)=ac⋅f(1/a).

Отсюда получаем, что ac=f(c)/f(1/a).

Ответ:0,375

Задание №5

Сколько существует различных натуральных значений n, при которых функция

f(x)=cos nx⋅sin имеет период 6π?

Решение

Для любого действительного x должно выполняться равенство f(x+6π)=f(x).

То есть

Ответ:8

Тема3:Инвариант и полуинвариант

Определение

Инвариантом называется величина или некоторое свойство, которое не меняется при заданных преобразованиях.

Пример

На доске написаны шесть чисел: 1, 2, 3, 4, 5, 6. За один ход разрешается к любым двум из них одновременно добавлять по единице. Можно ли за несколько ходов все числа сделать равными? 

Решение

Сумма написанных чисел нечетна (она равна 21). За каждый ход эта сумма увеличивается на 2, т. е. всегда остается нечетной. А сумма шести равных чисел всегда четна. Это значит, что сделать числа равными невозможно.

Ответ. Нельзя.

 Пример

100 фишек выставлены в ряд. Разрешено менять местами две фишки, стоящие через одну. Можно ли с помощью таких операций переставить все фишки в обратном порядке? 

Решение

Пронумеруем места, на которых стоят фишки, числами от 1 до 100. Заметим, что после выполнения данной в условии операции номер каждой фишки либо не изменился, либо изменился (увеличился или уменьшился) на 2. Таким образом, фишка, стоящая вначале на месте с четным номером, в любой момент остается стоять на месте с четным номером. Следовательно, фишка, стоящая на месте под номером 100, никогда не сможет попасть на клетку с номером 1.

Ответ. Нельзя.

 Пример

Вера, Надя и Люба решали задачи. Чтобы дело шло быстрее, они купили конфет и условились, что за каждую решенную задачу девочка, решившая ее первой, получает четыре конфеты, решившая второй — две, а решившая последней — одну. Девочки говорят, что каждая из них решила все задачи и получила 20 конфет, причем одновременных решений не было. Может ли такое быть? 

Решение

Если за решение каждой задачи все три девочки вместе получали 7 конфет (первая — 4, вторая — 2, третья — 1 конфету), значит, сумма всех полученных ими конфет должна обязательно делиться на 7, но 60 на 7 не делится. Следовательно, девочки ошиблись.

Ответ. Не может.

 Пример

Дана шахматная доска. Разрешается перекрашивать в другой цвет сразу все клетки какой-либо горизонтали или вертикали. Может ли при этом получиться доска, у которой ровно одна черная клетка? 

Решение

При перекрашивании горизонтали или вертикали, содержащей k черных и 8−k белых клеток, получится 8−k черных и k белых клеток. Поэтому число черных клеток изменится на (8−k)−k=8−2k, т. е. на четное число. Так как четность числа черных клеток сохраняется, из исходных 32 черных клеток мы не сможем получить одну черную клетку.

Ответ. Не может.

 Пример

На доске написано число 12. В течение каждой минуты число либо умножают, либо делят на 2 или на 3, и результат записывают на доску вместо исходного числа. Докажите, что число, которое будет написано на доске ровно через час, не может быть равно 54. 

Решение

После каждой операции меняется четность общего количества двоек и троек в разложении на простые множители числа на доске. Вначале это число нечетно (равно трем), т. к. 12=2⋅2⋅3. Поэтому через 60 операций (секунд) оно должно быть нечетным, но в разложении 54=2⋅3⋅3⋅3 четыре множителя.

Противоречие показывает, что превращение из 12 в 54 невозможно.

Ответ. Не может.

 Пример

На острове Серобуромалин живет 13 серых, 15 бурых и 17 малиновых хамелеонов. Когда встречаются два хамелеона разного цвета, они одновременно перекрашиваются в третий цвет. Может ли через некоторое время оказаться, что все хамелеоны имеют один цвет? 

Решение

Пусть с, б, м означают соответственно количества серых, бурых и малиновых хамелеонов в некоторый момент. После встречи, скажем, серого и бурого хамелеонов количества хамелеонов серого, бурого и малинового цветов стали равны с−1, б−1, м+2. Заметим, что остаток от деления на 3 каждой из разностей с−б, б−м, м−с, не изменился после встречи двух хамелеонов. Вначале ни одна из этих разностей не делилась на 3, поэтому ни в какой момент ни одна из разностей не может стать равной 0. Это означает, что количества хамелеонов двух разных цветов никогда не станут равными.

Ответ. Не может.

Определение

Полуинвариантом называется величина, значение которой изменяется монотонно (не убывает или не возрастает) при заданных преобразованиях.

Пример

В стране несколько городов, попарные расстояния между которыми различны. Путешественник отправился из города A в самый удаленный от него город B, оттуда — в самый удаленный от него город C и т. д. Докажите, что если город C не совпадает с городом A, то путешественник никогда не вернется в город A. 

Решение

Предположим, что на втором шаге путешественник не возвратился в A, то есть город C отличен от города A. Тогда маршрут от A до B короче маршрута из B в C (поскольку C — наиболее удаленный от B город, а расстояния между городами различны). В дальнейшем каждый следующий маршрут будет не короче предыдущего, так как каждый раз мы в качестве следующего пункта назначения выбираем наиболее удаленный город. Пусть на некотором шаге путешественник все же вернулся в город A, выйдя из некоторого города X. По доказанному, маршрут от X до A длиннее маршрута от A до B, а это противоречит тому, что B — наиболее удаленный от A город.

 Пример

Шеренга новобранцев стояла лицом к сержанту. По команде «налево» некоторые повернулись налево, а остальные — направо. Всегда ли сержант сможет встать в строй так, чтобы с обеих сторон от него оказалось поровну новобранцев, обращенных к нему лицом? 

Решение

Договоримся в случае, когда сержант стоит в строю, обозначать буквой m количество человек, стоящих в строю слева от сержанта к нему лицом, а буквой n — количество человек, стоящих справа от сержанта к нему лицом.

Пусть сначала сержант встанет в левый край шеренги. Тогда слева от него никого не будет (m=0). Если и справа от сержанта никто не будет стоять к нему лицом (n=0), то задача решена. В противном случае (n>0) пусть сержант идет слева направо от человека к человеку. Если он проходит новобранца, стоявшего к нему спиной, то число m увеличивается на 1, а число n не изменяется. Если сержант проходит новобранца, стоявшего к нему лицом, то число n уменьшается на 1, а число m не изменяется. Тем самым число m−n сначала отрицательно, а в процессе движения сержанта вдоль строя увеличивается на 1 при прохождении каждого новобранца. Но когда сержант дойдет до правого края, уже число n будет нулевым, а значит, число m−n будет неотрицательным. Итак, начав с отрицательного числа m−n и прибавляя к нему несколько раз по единице, мы получили неотрицательное число. Значит, в какой-то момент мы должны были получить ноль, то есть в тот момент m=n и с обеих сторон от сержанта лицом к нему находилось поровну новобранцев.

Ответ. Всегда.

 Пример

На материке есть несколько стран, в каждой из которых правит либо партия правых, либо партия левых. Раз в месяц в одной из стран может поменяться власть. Это может произойти только в случае если в большинстве стран, граничащих с этой страной, правит другая партия. Докажите, что смены партий не могут продолжаться бесконечно. 

Решение

Пусть власть сменилась в некоторой стране A, в которой правят левые (для определенности). Пусть среди граничащих с ней стран было k стран, где правят левые, и m стран, где правят правые, k<m. При смене власти в стране A количество стран среди граничащих с ней стран, в которых правит та же партия, что и в A, возрастет на 2(m−k)>0. Таким образом, после смены власти в какой-либо из стран число пар граничащих стран, имеющих одну и ту же партию у власти, возрастает. Это возрастание не может продолжаться бесконечно долго, поскольку число всех пар граничащих стран конечно.

 Пример

Несколько ребят сидят за круглым столом. У каждого из них есть некоторое четное количество конфет. По команде каждый передает половину своих конфет сидящему справа. Если после этого у кого-нибудь оказалось нечетное количество конфет, то ему извне добавляется одна конфета. Это повторяется много раз.

Докажите, что настанет время, когда у всех будет поровну конфет. 

Решение

Пусть 2m — наибольшее, а 2n — наименьшее количество конфет у одного человека. После одного круга обмена и, возможно, добавления конфет извне m не увеличится, а количество людей, имеющих 2n конфет, уменьшится. (Действительно, каждый человек оставляет себе не более m конфет, а получает не более m+1 конфеты. Причем если он получил m+1 конфету, то одна из них была добавлена извне, значит, после получения m конфет у него стало не более 2m−1 конфеты. С другой стороны, если m>n, среди людей имевших 2n конфет, найдется человек, который получит более n конфет.) Таким образом, так как n увеличивается, а m не увеличивается, наступит момент, когда m станет равным n.

 Пример

Круг разбит на 2012 секторов, в некоторых секторах стоят фишки — всего 2013 фишек. Затем берутся какие-нибудь две фишки, стоящие в одном секторе, и переставляются в разные стороны в соседние секторы. Докажите, что после нескольких таких операций не менее 1006 секторов будет занято. 

Решение

Докажем более сильное утверждение: начиная с некоторого момента не менее половины секторов будет занято. Отметим, что поскольку фишек больше, чем секторов, то в любой момент в каком-то секторе будут находиться не менее двух фишек. Значит, движение может продолжаться бесконечно долго, независимо от того, каким образом позиция преобразуется. Докажем, что каждый из секторов в какой-то момент окажется непустым. Предположим противное. Пусть движение происходит так, что один из секторов все время остается пустым. Это значит, что движение фишек никогда не исходит из двух соседних с ним секторов. Поэтому количество фишек в этих двух секторах не может уменьшаться. Так как общее количество фишек конечно, то начиная с какого-то момента фишки в эти сектора поступать не будут. А это значит, что с этого момента никакого движения не будет исходить из двух следующих, соседних с ними секторов. Продолжая подобные рассуждения, приходим к выводу, что в некоторый момент движение должно вообще прекратиться. Полученное противоречие показывает, что предположение было ложным, значит, каждый сектор в какой-то момент окажется непустым. После этого всегда либо этот сектор, либо его сосед (по часовой стрелке) будет непустым. Действительно, всякий раз, когда освобождается один из двух соседних секторов, второй заполняется. Дождемся момента, когда все секторы побывают заполненными. Тогда любому пустому сектору можно поставить в соответствие непустой — следующий за ним по часовой стрелке. При таком соответствии непустой сектор может соответствовать не более чем одному пустому. Поэтому пустых секторов будет не больше, чем непустых. Значит, занятыми будут не менее половины секторов

Задание1.

Хулиган Вова порвал стенгазету на несколько частей, причём каждый раз он рвал какой-то кусок на 4 части. Сколько частей могло получиться? Выберите возможные ответы.

Решение

Каждый раз, когда Вова разрывает какой-то кусок прибавляется 3 куска. Поэтому остаток при делении на три количества кусков не изменяется. Так как вначале был 1 кусок, то получится может только число кусков, сравнимое с 1 по модулю 3. Все такие числа могут получиться, так как когда Вова рвёт стенгазету, то последовательно получаются 3k+1 куска для натуральных k.

Ответ:2014, 484, 10000

Задание2.

На доске записано число 123456789. У написанного числа выбираются две соседние ненулевые цифры, из каждой из них вычитается по единице, после этого выбранные цифры меняются местами. Какое наименьшее число может быть получено в результате таких операций?

Решение

Заметим, что при выполнении каждой операции не меняется четность цифры, стоящей на каждом месте. В самом деле, вначале у нас было число 123456789, т.е. число вида *НЧНЧНЧНЧН* (*Н* означает нечетную цифру, а *Ч* — четную). Если мы возьмем пару соседних цифр, скажем *НЧ*, то при уменьшении этих цифр на 1 получится пара *ЧН*, а при смене местами снова получится пара *НЧ*. Аналогично, если мы возьмем пару соседних цифр вида *ЧН*, то при уменьшении этих цифр на 1 получится пара *НЧ*, а при смене местами снова получится пара *ЧН*. Итак, в процессе выполнения операций число все время будет иметь вид *НЧНЧНЧНЧН*. Минимальным числом такого вида, очевидно, является число 101010101. Осталось показать, что число 101010101 получить можно. Для этого достаточно в исходном числе 123456789 применить два раза нашу операцию к паре соседних цифр 2 и 3, применить четыре раза операцию к паре соседних цифр 4 и 5, шесть раз к паре соседних цифр 6 и 7, и наконец восемь раз к паре соседних цифр 8 и 9.

Ответ: 101010101

Задание3.

В ряд выложены 2013 черных и 2013 красных шаров, причём самый левый и самый правый шары чёрные. Всегда ли можно выбрать слева подряд несколько шаров (но не все!) так, чтобы среди них количество красных равнялось количеству чёрных?

Решение

Пусть мы выбрали слева подряд k>0 шаров, причем количества черных и красных не совпадают. Определим f(k) — количество красных шаров минус количество черных (среди этих k). Тогда при увеличении k на единицу наша функция меняется тоже ровно на 1. Поэтому, так как f(1)=−1, a f(2012+2013)=1, то при каком-то k наша функция была равна 0 (так как при изменении k на 1, f тоже меняется на 1).

Ответ: да

Задание4.

Есть куча из 1001 камня. Одним ходом из какой-нибудь кучи, где лежит больше одного камня, выкидывают один из них, а затем любую кучу делят на две меньшие. Какие ситуации можно получить?

Решение

Заметим, что величина i, равная сумме количества камней и количества кучек остаётся неизменной. Поэтому сразу отпадают варианты, когда во всех кучках по 3, 4, 10 или 600 камней: в этих случаях i делится на 4, 5, 11 или 601 соответственно, а вначале i=1002. Остальные случаи возможны, например, можно откладывать из большой кучки по одной кучке требуемого размера.

Ответ:

               В каждой куче только один камень  +

               Все кучи состоят из трех камней      -

               Все кучи состоят из 5 камней          +

               Все кучи состоят из 4 камней           -

               Все кучи состоят из 10 камней         -

               Все кучи состоят из 500 камней       +

               Все кучи состоят из 600 камней       -

Задание4.

На поле 10×10 9 клеток поросло бурьяном. Каждый год на всех клетках, у которых есть хотя бы две соседние по стороне клетки, поросшие бурьяном, вырастает бурьян. Если клетка поросла бурьяном, то он на ней будет всегда. Найти максимальное число клеток, на которых через 100 лет будет расти бурьян.

Решение

Заметим, что периметр поросшей бурьяном территории не увеличивается. Если рядом с клеткой, которая на которой вырастает бурьян, было три или четыре поросших бурьяном клетки, то он уменьшается, а если только две, то остаётся неизменным. Изначально он не больше, чем 9⋅4=36. Наибольшая площадь прямоугольник при данном периметре достигается в случае, когда прямоугольник — квадрат со стороной 9. Примером изначальной рассады бурьяна служит поросшая бурьяном главная диагональ без угловой клетки.

Ответ:81

Тема 4.  Некоторые методы доказательства неравенств

Задание 1

Решение

Ответ:8

Задание 2

Решение

Ответ:16

Задание 3

Решение

Ответ:1

Задание 4

Решение

Ответ:5

Задание 5

 

Решение

Ответ: 50

Тема 5: Метод (принцип) математической индукции

Пусть имеется последовательность утверждений У₁, У₂, У₃, … И пусть первое утверждение У₁ верно, и мы умеем доказывать, что из верности утверждения У_k следует верность следующего утверждения У_k+1. Тогда все утверждения в этой последовательности верны.

Определение

Базой индукции называется утверждение У₁. Иногда базой индукции называют несколько первых утверждений У₁,У₂,⋯У_k, но чаще всего база индукции — это только первое утверждение.

Предположением индукцией называется предположение о том, что утверждение У_n верно для n=k.
Шагом индукции (переходом индукции) называется доказательство того, что из верности утверждения У_k  следует верность утверждения У_k+1.

Пример

Доказать, что сумма кубов трех последовательных натуральных чисел делится на 9. 

Решение

Более формально утверждение задачи можно записать так: доказать, что для любого натурального n сумма кубов n³+(n+1)³+(n+2)³ делится на 9.

Поскольку 1³+2³+3³=36 делится на 9, то для n=1 утверждение верно.

Предположим, что оно верно для n=k, то есть 

k³+(k+1)³+(k+2)³=9m

 для некоторого натурального числа m. Докажем, что тогда утверждение верно и для n=k+1. Действительно, 

(k+1)³+(k+2)³+(k+3)³=(k+1)³+(k+2)³+k³+9k²+27k+27=

=9m+27k+9k²+27=9(m+3k+k²+3)

 делится на 9. Поэтому утверждение верно для любого натурального n.

Пример

Доказать, что 

1²+2²+3²+…+n²=n(n+1)(2n+1)

                                6.

Решение

Проверим, справедлива ли эта формула при n=1: 

1²=1(1+1)(2+1) =1.

6

Это верно.

Предположим, что тождество верно при n=k, то есть 

1²+2²+3²+…+k²=k(k+1)(2k+1)/6.

Проверим, что тогда это тождество верно и при n=k+1: 

1²+2²+3²+…+k²+(k+1)²=(1²+2²+3²+…+k²)+(k+1)²=

=k(k+1)(2k+1) +(k+1)²=k(k+1)(2k+1)+6(k+1)²=

6                                 6

=(k+1)(k(2k+1)+6(k+1)) =(k+1)(2k2+7k+6) =

3                                  6

=(k+1)(k+2)(2k+3) =(k+1)((k+1)+1)(2(k+1)+1).

6                                             6

Значит, тождество верно для любого n.

Пример

Доказать, что при каждом натуральном n⩾3 существует выпуклый n-угольник, имеющий ровно три острых угла. 

Решение

Для n=3 утверждение очевидно, так как подходит любой остроугольный треугольник. В качестве примера четырехугольника можно взять правильный треугольник, к одной из сторон которого основанием «приклеили» тупоугольный равнобедренный треугольник с углом при вершине меньше 120∘.

Пусть есть такой k-угольник, k⩾4. Возьмем один из его тупых углов и «отрежем» его, соединив середины образующих его сторон. Число вершин станет k+1. Новые два угла, появившиеся вместо старого, будут еще более тупые, так как они являются внешними углами «отрезанного» треугольника.

 Пример

В один из дней года оказалось, что каждый житель города сделал не более одного звонка по телефону. Докажите, что население города можно разбить не более, чем на три группы так, чтобы жители, входящие в одну группу, не разговаривали в этот день между собой по телефону. 

Решение

Докажем утверждение задачи по индукции (по числу жителей n).

Если n⩽3, то утверждение задачи очевидно. Пусть утверждение доказано для n=m. Докажем для n=m+1. Для начала отметим, что всего было совершено не более n звонков. Рассмотрим человека, который разговаривал наименьшее число раз (если таковых несколько, то любого из них). Если он разговаривал по крайней мере 3 раза, то всего в городе было совершено по крайней мере 3n/2 звонка, т.к. если мы посчитаем все звонки, суммируя количество звонков, в которых участвовал каждый отдельный человек, то получим удвоенное число звонков (т.к. каждый звонок мы будем считать 2 раза. Почему?). Но 3n/2>n (неравенства для общего числа звонков), поэтому этим человеком было совершено не более двух звонков. А теперь на некоторое время "забудем" об этом человеке, т.е. рассмотрим всех жителей этого города без этого человека и без звонков, в которых он участвовал. Тогда осталось жителей ровно n=m и каждым из жителей было совершено не более 1 звонка, значит, по предположению индукции их можно разделить на три группы. Теперь "вспомним" о том, человеке, который принимал участие в наименьшем числе звонков. Так как у него было совершено не более 2 звонков, то его можно добавить в ту группу, в которой нет тех людей, с которыми он разговаривал.

Последняя задача связана со следующим общим фактом:

Утверждение

Если из каждой вершины графа выходит не более n ребер, то вершины этого графа можно покрасить в n+1цвет так, что никакие две вершины, которые соединены ребром будут разных цветов.

Доказательство данного утверждения почти полностью совпадает с доказательством предыдущей задачи.

Комментарий

На самом деле верна гораздо более сильная теорема (теорема Брукса): Если из каждой вершины связанного графа (т.е. из любой вершины можно добраться по ребрам до любой другой вершины графа) выходит не более n ребер и данный граф не совпадает с полным графом на n+1 вершине (полный граф — граф, у которого проведены все ребра), то вершины этого графа можно покрасить в n цветов так, что никакие две вершины, которые соединены ребром будут разных цветов.

 Метод (принцип) полной индукции

Пусть имеется последовательность утверждений У1, У2, У3, … И пусть мы умеем доказывать, что из верности утверждений У1, У2, У3, …, Уk следует верность следующего утверждения: Уk+1. Тогда все утверждения в этой последовательности верны.

Также примером применения метода(принципа) математической индукции является доказательство существования разложения на простые множители для любого натурального числа (это часть основной теоремы арифметики).

Пример

Докажите, что любое натуральное число, отличное от 1, можно представить в виде произведения простых множителей.

Доказательство

Наше доказательство будет основано на том факте, что наименьший из всех делителей, которые есть у числа (но отличный от 1), является простым числом. Давайте докажем это утверждение. Итак, рассмотрим наименьший (отличный от 1) из всех делителей, которые есть у натурального числа n>1. Обозначим его через m, покажем, что это число – простое. Если это число составное, то у него есть разложение m=ab, где 1<a,b<m. Т.е. у числа n есть делители a и b, которые меньше, чем m. Значит,m — простое число.

Теперь покажем, что для n>1 существует разложение на простые. Действительно, будем доказывать по индукции. Для n=2 — это очевидно. Пусть это утверждение доказано для всех натуральных меньшихn. Докажем это утверждение для n. Если n — простое число, то мы доказали (само число и есть разложение на простые множители). Тогда предположим, что n — составное. Рассмотрим наименьший делитель (p) числа n, отличный от 1. То есть n представимо в виде n=pk, где 1<k<n. Но для k мы доказали существование разложения на простые множители. То есть и число n раскладывается на простые множители.

Задание 1

Найдите сумму  1/1⋅2+1/2⋅3+⋯+1/99⋅100.

Ответ: 0,99

Задание 2

Найдите сумму 1+3+5+…999

Ответ: 250000

Задание 3

При каких n выражение n³+5n делится на 6?

Ответ:  любое натуральное число

Задание 4

Найдите количество целых чисел вида x^k+1/x^k, где k — целое число из отрезка [−2014;2014], если известно, что x+1/x — целое число.

Ответ: 4029

Задание 5

На сколько частей делят плоскость 100 прямых общего положения, т.е. таких, что никакие две не параллельны и никакие три из них не пересекаются в одной точке?

Ответ: 5051

Тема 6: Комбинаторика

Определение

Комбинаторикой (или комбинаторным анализом) называется область математики, в которой изучаются закономерности между комбинациями, составленными из букв, цифр или любых других объектов и удовлетворяющими некоторым условиям. Идеи комбинаторного характера имеют самое широкое распространение в математике, в таких ее разделах, как теория вероятностей, теория чисел и т.п.

Правило суммы и произведения

ПРИМЕР

К девочке в гости пришел мальчик, и она решила его чем-нибудь угостить. У себя в буфете она нашла семь печений и пять пирожных. Сколькими различными способами девочка может угостить мальчика, если она хочет дать ему лишь одно пирожное и одно печенье?

Решение

Пусть девочка выбрала какое-то печенье. В пару к нему она может выбрать любое из пяти пирожных. Поэтому она может сделать пять различных угощений с этим печеньем, а так как печений всего семь, то всего различных угощений 7⋅5=35.

Ответ. 35.

ПРИМЕР

Гостеприимная девочка еще порылась в буфете и обнаружила кроме семи печений и пяти пирожных еще и десять конфет. Сколько теперь есть у нее способов составить угощение для мальчика, если она хочет дать ему одну конфету, одно печенье и одно пирожное?

Решение

Мы уже знаем, что различных комбинаций из печений и пирожных — 35 штук. Для каждой из этих комбинаций есть десять различных способов добавить конфету. Поэтому девочка может составить угощение 35⋅10=350 различными способами.

Ответ. 350.

ПРИМЕР

 Жадная девочка, отыскав в буфете семь печений, пять пирожных и десять конфет, решила дать мальчику только две какие-нибудь сладости (печенье с пирожным, пирожное с конфетой или конфету с печеньем). Сколько различных вариантов угощения может она составить?

Решение

У девочки есть три возможности выбора двух видов сладостей. Для каждой из них несложно подсчитать число вариантов: для первой, как следует из первой задачи, их 35, аналогично для второй — 5⋅10=50 и для третьей — 10⋅7=70. Складывая все эти варианты, получаем ответ — 155 вариантов.

Ответ. 155.

При решении таких задач самое главное — не запутаться, когда нам нужно перемножать количества вариантов, а когда складывать. Чтобы лучше себе это уяснить, сформулируем два основных комбинаторных правила.

Правило произведения

Пусть объект A можно выбрать n способами, и после каждого такого выбора объект B можно выбрать m способами. Тогда выбор пары (A,B) можно осуществить nm способами. 

Например, в первом примере было два «объекта» — печенье и пирожное.

Правило суммы

Пусть некоторый объект A можно выбрать n различными способами, а другой объект B можно выбрать m способами. Тогда существует n+m способов выбрать либо объект A, либо объект B.

В третьем примере такими «объектами» являются пары — (печенье и пирожное), (пирожное и конфета) и (конфета и печенье).

ПРИМЕР

Монетку бросают десять раз. Сколько различных последовательностей из орлов и решек может при этом получиться?

Решение

Различных результатов после первого броска два — либо орел, либо решка. После каждого из них результатов второго броска также два. Это означает, что после второго броска может получиться 2⋅2=4 различных исхода. Аналогично, после третьего 4⋅2=2³=8 различных результатов. После четвертого — 2⁴, ……, после десятого — 2¹⁰=1024 различных последовательностей из орлов и решек.

Ответ. 1024.

При решении подобных задач получается ответ вида n^m, где n и m — некоторые натуральные числа. Такой ответ получается во всех задачах, в которых требуется посчитать количество способов, на каждое из m мест поставить один из n различных объектов. В таких задачах главное не перепутать, что в какую степень следует возводить!

Например, в предыдущей задаче «местом» является номер броска, а «объектом» — сторона монеты — орел или решка.

ПРИМЕР

В классе 25 человек. Сколькими способами можно выбрать старосту класса и его помощника?

Решение

Старосту класса можно выбрать 25 различными способами. После этого к каждому такому выбору старосты помощника можно подобрать 24 различными вариантами. Итого получаем 25⋅24=600 способов выбрать старосту класса и его помощника.

Ответ. 600.

Отметим, что при решении таких задач надо не забывать, что выбор первого объекта может сузить множество вариантов для выбора следующего объекта. Так, например, в пятом примере выбор старосты ограничивает число людей, претендующих на роль помощника, до 24 человек, то есть выборы старосты и помощника не являются независимыми, в отличие от первых разобранных примеров, где выбор пирожного никак не влиял на последующий выбор печенья.

Рассмотрим еще несколько задач на ту же идею, объединенных общей тематикой, — это так называемые задачи на шахматных досках. Заметим, что для решения этих задач про шахматы, по сути, ничего знать не надо, кроме того, как ходят фигуры.

ПРИМЕР

Сколькими способами можно поставить на шахматную доску черную и белую ладьи так, чтобы они не били друг друга?

 Решение

Черную ладью можно поставить на любую клетку доски — 64 способа. После того как мы поставим эту ладью, для белой останется лишь 49 мест, куда ее можно поставить, так как где бы ни стояла черная ладья, она бьет 15 клеток (считая ту клетку, на которой она стоит). Значит, всего вариантов расстановки двух ладей — 64⋅49=3136.

Ответ. 3136.

ПРИМЕР

Сколькими способами можно поставить на шахматную доску черного и белого слона так, чтобы они не били друг друга? 

 Решение

Заметим, что, в отличие от ладьи, количество полей, которые бьет слон, зависит от того, где он стоит. 

Давайте раскрасим всю шахматную доску в четыре цвета, как показано на рисунке, тогда если черный слон стоит на желтой клетке, то он бьет восемь полей (включая то, на котором он стоит), если на красной, то бьет десять полей, если на синей — 12 полей, на зеленой — 14 полей.

Таким образом, если черный слон стоит на желтой клетке (28 различных вариантов), то для белого слона остается 64−8=56 полей, куда его можно поставить. Если черный слон на красной клетке (20  вариантов), то у белого слона остается 64−10=54 поля. Если на синей (12 вариантов), то у белого — 64−12=52 поля. Если на зеленой (4 варианта), то у белого 64−14=50 полей.

Таким образом, получается всего 28⋅56+20⋅54+12⋅52+4⋅50=3472 способа поставить этих слонов, чтобы они не били друг друга.

Ответ. 3472.

Формулы включения-исключения

ОПРЕДЕЛЕНИЕ

Формула включений-исключений — комбинаторная формула, позволяющая определить мощность объединения конечного числа множеств, которые в общем случае могут пересекаться друг с другом.

Например, в случае двух множеств A, B формула включений-исключений имеет вид:

|A∪B|=|A|+|B|−|A∩B|.

Действительно, сумме |A|+|B| элементы пересечения A∩B учтены дважды, и чтобы компенсировать это мы вычитаем |A∩B| из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера для двух множеств.

Таким же образом и в случае n>2 множеств процесс нахождения количества элементов объединения A₁∪A₂∪…∪A_n  состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и т. д., то есть в попеременном включении и исключении. Отсюда и происходит название формулы. Пусть A₁,A₂,…,A_n — множества, состоящие из конечного числа элементов. Формула включений-исключений утверждает:

При n=2n=2 получаем формулу для двух множеств, приведенную выше.

Число сочетаний

Числа Фибоначчи

Фибоначчи (Леонардо Пизанский) в своем труде «Liber Abaci» 1202 г. рассматривает развитие идеализированной популяции кроликов, которые никогда не умирают. Числа, названные в честь Фибоначчи, — это количество пар в определенный месяц.

ОПРЕДЕЛЕНИЕ

Числа Фибоначчи представляют из себя числовую последовательность:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765…

И могут быть заданы рекуррентной формулой:

F_n = F_n−1 + F_n−2;  F₀ = 0;  F₁ = 1.

Числа Каталана

Числа Каталана — числовая последовательность, которая встречается во многих задачах комбинаторики. Последовательность названа в честь бельгийского математика Каталана.

Первые несколько чисел Каталана:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845…

ОПРЕДЕЛЕНИЕ

n-е число Каталана C_n можно определить следующим образом: 

Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих.

Пример

Для n=3 существует 5 таких последовательностей:

((())), ()(()), ()()(), (())(), (()())

то есть  C₃=5.

Задание 1

Сколько существует различных шестизначных чисел, делящихся на 5?

Решение

Будем пользоваться правилом умножения. Если число делится на 5, то оно должно оканчиваться на 5 или на 0. Таким образом, на первую позицию мы можем поставить любую цифру от 1 до 9 (0 не может стоять на первой позиции в шестизначном числе, т.е. есть 9 возможностей), на вторую — любую цифру от 0 до 9 (т.е. есть 10 возможностей), на третью — любую цифру от 0 до 9 (т.е. есть 10 возможностей), на четвертую — любую цифру от 0 до 9 (т.е. есть 10 возможностей), на пятую — любую цифру от 0 до 9 (т.е. есть 10 возможностей), на шестую — цифру 0 или цифру 5 (т.е. есть 2 возможности). Значит, всего по правилу произведения число таких чисел равно 9⋅10⋅10⋅10⋅10⋅2=180000.

Ответ:180000

Задание 2

Сколькими способами можно выбрать на шахматной доске белое и черное поля, не лежащие на одной горизонтали или одной вертикали?

Решение

Выберем сперва черное поле, это можно сделать 32 способами (всего 32 белых и 32 черных клетки). На той вертикали, где находится выбранное поле, есть четыре белых и четыре черных клетки, точно также, на той горизонтали, где оно находится, есть четыре белых и четыре черных клетки, следовательно, выбирать белое поле можно уже из 32−4−4=24 клеток. То есть, ответ: 32⋅24 способа.

Ответ: 768

Задание 3

Какое наибольшее количество непересекающихся диагоналей можно провести в выпуклом 2013-угольнике (допускаются диагонали, имеющие общую вершину)?

Решение

Каждая проведенная диагональ увеличивает число многоугольников на 1. Поэтому проведя k непересекающихся диагоналей, мы разрежем 2013-угольник на (k+1) многоугольник. Оценим их количество.

Общее число сторон получившихся частей равно 2013+2k (каждая диагональ является стороной двух многоугольников). У каждого многоугольника не меньше трех сторон. Поэтому 2013+2k⩾3(k+1), то есть k⩽2010.

Пример с 2010 диагоналями можно получить, если разрезать 2013-угольник на треугольники (например, провести все диагонали, выходящие из одной вершины).

Ответ: 2010

Задание 4

Шесть девушек водят хоровод. Сколькими различными способами они могут встать в круг?

Решение

Наденем на одну из девушек красную шапочку, чтобы отличать ее от остальных. Затем пронумеруем всех девушек, следующих за ней, против часовой стрелки — ту, которая по правую руку от Красной Шапочки, назовем первой, следующую — второй, и т.д. Тогда в качестве первой девушки может быть любая из пяти (ею могут быть все, кроме самой Красной Шапочки), на втором месте может быть любая из четырех оставшихся, и т.д. В итоге получаем 5!=120 способов для десяти девушек встать в хоровод.

Ответ: 120

Задание 5

Сколькими способами можно выбрать 4 солдата из шеренги, в которой стоят 11 солдат, причем чтобы никакие двое из выбранных не стояли бы рядом?

Решение

Рассмотрим 7 не выбранных солдат в шеренге, между соседними из них мы можем вставить не более одного выбранного солдата, т.е. мы рассматриваем положения выбранных солдат относительно не выбранных. Всего промежутков между ними 6 и ещё 2 с краев, итого 8. Значит, искомое число способов C⁴₈=70.

Ответ: 70

Тема 7: Теория графов

Определение

Два ребра называются смежными, если они имеют общую вершину.

Два ребра называются кратными, если они соединяют одну и ту же пару вершин.

 Ребро называется петлей, если его концы совпадают.

Степенью вершины называют количество ребер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра. Вершина называется висячей, если из неё выходит ровно одно ребро.

Определение

Граф без кратных ребер и петель называется обыкновенным.

Пример

В деревне 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

Решение

Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а ребра — соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины). Поэтому число ребер графа должно быть равно (15⋅5):2. Но это число нецелое. Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.

Ответ: невозможно

Лемма о рукопожатиях

 В любом графе сумма степеней всех вершин равна удвоенному числу ребер.

Доказательство

Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды; если же ребро является петлей, то при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).

Из леммы о рукопожатиях легко вытекает следующий факт.

Следствие. В любом графе число вершин нечетной степени четно.

Пример

В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей (считается, что все дружбы взаимные)?

Решение

Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — степень 4, 10 — степень 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.

Пример

Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

Решение

Если в государстве k городов, то дорог — 3k/2. Это число не может быть равно 100.

Ответ. Не может.

Пример

Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Докажите, что среди них найдутся четверо, имеющие одинаковое число знакомых.

Решение

Предположим противное. Тогда для каждого числа от 68 до 101 имеется не более трех человек, имеющих такое число знакомых. С другой стороны, имеется ровно 34 натуральных числа начиная с 68 и заканчивая 101, а 102=34⋅3. Это означает, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Определение

Путем (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.

Циклом называют путь, в котором первая и последняя вершины совпадают.

Путь (или цикл) называют простым, если ребра в нем не повторяются.

Определение

Если в графе любые две вершины соединены путем, то такой граф называется связным.

Пример

Докажите, что граф с n вершинами, степень каждой из которых не менее( n−1)/2, связен.

Решение

Рассмотрим две произвольные вершины и предположим, что они не соединены путем. Каждая из этих двух вершин по условию соединена не менее чем с ( n−1)/2 другими; при этом все эти вершины различны (если какие-то две из них совпадают, то есть путь, соединяющий исходные вершины).

Таким образом, в графе не менее ( n−1)/2+( n−1)/2+2=n+1 вершин.

Противоречие.

Определение

Рассмотрим подмножество вершин графа такое, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества. Каждое такое подмножество (вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества) называется компонентой связности.

Пример

В некоторой стране из Столицы выходит 21 дорога, а из города Крайний — одна, а из всех остальных городов — по 20. Докажите, что из Столицы можно доехать до Крайнего (возможно, с пересадками).

Решение

Рассмотрим компоненту связности графа дорог, содержащую Столицу. Нам нужно доказать, что она содержит также и город Крайний. Предположим противное. Тогда в этой компоненте связности из одной вершины (Столицы) выходит 21 ребро, а из всех остальных вершин — по 20 ребер. Таким образом, в этом графе (компоненте связности) ровно одна нечетная вершина. Противоречие.

Пример

В стране из каждого города выходит 100 дорог и от любого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь от любого города можно добраться до любого другого.

Решение

Если закрыта дорога AB, то нам достаточно доказать, что и после этого можно добраться из A в B. Рассмотрим компоненту связности, содержащую вершину A. Если в этой компоненте нет вершины B, то в этой компоненте все вершины кроме A имеют четную степень. Но наличие ровно одной вершины с нечетной степенью противоречит следствию из леммы о рукопожатиях.

Определение

Два графа называются изоморфными, если у них поровну вершин, и вершины каждого графа можно занумеровать числами так, чтобы вершины первого графа были соединены ребром тогда и только тогда, когда соединены ребром соответствующие (занумерованные теми же числами) вершины второго графа.

Определение

Граф H, множество вершин V′ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V′ называется подграфомграфа G.

1. В государстве 100 городов и из каждого из них выходит ровно 4 дороги. Чему равно число дорог в этой стране?

Решение

Воспользуемся леммой о рукопожатиях. Удвоенное число ребер в графе равно сумме степеней всех вершин. Тогда получаем 2e=100⋅4, т.е. e=200.

2. В стране Озерная 7 озер, соединенных между собой 10 непересекающимися каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

Решение

Рассмотрим граф, вершины которого будут соответствовать озёрам, а рёбра — каналам. Он планарный, так как его можно изобразить картой страны Озёрной. Воспользуемся формулой Эйлера для плоских графов. Пусть в графе В вершин, Р рёбер и Г частей на которые он разбивает плоскость (граней). Тогда В-Р+Г=2. Подставим В=7 и Р=10. Получаем Г=2+Р-В=5. Это количество островов плюс один материк. Значит, островов на один меньше.

3. В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?

Решение

 

4. Жук ползет по ребрам куба. Какое минимальное число ребер нужно удалить, чтобы он мог проползти по всем ребрам по одному разу?

Решение

Заметим, что у нас есть восемь вершин, из которых выходит по три ребра. Но если жук проползет по всем ребрам, то не более чем из двух вершин может исходить нечетное число ребер (из начальной и конечной). Таким образом нужно изменить степень у шести вершин с нечетной степенью. Так как одно ребро меняет степень только двух вершин, то нужно удалить минимум три ребра. Пример очевиден — удаляем любые три параллельных ребра.

5. В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?

Решение

Докажем, что меньше, чем 21 линией не обойтись. Действительно, если 15 городов соединены авиалиниями так, что можно добраться от любого города до любого другого, то авиалиний не меньше 14.

Обозначим количество линий у авиакомпаний через a, b и c. По доказанному, у любых двух компаний вместе не менее 14 линий, то есть a+b⩾14, b+c⩾14, c+a⩾14. Складывая эти неравенства, получаем: 2(a+b+c)⩾42, то есть у трех компаний в сумме не менее 21 авиалинии.

Осталось привести пример с 21 авиалинией:

 

Определение 1. Граф называется связным если из любой его вершины по ребрам можно дойти до любой другой.

Определение 2. Деревом называется связный граф без циклов.

Теорема (свойства деревьев):

а) В дереве с n вершинами ровно n–1 ребро.

б) Если в связном графе n–1 ребро, то это – дерево.

o   В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы по оставшимся дорогам из каждого города можно было проехать в каждый?

Решение.

 Найдем ответ на другой вопрос. Сколько дорог можно оставить? Схема дорог соединяющих города страны – граф. Вершины в этом графе – города, ребра – дороги. Закрыть дороги, значит выкинуть ребра из графа. Чтобы по оставшимся дорогам из каждого города можно было проехать в каждый, граф должен быть связным. Если в графе есть фрагмент - цикл, то из него можно «разорвать», т.е. выкинуть из цикла одно ребро, все равно останется связный граф. Таким образом, в минимальном случае останется связный граф без циклов – то есть дерево. Так как в дереве ребер на одно меньше чем вершин, то останется 29 дорог.

В стране каждый город соединен с каждым, т.е. дорог в нем  . Закрыть можно 435-29 = 406. Ответ. Можно закрыть 406 дорог.

o   Волейбольная сетка имеет вид прямоугольника размером 50 × 200 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?

Решение 1.

Поступим аналогично решению задачи 2. Сколько веревочек на сетке останется? Узлы сетки – вершины графа, веревочки – ребра. Останется связный граф без циклов, т.е. дерево. Узлов на сетке  , значит останется   веревочка. Посчитаем количество веревочек-ребер (сторон клеток). Вертикальных сторон будет  , а горизонтальных  , т.о. всего ребер  .

Значит, перерезать можно  веревочек. Ответ. Разрезать можно 10000веревочек.

Решение 2.

 Мы знаем, что наименьшее число ребер будет в дереве, причем в любом дереве одинаковое. Поэтому сделаем произвольное дерево, посчитав, сколько ребер разрезали.

Разрежем все горизонтальные ребра, кроме самого верхнего в своем столбце (оно толстое, его сложнее резать). Мы разрезали   ребер. Осталось дерево, т.к. нет циклов.

o   Можно ли раскрасить ребра куба в два цвета так, чтобы по ребрам каждого цвета можно было пройти из любой вершины в любую?

Решение.

Чтобы по ребрам одного цвета можно было попасть из каждой вершины в каждую нужно, чтобы одноцветные ребра образовывали связный граф. В кубе 8вершин, значит, в одноцветном графе будет не меньше 7 ребер. Так как таких одноцветных графа должно быть 2, то в кубе должно быть не меньше 14 ребер, а в нем всего 12 ребер. Ответ. Нельзя так покрасить ребра.

o   У Царя Гвидона было 5 сыновей. Среди его потомков 100 имели каждый ровно по 3 сына, а остальные умерли бездетными. Сколько потомков было у царя Гвидона?

Решение 1.

Схему родственных отношений семьи Гвидона можно представить в виде графа. Вершины графа – Гвидон и потомки, ребра – родственная связь «отец-сын». Этот граф будет деревом (в нем нет циклов так как у человека не может быть двух отцов). В этом графе будет   ребер «отец-сын». Так как этот граф – дерево, то в нем 306 вершин (одна из вершин – Гвидон). Значит потомков у Гвидона – 305.

Решение2.

Пусть всего было n потомков. Из них 100 имели по 3 сына, а остальные   – умерли бездетными. Нарисуем соответствующий граф (двух людей соединим ребром, если один из них отец другого). В этом графе n+1 вершина (кроме потомков есть еще сам Гвидон). Посмотрим сколько от вершин отходит ребер. От Гвидона ведет 5ребер, от n-100 вершин ведет всего по одному ребру (т.к. они умерли бездетными, то есть только одно ребро, ведущее к отцу), и еще от 100 вершин ведет по 4 ребра (три ребра к сыновьям и одно к отцу). Посчитаем, сколько всего ребер:  . Но с другой стороны, этот граф – дерево, поэтому ребер в нем должно быть на 1 меньше чем вершин, т.к. вершин n+1, то ребер n. Получили уравнение, откуда n=305.

Ответ: 305.

o   В стране 15 городов, некоторые из них соединены авиалиниями, принадлежащими трем авиакомпаниям. Известно, что даже если любая из авиакомпаний прекратит полеты, можно будет добраться из любого города в любой другой (возможно, с пересадками), пользуясь рейсами оставшихся двух компаний. Какое наименьшее количество авиалиний может быть в стране?

Решение.

Пусть компании обслуживают k, l и m рейсов соответственно. Если выключить первую компанию, останется (l +m) рейсов, и это не меньше, чем 14, раз страна осталась связной. Аналогично для других пар: (l + k)≥14, (m + k)≥14 . Сложим эти неравенства, получим:

(k + l) + (l + m) + (m + k) ≥ 42        k + l + m ≥ 21     Мы доказали, что количество рейсов не меньше, чем 21. Теперь построим пример на 21рейс:   Ответ: 21.

Тема 8: Игры

Во всех играх предполагается, что играют двое, ходы делаются по очереди (игроки не могут пропустить ход). И ответить всегда надо на один и тот же вопрос: «Кто побеждает: начинающий (первый) или его партнер (второй)?».

Игры-шутки.

Это игры, исход которых не зависит от того, как играют соперники. Поэтому для решения такой игры не нужно указывать выигрышную стратегию. Достаточно лишь доказать, что выигрывает тот или иной игрок (независимо от того, как будет играть).

Пример

Двое по очереди ломают шоколадку 6×86×8. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход.

Решение

Заметим, что после каждого хода количество кусков увеличивается ровно на 1. Сначала был один кусок, а в конце игры, когда нельзя сделать ни одного хода, шоколадка разломана на 48 маленьких долек. Таким образом, игра будет продолжаться ровно 47 ходов. Последний, 47-й ход (нечетный по счету ход), сделает первый игрок. Поэтому он в этой игре побеждает, причем независимо от того, как будет играть.

Симметричные стратегии

Пример

Двое по очереди кладут пятаки на круглый стол, причем так, чтобы они не накладывались друг на друга. Проигрывает тот, кто не может сделать ход.

Решение

В этой игре выигрывает первый. Первым ходом он кладет пяток так, чтобы центры монеты и стола совпали. После этого каждый ход второго игрока начинающий отвечает симметрично относительно центра стола. Отметим, что при такой стратегии после каждого хода первого игрока позиция симметрична. Поэтому, если возможен очередной ход второго игрока, то возможен и симметричный ему ответный ход первого. Следовательно, он побеждает.

При доказательстве правильности симметричной стратегии нельзя забывать о том, что очередному ходу может помешать только что сделанный ход соперника. Ранее сделанные ходы в силу симметричности позиции помешать не могут.

Поэтому чтобы решить задачу при помощи симметричной стратегии‚ необходимо найти симметрию, при которой только что сделанный противником ход не препятствует осуществлению выбранного плана игры.

Пример

Имеется две кучи камней по семь камней в каждой. За ход разрешается взять любое количество камней, но только из одной кучки. Проигрывает тот, кому нечего брать.

Решение

В этой игре второй игрок побеждает при помощи симметричной стратегии. Каждым своим ходом он должен брать столько же камней, сколько предыдущим ходом взял первый игрок, но из другой кучки. Таким образом, у второго игрока всегда есть ход.

Выигрышные позиции

Пример

Ладья стоит на поле a₁. За ход разрешается сдвинуть ее на любое число клеток вправо или на любое число клеток вверх. Выигрывает тот, кто поставит ладью на поле h₈.

Решение

В этой игре побеждает второй игрок. Его стратегия такова: каждым своим ходом он возвращает ладью на диагональ a₁−h₈. Первый игрок каждый раз вынужден будет уводить ладью с этой диагонали, а второй игрок после этого будет иметь возможность вернуть ладью па линию a₁−h₈. Так как поле h₈ принадлежит диагонали, то на него сумеет встать именно второй игрок.

При решении этой задачи нам удалось выделить класс выигрышных позиций (ладья стоит в одной из клеток диагонали a₁−h₈)‚ обладающих следующими свойствами:

1. Завершающая игру позиция является выигрышной.
2. За ход из одной выигрышной позиции нельзя попасть в другую.
3. Из любой невыигрышной позиции за один ход можно попасть в какую-то выигрышную.

Нахождение такого класса выигрышных позиций для игры равносильно ее решению. Действительно к победе ведет такая стратегия: ходи в выигрышную позицию. Если исходная позиция выигрышная, то выигрывает второй. В противном случае выигрывает первый.

Задача 1.

Двое выписывают n -значное число, выставляя по очереди по одной цифре, начиная со старшего разряда (потом заполняют следующий разряд и т.д.). Если получившееся число разделится нацело на 7, то выигрывает второй игрок, иначе — начинающий. 

Решение задачи

Заметим, что тот игрок, который последним делает ход может поставить любую цифру от 0 до 6, тем самым он может создать 7 чисел с различными остатками при делении на 7 (в том числе и с нулевым остатком). Значит, этот игрок и выигрывает. Осталось правильно понять, кто делает ход последним. Если n  — четно, то второй игрок, если n  — нечетно, то начинающий.

n=6  второй игрок

n=7  начинающий игрок

n=8  второй игрок

Задача 2

Имеется 10 фишек: 2 белых, 2 чёрных, 2 красных, 2 синих и 2 зелёных. Игроки А и Б ставят по очереди по одной фишке в одной из вершин 10-угольника. Игрок А хочет получить 5 последовательных вершин всех пяти цветов, а игрок Б хочет этому помешать. Игру начинает Б. 

 Решение задачи

Выигрывает второй игрок, т.е. А. Он будет использовать симметричную стратегию. После каждого хода Б, он будет класть в противоположную вершину фишку того же цвета, что и Б. В результате никакие две фишки одного цвета не будет находится среди последовательных пяти фишек, значит, среди любых последовательных пяти фишек будут присутствовать все цвета. Т.е. выигрывает А.

Ответ: А

Задача 3

По кругу расставлено 9 чисел - 4 единицы и 5 нулей. Каждую секунду над числами проделывают следующую операцию: между соседними числами ставят нуль, если они различны, и единицу, если они равны; после этого старые числа стирают. Могут ли через некоторое время все числа стать одинаковыми? Укажите, через какое число шагов это состояние возникнет первый раз (укажите 0, если достичь невозможно).

 Решение задачи

Первая комбинация из девяти единиц может получиться только из комбинации девяти нулей. Если же получилось девять нулей, то на предыдущем ходу нули и единицы чередовались, что невозможно, так как их нечетное количество.

Задача 4

В ряд лежат nn монет. За ход разрешается брать одну или две рядом лежащие монеты. Проигрывает тот, кому нечего брать. При каких nn у первого игрока есть выигрышная стратегия?

Решение задачи

Если n — нечетное, то пусть первый заберет центральную монету. Если же n — четное, то пусть первый заберет две центральных монеты. Тогда (в обоих случаях) у нас останется две одинаковые кучи монет. Теперь заметим, что по правилам игры мы не можем брать монеты из разных куч, поэтому можно применить симметричную стратегию (её может применить первый игрок). Эта стратегия такова: мы будем брать то же количество монет, которое взял второй игрок, на соответствующих симметричных позициях из другой кучи. Так как после нашего хода всегда получаются две кучи с одинаковым числом монет и симметричным расположением, а после хода второго количество монет в кучах разное, то при такой стратегии первый игрок победит.

(Ответ: 38,39,40,41,42,43,44,45,46,47,48)

Задача 5

На доске размером n×n двое по очереди закрашивают клетки так, чтобы не появлялось закрашенных уголков из трех клеток. Проигрывает тот, кто не может сделать ход. При каких nn выигрывает второй игрок?

Решение задачи

Для четных n выиграет второй игрок, если он будет ходить симметрично первому (относительно центра доски). В самом деле, играя таким образом, он всегда сможет сделать ход, и при его ходе не может появиться закрашенный уголок — иначе он появился бы на предыдущем ходу. В случае нечетных n первый своим первым ходом красит центральную клетку и тоже применяет симметричную стратегию.

(Ответ:14,16)

Тема 9: Оценка плюс пример 

Оценка плюс пример — это метод решения задач, который применяется при нахождении наибольших или наименьших значений. Суть метода состоит в следующем. Предположим, что мы ищем наименьшее значение некоторой величины A. Действуем в два этапа:

1. Оценка. Показываем, что выполнено неравенство A⩾α.
2. Пример. Предъявляем пример, когда достигается равенство A=α.

Тем самым доказываем, что наименьшее значение величины A равно α.

ПРИМЕР

Найти наименьшее значение функции f(x)=x²+2x−3.

РЕШЕНИЕ

Выделим полный квадрат: f(x)=(x+1)²−4. Поскольку квадрат числа неотрицателен, получаем оценку: f(x)⩾−4.

Приводим пример, когда равенство достигается: f(−1)=−4. Следовательно, искомое наименьшее значение равно −4.

Ответ. −4.

ПРИМЕР

ПРИМЕР

Несколько камней весят вместе 10 тонн, при этом каждый из них весит не более одной тонны. На каком наименьшем количестве трехтонок можно увезти этот груз за один раз? 

РЕШЕНИЕ

Покажем, что на пяти трехтонках можно увезти весь груз за один раз. Действительно, на каждой из четырех первых трехтонок можно увезти более 2 тонн камней. То есть первые четыре машины увезут по крайней мере 8 тонн камней. Оставшиеся камни (суммарным весом менее 2 тонн) увезет пятая машина.

Покажем теперь, что четырех машин может не хватить. Действительно, если бы изначально было 13 камней весом по 10/13тонн каждый, то каждая трехтонка может увезти только 3 таких камня. То есть 4 трехтонки могут увезти лишь 12 из 13 камней.

Ответ. 5.

ПРИМЕР

Каково наименьшее натуральное n такое, что n! делится на 18, на 19, на 20 и на 21?  

РЕШЕНИЕ

Заметим, что число 19 — простое, поэтому если n<19, то n! не делится на 19. Осталось понять, что 19! делится и на 18, и на 19, и на 20 (20=4⋅520=4⋅5), и на 21 (21=3⋅721=3⋅7).

Ответ. 19.

ПРИМЕР

Все члены конечной последовательности являются натуральными числами. Каждый член этой последовательности, начиная со второго, либо в 13 раз больше, либо в 13 раз меньше предыдущего. Сумма всех членов последовательности равна 6075. Какое наибольшее количество членов может быть в последовательности? 

РЕШЕНИЕ

Ясно, что чисел в последовательности будет тем больше, чем меньше сами числа. Поэтому надо по максимуму использовать 1 и 13, чередуя их. Попробуем так и начать: 1, 13, 1, 13, … Эта последовательность состоит из идущих друг за другом пар (1; 13); сумма в каждой паре равна 14. Какое число будет последним? Очевидно, 13 в конце оказаться не может — тогда сумма всех членов последовательности будет делиться на 14, а 6075 — число нечетное. Остается проверить единицу. Делим 6075 на 14 с остатком и получаем: 6075=14⋅433+13. Значит, и единицы в конце быть не может.

Наша последовательность не подошла, но результат деления с остатком подсказывает, что нужно сделать. Изменим чередование: 13, 1, 13, 1, … Тогда после 433 пар (13; 1) мы сможем завершить последовательность числом 13. Таким образом, нам удалось обойтись только числами 1 и 13, и возникает ощущение, что это и есть наиболее длинная последовательность. Теперь попробуем это аккуратно доказать.

Покажем, что больше чем 433⋅2+1=867 членов быть не может. Предположим обратное: наша последовательность a₁, a₂, a₃, …содержит не менее 868 членов. Разобьем их последовательно на пары: (a₁;a₂); (a₃;a₄); … Сумма чисел в каждой паре как минимум 14, а самих пар не менее 434. Сумма всех членов получится тогда не менее 14⋅434=6076, что противоречит условию.

Значит, в последовательности может быть самое большее 867 членов.

Ответ. 867.

Задача 1.

Какое наименьшее неотрицательное число может получиться, если расставить знаки "+" или "-" между каждыми двумя соседними цифрами числа 123456789?

Решение задачи

Воспользуемся правилом: сумма нечетного числа нечетных чисел — нечетное число. После того как мы расставим знаки плюсы или минусы между цифрами 123456789 число нечетных слагаемых будет равно 5, т.е. нечетно. Следовательно, число, которое получается в результате арифметических действий, должно быть обязательно нечетным (независимо от того, как расставлены знаки). Значит, наименьшее неотрицательное значение больше или равно 1. Несложно убедиться, что число 1 можно получить:

1+2−3−4+5+6−7−8+9=1.

Ответ:1

Задача 2.

Найдите наибольшее натуральное n, что существует выпуклый n-угольник, у которого все углы измеряются целым числом градусов.

Решение задачи

Заметим, что если каждый угол измеряется целым числом градусов, то он не более 179∘. Значит внешний угол, соответствующий ему не менее 1∘. У каждого выпуклого n-угольника сумма внешних улов равна 360∘. Значит внешних углов не более 360. Поэтому, всего углов не более 360.

 В качестве примера можно взять правильный 360-угольник (у него все углы по 179∘).

Ответ:360

Задача 3.

На острове живут рыцари и лжецы, всего 2014 человек. Рыцари всегда говорят правду, а лжецы всегда лгут. Каждый житель острова заявил: "Среди оставшихся жителей острова более половины — лжецы". Какое максимальное количество лжецов может быть на острове?

Решение задачи

Ответ:1007

Задача 4.

Числа от 1 до 10 разбили на две группы так, что произведение чисел в первой группе нацело делится на произведение чисел во второй. Какое наименьшее значение может быть у частного от деления первого произведения на второе?

Решение задачи

Рассмотрим числа от 1 до 10. Среди них есть ровно одно, которое делится на 7 (это само число 7). Поэтому 7 не может быть во второй группе (иначе произведение чисел первой группы должно было бы делится на 7). Значит, семерка в первой группе. Поэтому частное не меньше 7. Приведем пример, показывающий, что есть разбиение на группы с частным произведений равным 7: {3,5,6,7,8}, {1,2,4,9,10}.

Ответ:7

Задача 5.

Круглая мишень разбита на 20 секторов, которые заполняются по кругу в каком-либо порядке числами 1,2,…,20 (естественно, каждое число берется лишь один раз). Если секторы занумерованы, например, в следующем порядке (1, 20, 5, 12, 9, 14, 11, 8, 16, 7, 19, 3, 17, 2, 15, 10, 6, 13, 4, 18), то наименьшая из разностей между номерами соседних (по кругу) секторов равна 12−9=3. Каково наибольшее возможное значение этой величины (наименьшей из разностей)?

Решение задачи

Если секторы занумерованы в следующем порядке: (1, 11, 2, 12 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19, 10, 20), то наименьшая из разностей между соседними номерами равна 9. Эта величина не может быть больше 9, так как в противном случае при любой нумерации рядом (и слева, и справа) с сектором номер 10 может находиться только сектор с номером 20, что невозможно.

Тема 10: Вневписанная окружность треугольника

ТЕОРЕМА

В любом треугольнике биссектрисы двух внешних углов и биссектриса внутреннего угла, не смежного с ними, пересекаются в одной точке.

Доказательство

Из доказательства предыдущей теоремы следует, что OF=OG=OH. Значит, точки F, G и H лежат на одной окружности с центром в точке O.

ОПРЕДЕЛЕНИЕ

Вневписанной окружностью треугольника называется окружность, которая касается стороны треугольника и продолжений двух других сторон.

Из предыдущей теоремы следует, что у каждого треугольника есть три вневписанные окружности.

ТЕОРЕМА

Пусть вневписанная окружность касается стороны AC треугольника ABC. Тогда отрезки касательных от вершины B до точек касания с вневписанной окружностью равны полупериметру треугольника.

Доказательство

Пусть данная вневписанная окружность касается продолжений сторон BA и BC в точках K и L соответственно, а стороны AC в точке N. Тогда известно, что

BK=BL,AK=AN,CL=CN, поскольку касательные, проведенные к окружности из одной точки, равны. Отсюда следует, что 2BK=BK+BL=(BA+AK)+(BC+CL)=(BA+AN)+(BC+CN)= =BA+BC+AN=CN=BA+BC+AC=PABC,

что и требовалось доказать.

Тема 11: Принцип крайнего. Комбинаторная геометрия

Принцип крайнего

ПРИМЕР

На каждой из 15 планет, расстояния между которыми попарно различны, находится по астроному, каждый из которых наблюдает за ближайшей к нему планетой. Докажите, что некоторую планету никто не наблюдает. 

РЕШЕНИЕ

Отметим сразу, что если на какую-нибудь планету смотрят сразу два астронома, то на какую-то планету никто не смотрит (так как планет и астрономов одинаковое количество). Предположим поэтому, что за каждой планетой наблюдает ровно один астроном. Рассмотрим две планеты, расстояние между которыми наименьшее среди всех попарных расстояний. Ясно, что астрономы, находящиеся на этих двух планетах, смотрят друг на друга. Посмотрим теперь на оставшиеся 13 планет. Из них опять можно выбрать две с наименьшим расстоянием — астрономы, находящиеся на них, должны смотреть друг на друга. Продолжая такие рассуждения, мы найдем планету, которую никто не наблюдает (так как число 15 нечетно).

ПРИМЕР

По кругу выписано несколько чисел, каждое из которых равно среднему арифметическому своих соседей. Докажите, что все числа равны.

РЕШЕНИЕ

Рассмотрим максимальное из этих чисел. С одной стороны, оно не меньше каждого из своих соседей, а с другой стороны, равно их среднему арифметическому. Поэтому это число должно быть равно каждому из своих соседей. Аналогичным образом продолжая рассматривать следующих соседей, доказываем, что все числа, стоящие по кругу, равны между собой.

ПРИМЕР

Докажите, что не существует попарно различных натуральных чисел k, ℓ, m,n, для которых было бы справедливо равенство: k^k + ℓ^ℓ = m^m + nⁿ.

РЕШЕНИЕ

Предположим, что такие числа все-таки нашлись. Пусть, например, n — наибольшее из этих чисел. Тогда n⩾4, а значит,

 что противоречит предположению. Следовательно, таких чисел не существует.

ПРИМЕР

На плоскости синим и красным цветом окрашено несколько точек так, что никакие три точки одного цвета не лежат на одной прямой (точек каждого цвета не менее трех). Докажите, что можно найти треугольник с одноцветными вершинами, на трех сторонах которого лежит не более двух точек другого цвета. 

РЕШЕНИЕ

Из всех треугольников с одноцветными вершинами выберем треугольник наименьшей площади. Допустим, что на его сторонах расположено не менее трех точек другого цвета. Так как они не могут все лежать на одной стороне этого треугольника, то эти три точки являются вершинами некоторого треугольника, площадь которого, очевидно, меньше площади первоначально выбранного треугольника, а это противоречит тому, что тот треугольник имел наименьшую площадь из всех треугольников с одноцветными вершинами.

ПРИМЕР

ПРИМЕР

Можно ли на плоскости расположить 1000 отрезков так, чтобы каждый отрезок обоими своими концами упирался строго внутрь каких-то двух других отрезков? 

РЕШЕНИЕ

Пусть на плоскости расположено 1000 отрезков. Возьмем произвольную прямую ℓ, не перпендикулярную ни одному из них (ясно, что такая прямая существует, так как отрезков конечное число, а различных направлений бесконечно много). Спроецируем концы всех этих отрезков на прямую ℓ. Очевидно, что конец отрезка, проецирующийся в самую правую из полученных точек (можно считать, что на прямой задана некоторая ориентация), не может упираться строго внутрь какого-то другого отрезка.

ПРИМЕР

На плоскости дано конечное множество многоугольников (не обязательно выпуклых), каждые два из которых имеют общую точку. Докажите, что существует прямая, имеющая общие точки со всеми этими многоугольниками. 

РЕШЕНИЕ

Возьмем на плоскости произвольную прямую ℓ и спроецируем на нее все многоугольники. При этом мы получим несколько отрезков, любые два из которых имеют общую точку. Рассмотрим левые концы этих отрезков и выберем из них самый правый (мы считаем, что на прямой задана какая-то ориентация). Легко понять, что полученная точка принадлежит всем отрезкам, поэтому проведенный через нее перпендикуляр к прямой ℓ пересекает все данные многоугольники.

Комбинаторная геометрия

Комбинаторная геометрия (дискретная геометрия) — раздел математики, в котором изучаются геометрические объекты с точки зрения комбинаторики (дискретной математики). То есть мы рассматриваем конечное число (или счетное число) геометрических объектов и пытаемся понять их свойства. Эта область математики связана с теорией графов, теорией чисел и многими другими разделами геометрии и комбинаторики. Как более-менее самостоятельная наука этот раздел математики сформировался в конце XIX века — начале XX века.

Одним из старых вопросов, который относится к комбинаторной геометрии, является вопрос о контактном числе. Обсуждался он еще в XVII веке Ньютоном и Грегори. Звучит он вот так: чему равно максимальное число единичных шаров, которые касаются данного единичного шара и при этом не пересекаются (касаться друг друга они могут)? Ньютон считал, что это число равно 12, а Грегори выдвигал гипотезу, что 13. Лишь в середине XX века удалось строго доказать, что был прав Ньютон (на рисунке изображено, как можно расположить 12 шаров, касающихся центрального).

Ниже мы рассмотрим несколько простых задач по комбинаторной геометрии.

ПРИМЕР

Прямая раскрашена в два цвета. Докажите, что найдется отрезок, оба конца и середина которого покрашены в один и тот же цвет.

Решение

ПРИМЕР

Плоскость раскрашена в два цвета. Докажите, что найдутся две точки одного цвета, расстояние между которыми равно 1.

РЕШЕНИЕ

Рассмотрим равносторонний треугольник со стороной 1. Какие-то две из его трех вершин имеют одинаковый цвет.

ПРИМЕР

На плоскости дано 300 точек, никакие 3 которых не лежат на одной прямой. Докажите, что существует 100 попарно не пересекающихся треугольников с вершинами в этих точках.

РЕШЕНИЕ

Примем за ось x любую прямую, не перпендикулярную ни одной из прямых, соединяющих пары данных точек. Обозначим координаты данных точек через x₁, x₂, …, x₃₀₀ в порядке возрастания (x₁<x₂<…<x₃₀₀). В качестве первого треугольника возьмем тот, вершины которого проецируются в x₁, x₂, x₃; второго — с вершинами x₄, x₅, x₆  и т. д. Проекции на ось x полученных 100 треугольников не пересекаются. Значит, и сами треугольники не пересекаются.

Примеры олимпиадных работ

7 класс.

1. Что больше:  1234567·1234569 или  1234568² ?
2. Магазин продал одному покупателю 25% полотна, второму – 30% остатка, а третьему – 40% нового остатка. Сколько  процентов полотна осталось?
3. Учитель математики, проверив контрольные работы у трех друзей: Алексея, Бориса и Василия, сказал им: «Все вы написали работу, причем получили разные отметки («3», «4», 5»). У Василия — не «5», у Бориса — не «4», а у Алексея, по моему, «4». Впоследствии оказалось, что учитель ошибся: одному ученику сказал отметку верно, а другим двум неверно. Какие отметки получил каждый из учеников?
4. Дворец имеет форму прямоугольника размером 13х15. Каждая клетка, кроме центральной, - комната замка, а в центральной клетке находится бассейн. В каждой стене (стороне клетки), разделяющей две соседние комнаты, есть дверь. Можно ли, не выходя из дворца и не заходя в бассейн, обойти все комнаты, побывав в каждой ровно по одному разу?
5. Дан угол в 13°. Как получить угол в 11°?

Решения и ответы:

1. 1234568² > 1234567·1234569

1234567·1234569= (1234568-1)·(1234568+1)= 1234568²-1²

1234568² > 1234568²-1²

2. 31,5%.

Пусть было 100% полотна.

После первой продажи осталось 100-25=75% полотна. После второй 100-30=70% остатка, а после третьей 100-40=60% нового остатка. Значит, осталось 100·0,75·0,7·0,6=0,315=31,5%.

3. Алексей получил «5», Борис – «4», Василий – «3».

Рассмотрим три случая.

1 случай. Пусть учитель сказал верно Алексею. Значит, у Алексея – «4». Т.к.  Борису и Василию учитель назвал неверные отметки, то у Бориса – «4», а у Василия – «5». Получилось, что у двух учеников оказались одинаковые отметки, что противоречит условию задачи. Данный случай невозможен.

2 случай. Пусть учитель сказал верно Василию. Тогда у Василия отметка – не «5». Т.к. учитель сказал неверно об отметках Алексея и Бориса, то  у Алексея отметка не «4», а у Бориса – «4». Тогда у Алексея – «5», у Василия – «3».

3 случай. Пусть учитель сказал верно Борису. Тогда Борис получил не «4». Т.к. утверждения про отметки Алексея и Василия ложные, то у Алексея – не «4», у Василия – «5». Получается, что отметку «4» никто не получил. Этот случай тоже противоречит условию задачи.

4. Нельзя.

Раскрасим прямоугольник в шахматном порядке так, чтобы центральная клетка была черная. При этом клеток черного цвета будет на 1 меньше, чем белых клеток. В центральной клетке находится бассейн, поэтому черных комнат на 2 меньше, чем белых. При переходе через дверь мы попадаем в комнату другого цвета, т.е. цвет комнат чередуется. Поэтому разность между количеством пройденных комнат разного цвета не более одного (т.к. путь распадается на пары клеток разного цвета, исключая, может быть, последнюю). Значит, обойти все комнаты, побывав в каждой ровно по одному разу, нельзя.

5. Отложить 13 раз угол по 13°, получим угол 169°. Тогда разность развернутого угла и 169° даст искомый угол: 180°-169°=11°.

8 класс.

1.    Докажите, что значение выражения  есть число рациональное.

2.      Товар подорожал на 10%, а затем еще на 20%. Как изменилась цена этого товара?

3.      На какую цифру оканчивается число З²⁰⁰⁴ + 4²⁰⁰⁵?

4.      Аня младше Вани. Когда Ване было столько лет, сколько Ане сейчас, их матери было на 3 года меньше, чем Ане с Ваней теперь. Сколько лет было Ване, когда матери было столько лет, сколько Ване теперь?

5.      Найдите сумму пяти внутренних углов произвольной пяти­конечной звезды.

Ответы и решения:

1.   

2. Увеличилась на 32%.

Новая цена равна 1,1·1,2=1,32 от старой цены. Увеличение цены составит

 (1,32-1)·100%=32%.

3. На цифру 5.

Найдем последнюю цифру Зⁿ при различных значениях n: 1;2;3;4;5;6… Замечаем зависимость: через 4 числа последняя цифра повторяется (3;9;7;1;3;9…).Т.к. 2004=501·4+0, то число З²⁰⁰⁴  оканчивается такой же цифрой, что и З⁴  ,то есть 1. Рассматривая различные степени числа 4, получаем зависимость: если показатель степени четный, то число оканчивается цифрой 6, если нечетный – цифрой 4. Значит, число 4²⁰⁰⁵ оканчивается цифрой 4. Следовательно, число З²⁰⁰⁴ + 4²⁰⁰⁵оканчивается на цифру 5.

4. 3 года.

Пусть Ане сейчас а лет, Ване – b лет, маме – с лет. Ване было а лет, т.е. столько, сколько сейчас Ане, (b-а) лет назад. Маме тогда было с-(b-а)=с-b+а, и это число равно а+b-3. Значит, с=2b-3. Маме было b лет, т.е. столько, сколько Ване теперь, (с-b) лет назад, но Ване тогда было  b-с+b=2b-с=3.

Итак, Ване было 3 года.

5. На рис. 1:     ∠7= ∠1+∠3,  ∠6=∠2+ ∠5 (по теореме о свойстве внешнего угла треугольника). Тогда   ∠1+ ∠2+∠3+ ∠ 4+ ∠5=∠7+ ∠6+ ∠4=180°.

            Рис.1

9 класс

Задачи

9.1.(7баллов). Вычислить сумму дробей , если произведение  переменных  xyz  = 1.

9.2. (7баллов). Найдите действительные корни уравнения  (х + 2) ⁴ + х ⁴ = 82.

9.3. (7баллов). В ∆ ABC угол  ABC равен  60º. Внутри треугольника взята точка Р так, что углы  АРВ,  ВРС и  СРА равны 120º. Известно, что АР  = а. Найдите площадь ∆ BРC.

9.4. (7баллов). При каких значениях параметра р разность корней уравнения

p x² + x – 2 = 0 равна 3? 

9.5.(7баллов). В гостиницу приехал путешественник. Денег у него не было. Он имел серебряную цепочку, состоящую из 7 звеньев. За каждый день пребывания в гостинице он расплачивался одним звеном цепочки. Хозяин предупредил, что согласен взять не более одного распиленного звена, а остальные должны быть целыми. Как путешественнику распилить цепочку, чтобы прожить в гостинице неделю и ежедневно расплачиваться с хозяином?

Ответы и решения

9.1. Вычислить сумму дробей , если произведение  переменных  xyz = 1.

Решение. Преобразуем дроби так, чтобы знаменатели каждой дроби были равны и содержалось произведение xyz. Для этого умножим числитель и знаменатель второй дроби на х, а третьей - на  xy. Получим: 

. Ответ: 1.

9.2. Найдите действительные корни уравнения  (х + 2) ⁴ + х ⁴ = 82.

Решение. Обозначим  х + 1 =  у, тогда  х + 2 = у + 1, х = у – 1. Исходное уравнение примет вид (у + 1) ⁴ + (у – 1) ⁴  = 82.

у ⁴ + 6у ² – 40 = 0, откуда  у ² = - 10  (это уравнение не имеет корней) или  у ² = 4. Тогда у = - 2 или у = 2. Следовательно, х + 1 =  - 2 или  х + 1 =   2.

В итоге получаем корни 1 и – 3.

Ответ: - 3 и 1.

9.3. В ∆ ABC угол  ABC равен 60º. Внутри треугольника взята точка Р так, что углы АРВ,  ВРС и  СРА равны 120º. Известно, что АР  = а. Найдите площадь ∆ BРC.

Решение.

9.4.  При каких значениях параметра р разность корней уравнения

px² + x – 2 = 0 равна числу 3?

Ответ: .

Решение. Пусть корни исходного уравнения х₁ и х₂. Применяя теорему Виета, запишем систему уравнений     Решая первое и третье уравнения системы получим ,  и, подставив эти выражения во второе  уравнение, получим равенство 9р² – 8р – 1 = 0,  откуда .

Ответ:

9.5. В гостиницу приехал путешественник. Денег у него не было. Он имел серебряную цепочку, состоящую из 7 звеньев. За каждый день пребывания в гостинице он расплачивался одним звеном цепочки. Хозяин предупредил, что согласен взять не более одного распиленного звена, а остальные должны быть целыми. Как путешественнику распилить цепочку, чтобы прожить в гостинице неделю и ежедневно расплачиваться с хозяином?

Решение. Если распилить третье звено, то цепочка распадается на три части: 1, 2 и 4 звена. С их помощью удается расплатиться, так как хозяин может давать сдачу звеньями, которые он получил раньше.

9 класс.

Задачи

1.                Найдите значение выражения:

(1+  при а=2008.

2.                Из Астрахани в Москву везли 80 т персиков, которые содержали 99% воды. По дороге они усохли и стали содержать 98% воды. Сколько тонн персиков привезли в Москву?

3.                В комнате собрались 8 человек. Некоторые из них лгут, а остальные – честные люди, всегда говорящие правду. Один из собравшихся сказал: «Здесь нет ни одного честного человека». Второй сказал: «Здесь не больше одного честного человека». Третий сказал: «Здесь не более двух честных людей» и т.д. до восьмого, который сказал: «Здесь не более семи честных людей». Сколько в комнате честных людей? Ответ обоснуйте.

4.                У отца спросили, сколько лет его двум сыновьям. Отец ответил, что если к произведению чисел, означающих их года, прибавить сумму этих чисел, то будет 14. Сколько лет сыновьям?

5.                 Постройте ромб, в котором высота равна 5 см, а одна из диагоналей 6 см.

Ответы и решения:

1. – 2007.

Применяя формулу последовательно для последних двух множителей, в результате получаем:

)=1-a.

При а =2008, 1-а=-2007.

2. 40т

В Астрахани в персиках содержался 1%,т.е. 8 т «сухого остатка», в Москве эти 8 т составляли уже 2% от привезенных персиков. Тогда вес персиков 8:2·100=40 т.

3. 4 человека.

Начнем рассуждения с высказывания восьмого человека: «Здесь не больше 7 честных людей». Если восьмой – честный, то все хорошо. Если он лжет, то в комнате 8 честных людей, что противоречит тому, что восьмой – лжец. Значит, восьмой не может лгать, он-честный. Первый сказал, что в комнате нет честных людей. Но восьмой – честный, поэтому – первый солгал. Рассматривая высказывание седьмого человека, получим, что он не может быть лжецом. Иначе в комнате должно быть 7 или 8 честных людей. Но первый – лжец. Поэтому седьмой – честный. Рассуждая далее аналогично, получим, что второй, третий и четвертый будут лжецами, а шестой и пятый – честными. Тогда в комнате будет 4 честных человека.

4. 2 года и 4 года.

Пусть одному сыну n лет, а другому m лет. Тогда

mn+m+n=14,

.

Поскольку m – натуральное число, а 15=5·3·1, то: а) либо n+1=5; б)либо n+1=3; в)либо n+1=1. В случае: а) n=4, тогда m=2; в случае б)n=2, тогда m=4; в случае в)n=0, чего не может быть, т.к. n – натуральное число. Следовательно, одному сыну 2 года, а другому 4 года.

5.                Построим прямой угол FEK. Затем на луче ЕF отложим отрезок ЕВ=5 см. Проведем окружность с центром в точке В и радиусом 6 см, а точку пересечения этой окружности со стороной ЕК обозначим через D. Проведем серединный перпендикуляр к отрезку ВD и прямую ВL, параллельную прямой ЕD. Точку пересечения данной прямой и серединного перпендикуляра обозначим за С, а точку пересечения серединного перпендикуляра с прямой ЕD обозначим за А. АВСD – искомый ромб.

10 класс

Задачи

10.1. (7 баллов). При каком т многочлены  Р (х) =  2х²– (3т + 2)х + 12 и 

G(x) = 4х²- (9т – 2)х + 36   имеют общий корень?

10.2  (7 баллов).    Построить график функции у = .

10.3. (7 баллов). Через вершины А  и  В единичного квадрата  ABCD проходит окружность, пересекающая прямые AD   и AC в точках К и М., отличных от А. Найдите длину проекции КМ  на  АС.

10.4. (7 баллов).  Найдите наименьшее целое значение параметра р, при котором для всех значений х выполняется неравенство х⁴ + 2х² + р  ≥ 4х.

10.5. (7 баллов). В гостиницу приехал путешественник. Денег у него не было. Он имел серебряную цепочку, состоящую из 7 звеньев. За каждый день пребывания в гостинице он расплачивался одним звеном цепочки. Хозяин предупредил, что согласен взять не более одного распиленного звена, а остальные должны быть целыми. Как путешественнику распилить цепочку, чтобы прожить в гостинице неделю и ежедневно расплачиваться с хозяином?

Ответы и решения

10.1. При каком т многочлены  Р (х) =  2х²– (3т + 2)х + 12 и 

G(x) = 4х²- (9т – 2)х + 36   имеют общий корень?

Ответ: т = 3.

Решение. Пусть х = t – общий корень этих многочленов. Тогда имеет место система     Умножим на (- 2) первое уравнение и сложим со вторым, получим (6 – 3т) t – 12 = 0, t = 0,25(т – 2). Подставим это значение t  в первое уравнение, получим:

 ∙ 4  = 0,    Итак,  т = 3.

Проверкой убеждаемся, что при т = 3 многочлены P(х) и  G(x) имеют общий корень х = 4.

10.2.  Построить график функции у = .

Решение. Используя свойства арифметического квадратного корня представим функцию в виде  . Раскрывая модули, получим    

График полученной функции построить несложно

10.3. Через вершины А  и  В единичного квадрата  ABCD проходит окружность, пересекающая прямые AD  и  AC в точках К и М., отличных от А. Найдите длину проекции КМ  на  АС.

Ответ: .

Решение. Будем считать что точка М лежит на прямой АС, а точка К на АD. Обозначим  через Т точку пересечения окружности с прямой ВС

11 класс.

11.1. (7 баллов). Сколько различных корней на отрезке   имеет уравнение

tg x - tg x + 3 sin x – 1 = 0 ?

   11.2. (7 баллов). Найдите все целые значения параметра  р, при которых уравнение           х ² + px + p = 0 имеет целый корень.

11.3. (7 баллов). Какие три цифры следует вычеркнуть в числе 123456789 так, чтобы получившееся  6 – значное число делилось на 72. Доказать, что полученное число  единственное.

11.4. (7 баллов).  Треугольную пирамиду разрезали по боковым ребрам и сделали развертку. Она оказалась квадратом со стороной 1 дм. Найдите объем пирамиды.

11.5. (7 баллов). В купе железнодорожного вагона имеется два противоположных дивана по 5 мест в каждом.  Из 10 пассажиров четверо желают сидеть лицом к паровозу, а трое - спиной к паровозу, остальным все равно, как сидеть. Сколькими способами могут разместиться пассажиры?

Ответы и решения

11.1. Сколько различных корней на отрезке   имеет уравнение

tg x - tg x + 3 sin x – 1 = 0 ?

 Ответ: два различных корня.

Решение. Преобразуем уравнение . (tg x + 3 sin x) – (tg x + 1) = 0,

3 sin xtg x + 1) - (tg x + 1) = 0,  (3 sin x – 1) (tg x + 1) = 0. Первый множитель  на отрезке   равен нулю дважды, а второй – один раз. При этом, если  sin x =  и  , то tg x =  . Тогда при этом значении х в нуль обращаются оба множителя полученного уравнения и оно имеет два корня.

11.2. Найдите все целые значения параметра  р, при которых уравнение

х ² + px + p = 0 имеет целый корень.

Ответ: при р = 0 корни х₁ = х₂ = 0;  при р = 4 корни х₁ = х₂ =  - 2.

Решение. Пусть корни уравнения х₁ и х₂. По теореме Виета х₁ + х₂ = - р,  х₁ · х₂ = р. Сложим эти два равенствам прибавим 1 к обеим частям полученного равенства. Получим (х₁ + х₂) + х₁ · х₂ + 1 = 1, (х₁ + 1) (х₂ + 1) = 1. Числа  х₁ + 1  и  х₂ + 1 должны быть целыми. Поэтому, или числа х₁ + 1 = 1  и  х₂ + 1 = 1, или  х₁ + 1= - 1  и  х₂ + 1 = - 1. В первом случае  х₁ =  х₂ = 0  и  р  = 0, во втором случае  х₁ = х₂ =  - 2  при  р  =  4.

11.3. Какие три цифры следует вычеркнуть в числе 123456789 так, чтобы получившееся  6 – значное число делилось на 72. Доказать, что полученное число  единственное.

Ответ. 2, 7 и 9.

Решение. Число должно делиться на множители числа 72, т.е. на 8 и 9. Необходимо применить признаки деления на 8 и на 9.

11.4. Треугольную пирамиду разрезали по боковым ребрам и сделали развертку. Она оказалась квадратом со стороной 1 дм. Найдите объем пирамиды.

Ответ: дм ³.

Решение.  Если снова склеить из развертки пирамиду, то в ее вершине сойдутся три вершины квадрата  (точки D, D₁ и D₂) а четвертая А станет одной из вершин основания. Каждое боковое ребро пирамиды будет склеиваться из двух разных отрезков границы квадрата. Это возможно в том случае, когда две вершины основания пирамиды, не совпадающие с вершинами квадрата, являются серединами его сторон, т.е. развертка имеет вид, изображенный на рисунке (вершины D, D₁ и D₂ склеиваются). Значит, длина одного из боковых ребер исходной пирамиды  равна 1 дм, а двух других – 0,5 дм. При этом все плоские углы при вершине пирамиды прямые.

совпадает с ее высотой. Подставляя полученные значения в формулу объема пирамиды, получим: V =  дм ³

11.5. В купе железнодорожного вагона имеется два противоположных дивана по 5 мест в каждом.  Из 10 пассажиров четверо желают сидеть лицом к паровозу, а трое - спиной к паровозу, остальным все равно, как сидеть. Сколькими способами могут разместиться пассажиры?

Решение. Определим, кто из трех пассажиров, которым неважно как сидеть, сядет лицом к паровозу. Это можно сделать тремя способами. На любом диване, имеющим 5 мест, можно пересаживать пассажиров 5! способами. По правилу умножения получим всего способов: 3 · 5! · 5! =  3 · 120 · 120 = 43200 способов. Ответ: 43200 способов..

10.4. Найдите наименьшее целое значение параметра р, при котором для всех значений х выполняется неравенство х⁴ + 2х²  + р  ≥ 4х.

Решение. Исходное неравенство преобразуем следующим образом:

х⁴ + 2х² - 4х + р  ≥ 0,   х⁴ + 2 (х² – 2х) + р  ≥ 0,   х⁴ + 2 (х² – 2х + 1) + (р – 2) ≥ 0,  

х⁴ + 2 (х – 1) ² + (р – 2) ≥ 0. Первые два слагаемых неотрицательны для всех значений х. Тогда и третье слагаемое должно быть неотрицательным, а это значит, что  р  - 2 ≥ 0, р ≥ 2.

 Наименьшее целое значение для параметра р – это 2. Ответ: р = 2.

10.5. В гостиницу приехал путешественник. Денег у него не было. Он имел серебряную цепочку, состоящую из 7 звеньев. За каждый день пребывания в гостинице он расплачивался одним звеном цепочки. Хозяин предупредил, что согласен взять не более одного распиленного звена, а остальные должны быть целыми. Как путешественнику распилить цепочку, чтобы прожить в гостинице неделю и ежедневно расплачиваться с хозяином? Решение. Если распилить третье звено, то цепочка распадается на три части: 1, 2 и 4 звена. С их помощью удается расплатиться, так как хозяин может давать сдачу звеньями, которые он получил раньше.

Используемая литература

1.      Коннова Е.Г. Математика. Поступаем в ВУЗ по результатам олимпиад. 5-8 класс. Часть 1/Под ред.Лысенко Ф.Ф. – Ростов – на –Дону: Легион;Легион – М,2010

2.      Коннова Е.Г. Математика. Поступаем в ВУЗ по результатам олимпиад. 6-9 класс. Часть 2/Под ред.Лысенко Ф.Ф. – Ростов – на –Дону: Легион;Легион – М,2010

3.      Олехник С.Н., Нестеренко Ю.В., Потапов М.К. Старинные занимательные задачи – М.:Дрофа,2006

4.      Фарков А.В. Внеклассная работа по математике. 5-11 классы – М.: Айрис-пресс,2007

5.      Фарков А.В. Математические кружки в школе. 5-8 классы– М.:Айрис-пресс,2006

6.      А.Я. Канель-Белов, А.К. Ковальджи Как решают нестандартные задачи. Москва, МЦНМО, 2009

7.      В.И. Арнольд Задачи для детей от 5 до 15 лет. Москва, МЦНМО, 2007

8.      Н.Я. Виленкин и др. Комбинаторика. Москва, МЦНМО, 2007

9.      Журналы «Квант» и «Математика в школе» разных лет

10.  Я.И.Перельман, Занимательная алгебра. Москва, «Наука», 1974

11.  А.В.Шевкин, Школьная олимпиада по математике. Москва, «Русское слово», 2002

12.  Всероссийская школа математики и физики «Авангард» тесты, 2007

13.  А.В. Фарков, Математические олимпиады в школе, 5-11 класс. Москва, Айрис-Пресс, 2004

14.  А.В. Фарков, Математические кружки в школе 5-8 классы. Москва, Айрис-пресс, 2006

15.  Л.Ф. Пичурин, За страницами учебника алгебры: Книга для учащихся 7-9 классов. Москва, Просвещение, 1990.

16.  Л.Ю. Березина, Графы и их применение. Москва, «Просвещение», 1979

17.  Я.И. Перельман, Живая математика. Москва, ГИТТЛ, 1958