Решу егэ олимпиадные задачи

1

---

2

---

3

---

4

---

5

---

6

---

7

---

8

---

9

---

10

1

---

2

---

3

---

4

---

5

---

6

---

7

---

8

---

9

---

10

---

11

---

12

---

13

---

14

---

15

---

16

---

17

---

18

---

19

---

20

---

21

---

22

---

23

---

24

---

25

---

26

---

27

---

28

---

29

---

30

---

31

---

32

---

33

---

34

---

35

---

36

---

37

---

38

---

39

---

40

---

41

---

42

---

43

---

44

---

45

---

46

---

47

---

48

---

49

---

50

---

51

---

52

---

53

---

54

---

55

1

---

2

---

3

---

4

1

Какова вероятность того, что случайно выбранный телефонный номер оканчивается двумя чётными цифрами?

---

2

Если шахматист А. играет белыми фигурами, то он выигрывает у шахматиста Б. с вероятностью 0,52. Если А. играет черными, то А. выигрывает у Б. с вероятностью 0,3. Шахматисты А. и Б. играют две партии, причём во второй партии меняют цвет фигур. Найдите вероятность того, что А. выиграет оба раза.

---

3

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

---

4

Вероятность того, что в случайный момент времени температура тела здорового человека окажется ниже чем 36,8 °С, равна 0,81. Найдите вероятность того, что в случайный момент времени у здорового человека температура окажется 36,8 °С или выше.

---

5

При изготовлении подшипников диаметром 67 мм вероятность того, что диаметр будет отличаться от заданного не больше, чем на 0,01 мм, равна 0,965. Найдите вероятность того, что случайный подшипник будет иметь диаметр меньше чем 66,99 мм или больше чем 67,01 мм.

---

6

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

---

7

В магазине три продавца. Каждый из них занят с клиентом с вероятностью 0,3. Найдите вероятность того, что в случайный момент времени все три продавца заняты одновременно (считайте, что клиенты заходят независимо друг от друга).

---

8

В торговом центре два одинаковых автомата продают кофе. Обслуживание автоматов происходит по вечерам после закрытия центра. Известно, что вероятность события «К вечеру в первом автомате закончится кофе» равна 0,25. Такая же вероятность события «К вечеру во втором автомате закончится кофе». Вероятность того, что кофе к вечеру закончится в обоих автоматах, равна 0,15. Найдите вероятность того, что к вечеру кофе останется в обоих автоматах.

---

9

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

---

10

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

---

11

Из районного центра в деревню ежедневно ходит автобус. Вероятность того, что в понедельник в автобусе окажется меньше 18 пассажиров, равна 0,82. Вероятность того, что окажется меньше 10 пассажиров, равна 0,51. Найдите вероятность того, что число пассажиров будет от 10 до 17.

---

12

Биатлонист пять раз стреляет по мишеням. Вероятность попадания в мишень при одном выстреле равна 0,8. Найдите вероятность того, что биатлонист первые три раза попал в мишени, а последние два промахнулся. Результат округлите до сотых.

---

13

Помещение освещается фонарём с двумя лампами. Вероятность перегорания лампы в течение года равна 0,3. Найдите вероятность того, что в течение года хотя бы одна лампа не перегорит.

---

14

---

15

На экзамене по геометрии школьник отвечает на один вопрос из списка экзаменационных вопросов. Вероятность того, что это вопрос по теме «Вписанная окружность», равна 0,2. Вероятность того, что это вопрос по теме «Параллелограмм», равна 0,15. Вопросов, которые одновременно относятся к этим двум темам, нет. Найдите вероятность того, что на экзамене школьнику достанется вопрос по одной из этих двух тем.

---

16

Чтобы пройти в следующий круг соревнований, футбольной команде нужно набрать хотя бы 4 очка в двух играх. Если команда выигрывает, она получает 3 очка, в случае ничьей  — 1 очко, если проигрывает  — 0 очков. Найдите вероятность того, что команде удастся выйти в следующий круг соревнований. Считайте, что в каждой игре вероятности выигрыша и проигрыша одинаковы и равны 0,4.

---

17

В Волшебной стране бывает два типа погоды: хорошая и отличная, причём погода, установившись утром, держится неизменной весь день. Известно, что с вероятностью 0,8 погода завтра будет такой же, как и сегодня. Сегодня 3 июля, погода в Волшебной стране хорошая. Найдите вероятность того, что 6 июля в Волшебной стране будет отличная погода.

---

18

В магазине стоят два платёжных автомата. Каждый из них может быть неисправен с вероятностью 0,05 независимо от другого автомата. Найдите вероятность того, что хотя бы один автомат исправен.

---

19

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

---

20

Две фабрики выпускают одинаковые стекла для автомобильных фар. Первая фабрика выпускает 45% этих стекол, вторая  — 55%. Первая фабрика выпускает 3% бракованных стекол, а вторая  — 1%. Найдите вероятность того, что случайно купленное в магазине стекло окажется бракованным.

---

21

Всем пациентам с подозрением на гепатит делают анализ крови. Если анализ выявляет гепатит, то результат анализа называется положительным. У больных гепатитом пациентов анализ даёт положительный результат с вероятностью 0,9. Если пациент не болен гепатитом, то анализ может дать ложный положительный результат с вероятностью 0,01. Известно, что 5% пациентов, поступающих с подозрением на гепатит, действительно больны гепатитом. Найдите вероятность того, что результат анализа у пациента, поступившего в клинику с подозрением на гепатит, будет положительным.

---

22

Автоматическая линия изготавливает батарейки. Вероятность того, что готовая батарейка неисправна, равна 0,02. Перед упаковкой каждая батарейка проходит систему контроля. Вероятность того, что система забракует неисправную батарейку, равна 0,99. Вероятность того, что система по ошибке забракует исправную батарейку, равна 0,01. Найдите вероятность того, что случайно выбранная изготовленная батарейка будет забракована системой контроля.

---

23

Агрофирма закупает куриные яйца в двух домашних хозяйствах. 40% яиц из первого хозяйства  — яйца высшей категории, а из второго хозяйства  — 20% яиц высшей категории. Всего высшую категорию получает 35% яиц. Найдите вероятность того, что яйцо, купленное у этой агрофирмы, окажется из первого хозяйства.

---

24

В торговом центре два одинаковых автомата продают кофе. Вероятность того, что к концу дня в автомате закончится кофе, равна 0,3. Вероятность того, что кофе закончится в обоих автоматах, равна 0,12. Найдите вероятность того, что к концу дня кофе останется в обоих автоматах.

---

25

---

26

Из районного центра в деревню ежедневно ходит автобус. Вероятность того, что в понедельник в автобусе окажется меньше 20 пассажиров, равна 0,94. Вероятность того, что окажется меньше 15 пассажиров, равна 0,56. Найдите вероятность того, что число пассажиров будет от 15 до 19.

---

27

Вероятность того, что на тестировании по биологии учащийся О. верно решит больше 11 задач, равна 0,67. Вероятность того, что О. верно решит больше 10 задач, равна 0,74. Найдите вероятность того, что О. верно решит ровно 11 задач.

---

28

На фабрике керамической посуды 10% произведённых тарелок имеют дефект. При контроле качества продукции выявляется 80% дефектных тарелок. Остальные тарелки поступают в продажу. Найдите вероятность того, что случайно выбранная при покупке тарелка не имеет дефектов. Результат округлите до сотых.

---

29

---

30

Перед началом волейбольного матча капитаны команд тянут честный жребий, чтобы определить, какая из команд начнёт игру с мячом. Команда «Статор» по очереди играет с командами «Ротор», «Мотор» и «Стартер». Найдите вероятность того, что «Статор» будет начинать только первую и последнюю игры.

---

31

В кармане у Пети было 2 монеты по 5 рублей и 4 монеты по 10 рублей. Петя, не глядя, переложил какие-то 3 монеты в другой карман. Найдите вероятность того, что пятирублевые монеты лежат теперь в разных карманах.

---

32

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

---

33

---

34

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

---

35

При двукратном бросании игральной кости в сумме выпало 9 очков. Какова вероятность того, что хотя бы раз выпало 5 очков?

---

36

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

---

37

Игральную кость бросили один или несколько раз. Оказалось, что сумма всех выпавших очков равна 4. Какова вероятность того, что был сделан один бросок? Ответ округлите до сотых.

---

38

Игральную кость бросили один или несколько раз. Оказалось, что сумма всех выпавших очков равна 3. Какова вероятность того, что было сделано два броска? Ответ округлите до сотых.

---

39

Первый игральный кубик обычный, а на гранях второго кубика нет чётных чисел, а нечётные числа 1, 3 и 5 встречаются по два раза. В остальном кубики одинаковые. Один случайно выбранный кубик бросают два раза. Известно, что в каком-то порядке выпали 3 и 5 очков. Какова вероятность того, что бросали второй кубик?

---

40

---

41

---

42

---

43

---

44

---

45

---

46

Маша коллекционирует принцесс из Киндер-сюрпризов. Всего в коллекции 10 разных принцесс, и они равномерно распределены, то есть в каждом очередном Киндер-сюрпризе может с равными вероятностями оказаться любая из 10 принцесс. У Маши уже есть две разные принцессы из коллекции. Какова вероятность того, что для получения следующей принцессы Маше придётся купить ещё 2 или 3 шоколадных яйца?

---

47

В городе 48 % взрослого населения  — мужчины. Пенсионеры составляют 12,6 % взрослого населения, причём доля пенсионеров среди женщин равна 15 %. Для социологического опроса выбран случайным образом мужчина, проживающий в этом городе. Найдите вероятность события «выбранный мужчина является пенсионером».

---

48

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

---

49

На рисунке показано дерево некоторого случайного эксперимента. Событию A благоприятствуют элементарные события a, b и c, а событию B благоприятствуют элементарные события b, c и d. Найдите — условную вероятность события A при условии B.

---

50

---

51

Симметричную игральную кость бросили 3 раза. Известно, что в сумме выпало 6 очков. Какова вероятность события «хотя бы раз выпало 3 очка»?

---

52

В коробке 8 синих, 6 красных и 11 зелёных фломастеров. Случайным образом выбирают два фломастера. Какова вероятность того, что окажутся выбраны один синий и один красный фломастер?

---

53

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

---

54

---

55

Министерство образования и науки Российской
Федерации

федеральное государственное бюджетное образовательное
учреждение высшего образования

 «Рязанский государственный университет имени С.А.
Есенина»

Физико-математический факультет

Кафедра математики

и методики преподавания математических дисциплин

Отчет по практике

Методические рекомендации

Олимпиадные
задачи в ЕГЭ

Выполнил:

студентка 3 курса, группа 3301

направления подготовки

01.03.01 «Математика»

Блинкова Елена Андреевна

Научный руководитель:

ст.препод.

Землякова Ирина Владимировна

Рязань, 2016

Аннотация.

В данной
методической рекомендации рассмотрены олимпиадные задачи, которые встречаются в
едином государственном экзамене.

Вам предлагается
краткий теоретический экскурс в такие темы как:

·        
Делимость

·        
Метод
математической индукции

·        
Принцип
Дирихле

·        
Инварианты
и полуинварианты

·        
Раскраски

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

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

Оглавление

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

Делимость.

Простые и составные
числа.

Наибольший общий
делитель и наименьшее общее кратное.

Деление с остатком

Признаки делимости

Признак Паскаля.

Метод математической
индукции.

Принцип наименьшего
числа.

Принцип Дирихле.

Инварианты и
полуинварианты.

Раскраски.

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

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

Данная методическая рекомендация предназначена
для реализации в 9-11 классах для расширения теоретических и практических
знаний учащихся.

 Олимпиадные задачи – очень сложный, но
довольно интересный материал, который также включён в единый государственный
экзамен (задачи под №19). Задачи №19 – это задачи на логику, нестандартные
вычислительные задачи с применением знаний из курса арифметики, теории чисел и
алгебры.  Выпускники при сдаче экзамена не берутся решать задачи такого типа,
т.к. во время обучения, этот вопрос не рассматривается должным образом из-за
своей сложности и нехватки времени.

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

В представленной методической рекомендации
также содержатся банк задач, в котором выписаны все задачи по данной теме с
сайта ФИПИ (часть задач про решена).

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

Делимость.

Ученики хорошо знают, что такое делимость
чисел. Но, к сожалению, не всегда знают, как решать задачи по данной теме.
Такие задачи нередко предлагаются на математических олимпиадах, и на итоговых
экзаменах. Прежде чем привести примеры, напомним основные сведения из теории
делимости.

(В теории будем рассматривать только целые
числа, т.к. в них входят и натуральные)

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

Определение 1.1. Число a делится на число b (или b делит
a, при b – не равном нулю) если существует такое число с, что
a = bc. При этом число c называется частным от деления a на b.

Обозначения:  —  а делится на b или
b½a – b делит a

     Рассмотрим простейшие свойства делимости.

Для любых целых чисел a, b, c
справедливы:

Теорема 1.2. Если  и с – частное от
деления, то с – единственное.

Теорема 1.3.

Теорема 1.4. Если  и , то .

Теорема 1.5. Если  и , то или a=b, или a= -b.

Теорема 1.6. Если  и , то а=0.

Теорема 1.7. Если  и а¹0, то .

Теорема 1.8. Для того чтобы  необходимо
и достаточно  чтобы.

Теорема 1.10. Если , то .

Теорема 1.11. Если сумма чисел и к-1 слагаемое этой суммы
делится на некоторое число с, то и к-ое слагаемое делится на с.

Свойства делимости находят применение при
решении задач.

 

Простые и
составные числа.

Будем рассматривать целые положительные числа.

Определение 2.1. Целое
положительное число р>
1 называется простым, если оно имеет ровно два положительных делителя: 1 и р.

Определение 2.2. Целое
положительное число m > 1 называется
составным, если оно имеет по крайней мере один положительный делитель отличный
от 1 и m.

Примеры:

1)               
3
имеет ровно 2 делителя: 1 и 3, по Определение 2.1. оно простое.

2)               
4
имеет своими делителями 1, 4 и 2, по Определение 2.2. число 4 – составное.

3)               
Перечислим
свойства простых чисел.

Теорема 2.1. Если р и р₁
– простые числа и рр₁, то р не
делится    на р₁

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

Теорема 2.7. (основная
теорема арифметики)

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

     Таким образом, если  m – целое
положительное число, а р₁, р₂, …р_к—
простые, то

                              m =.

Если среди чисел р₁, р₂, …, р_к
есть одинаковые, то

                              m =— каноническое представление целого
числа.

Наибольший общий делитель и наименьшее общее
кратное.

Определение 3.1. Общим делителем целых чисел a₁, a₂,…, a_n называется любое целое число d,
такое что d½а₁, d½а₂,…, d½а_n.

Определение 3.2.   Наибольшим
общим делителем (НОД) целых чисел   a₁, a₂,…, a_n
называется такой их положительный общий делитель, который делится на любой
другой общий делитель этих чисел.

Обозначение: если d есть НОД
чисел  a₁, a₂,…, a_n , то это
записывается следующим образом:  (a₁, a₂,…, a_n ) = d

Таким образом, из определения 3.2., если  (a₁, a₂,…, a_n ) = d, то

                  1) d> 0,

                  2) d½а₁, d½а₂,…, d½а_n,

                  3) если существует целое  число
k, такое
что k½a₁, k½a₂,…, k½a_n, то k½d.

     Рассмотрим основные свойства НОД целых чисел.

Теорема 3.1.  1) Для любых
целых чисел    a₁, a₂,…, a_n , из
которых хотя бы одно отлично от нуля, существует НОД.

2) Если   , где
р₁, …, р_s – различные простые числа, то (a₁, a₂,…, a_n ) = .

Теорема 3.2.   Если   (a₁, a₂,…, a_n ) = d, b½d  и b>0, то  .

Теорема 3.3.   (a₁,…,
a_n-1, a_n) = ((a₁,…, a_n-1),
a_n).

Определение 3.3.  Пусть 
a₁, a₂,…, a_n –
отличные от нуля целые числа. Наименьшим общим кратным (НОК) называют
наименьшее положительное число, делящееся на все эти числа.

Обозначение 

Таким образом, если  , то

1)                                           
,    

2)                                           
 ,

3)                                           
если
 и , то .

Теорема 3.4.   Если   — каноническое
разложение чисел a₁, a₂,…, a_n на
простые множители, то

                               =

Теорема 3.5.   Пусть — целые, ,
тогда .

Определение 3.4.  Числа
а и b
называются взаимно простыми, если НОД этих чисел равен 1.

Теорема 3.6.   Если a и  p – целые
числа, причем  p-простое,
то либо  , либо числа  a и  p взаимно
просты.

Теорема 3.7.  НОК двух
взаимно простых чисел равно их произведению.

Теорема 3.8. Для того чтобы
a делилось
на взаимно простые числа  b и  c,
необходимо и достаточно, чтобы оно делилось на их произведение.

Теорема 3.9.  Если , причем , то .

Деление с остатком

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

Определение. Разделить
целое число a на целое число b с остатком  – это значит представить его в виде
a=bq + r, где q и r целые числа, 0£r<ïbï.

Основную роль во всей арифметике целых чисел играет
теорема о делении с остатком.

Теорема. Для любых целых a и b существует единственная пара
чисел q и r, удовлетворяющих условиям, a=bq + r,  0£r<ïbï.

Замечание. В частности,
если  , то   и   делится на .

 Замечание. Если   то q
называется неполным частным, а  r – остатком от
деления a на  b.

Из теоремы о делении с остатком следует, что при
фиксированном целом  m>0 любое
целое число а можно представить в одном из следующих видов:

При этом если  то будем
иметь    ,    если  и

                                                                
, если .

Признаки делимости

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

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

Признак делимости на 2. Число n
делится на  2 в том и только в том случае, если его последняя цифра делится на
2.

Признак делимости на 4. Число n делится на 4 в том и только в том случае,
если на 4 делится число, образованное из двух последних цифр числа n.

Признак делимости на 8. Число n делится на 8 в том и только в том случае,
если на 8 делится трёхзначное число, образованное из трёх последних цифр числа n.

Если внимательно рассмотреть признаки
делимости на 2,4,8, то можно найти признак делимости на 2^m (m=1,2,3,…): число n
делится на 2^m в том и только в том случае, если на 2^m делится m-значное число, которое образуют m
последних  цифр числа n.

Признак делимости на 5.  Число n делится на 5 в том и только в том случае,
если его последняя цифра 0 или 5.

Признак делимости на 5^m  схож с признаком делимости числа n
на 2^m.

Признак делимости на 3. Число n делится на  3 в
том и только в том случае, если сумма его цифр делится на 3.

Признак делимости на 9. Число n
делится на  9 в том и только в том случае, если сумма его цифр делится на 9.

Признак делимости на 7. Число n делится на 7 в том и только в том случае,
если на 7 делится число p=n+3n+2n-(n+3n+n)+…,где n–последняя цифра числа n,
n–предпоследняя цифра числа и так далее.

Признак делимости на 11. Число n делится на  11 в
том и только в том случае, если сумма его цифр, стоящих на нечётных местах,
отличается от суммы его цифр, стоящих на чётных местах, на величину кратную 11.

(n+ n+ n+…)-( n+n+ n+…) делится на 11, то число n
делится на 11.

Признак делимости на 13. Число n делится на  13 в том и только в том случае,
если на 13 делится число l, полученное из n
зачёркиванием последней цифры и прибавлением к получённому числу учетверённое
значения зачеркнутой цифры.

Комбинируя уже известные признаки делимости,
можно узнать, делится ли данное число на 6, 10, 12, 14, 15 и так далее.

Признак Паскаля.

Французский математик, физик и философ 18 века
Блез Паскаль однажды задался вопросом: что будет, если в десятичном разложении
натурального числа

n=10n+…+10n +n все степени десятки взять и заменить на остатки m,…,m, получающиеся при
делении этих степеней на некоторое фиксированное число m.
Оказывается, в результате такой замены образуется число p=
m n+…+ m n+ n которое даёт тот же остаток при делении на m,
что и число n. В этом и состоит суть признака, описанного Паскалем
в работе ”Особенности делимости чисел”. Таким образом, n
делится на m, если p делится на m.

С помощью этого признака можно вывести
конкретные признаки, перечисленные выше.

Примеры 1. Пусть a делится на b
и с делится на d. Выясним, делится ли произведение ac
на bd.

Решение: Из определения делимости следует, что a= bk,
с= dm, где  k и

m
– целые числа.

 Отсюда aс=(bk)(
dm)=(bd)( km).

Так как k и m – целые числа, то km является
целым числом. Значит, существует такое целое число, при умножении которого на bd в произведении получается aс, то есть
по определению, aс делится на bd

Примеры 2. Какие
остатки могут получиться при делении квадрата целого числа на 3?

Решение: Всякое число a в соответствии с остатками от деления его на
3 может быть представлено в одном из видов: a=3k,
a=3k+1, a=3k+2 (k–целое
число).

Соответственно получаем

  

    

Мы видим, что число aлибо
делится на 3, либо при делении на 3 даёт остаток 1. Тем самым мы показали, что
квадрат целого числа при делении на 3 не может дать остаток 2.

Примеры 3. Коля, Серёжа и Ваня регулярно ходили в кинотеатр.
Коля бывал в нём каждый 3-й день, Серёжа  — каждый 7-й,
Ваня  — каждый 5-й. Сегодня все ребята были в кино. Когда все
трое встретятся в кинотеатре в следующий раз? 

Решение:
Начнём отсчитывать дни
от первого посещения кинотеатра всеми мальчиками. Номер дня, когда
в кинотеатр приходит Коля, делится на 3, когда приходит
Серёжа  — делится на 7 и т.д. Значит, чтобы все трое
пришли в кинотеатр, номер дня должен одновременно делиться на 3,
на 5 и на 7. Таким образом, номер этого дня должен делиться
на 105, т.е. 105, 210, 315 и т.д. Поскольку нас интересует самый
первый день, то это день под номером 105 (это значит, что до встречи
ребятам придётся ходить в кинотеатр больше 3х месяцев). 

Примеры 4.Найдите
все такие пары натуральных чисел x, y, что числа x³+y и y³+x
делятся на x²+y².

Решение. Докажем вначале, что x и y взаимно просты. Предположим противное.
Тогда x и y делятся на некоторое простое число p; пусть p входит в разложения
на простые множители чисел x и y соответственно в степенях a>1 и b>1,
положим для определенности a>b. Тогда максимальная степень p, на
которую делится x³+y, равна b (поскольку x³ делится на p^3a} и тем более
на p^b+1, а y делится на p^b и не делится на p^b+1). Но x²+y² делится на p^2b,
следовательно, x³+y не может делиться на x²+y².
Это противоречие доказывает, что x и y взаимно просты.

Далее, из условия следует, что число x(x²+y²)-(x³+y)=y(xy-1)
делится на x²+y². Заметим, что y и x²+y²не
имеют общего множителя, большего 1 (т. к. x и y взаимно просты), значит, xy-1
делится на x²+y². Но если xy>1, то это невозможно, т.
к. x²+y² > 2xy > xy-1.

Примеры 5. Петин счет в банке содержит 500 долларов.
Банк разрешает совершать операции только двух видов: снимать 300 долларов или
добавлять 198 долларов. 
Какую максимальную сумму Петя может снять со счета, если других денег у него
нет?

Решение. Поскольку 300 и 198 делятся
на 6, Петя сможет снять лишь сумму, кратную 6 долларам. Максимальное число,
кратное 6 и не превосходящее 500, — это 498.

Докажем, что снять 498 долларов возможно.
Произведем следующие операции:

500-300=200

200+198=398

398-300=98

98+198=296

296+198=494.

Сумма, лежащая в банке, уменьшилась на 6
долларов.

Проделав аналогичную процедуру 16 раз, Петя
снимет 96 долларов. Затем он может снять 300, положить 198 и снова снять 300. В
результате у него будет 498 долларов.

Метод математической индукции.

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

В широком
смысле индукция – это способ рассуждений, позволяющий переходить от
частных утверждений к общим. Обратный переход от общих утверждений к частным
называется дедукцией. Дедукция всегда приводит к правильным выводам. В
то же время индукция может привести к неверным выводам. Например, замечая, что
число 60 делится на числа 1,2,3,4,5,6, мы не в праве сделать вывод о том, что
60 делится вообще на любое число.

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

Применение
метода включает 3 этапа:

1)               
База индукции: проверяем справедливость утверждения P(n) для n=1 (или для другого,
частного значения n, начиная с
которого предполагается справедливость P(n)).

2)               
Предположение индукции: предполагаем, что P(n)
справедливо при n=k.

3)               
Шаг индукции: используя предположение, доказываем, что P(n) справедливо для n=k+1.

В результате
можно сделать вывод о справедливости P(n) для любого .
Действительно, для n=1, утверждение верно (база индукции). А, следовательно,
верно и для n=2, так как
переход от n=1к n=2 обоснован (шаг
индукции). Применяя шаг индукции снова и снова, получаем справедливость P(n) для n=3,4,5,…, т.е.
справедливость P(n) для всех n.

Если предложение P(n), зависящее от
натурального числа n, истинно для n=1 и из того, что оно истинно для n=k (где
k-любое натуральное число), следует, что оно истинно и для следующего числа
n=k+1, то предположение P(n) истинно для любого натурального числа n.

Замечание 1. В некоторых случаях метод
математической индукции используется в следующей форме:

Пусть m —
натуральное число, m > 1 и P(n) —
предложение, зависящее от n, n ≥ m.

Если

1.                
P(m) справедливо;

2.                
P(n) будучи истинным
предложением, влечет истинность предложения P(n + 1)
для любого натурального n, n ≥ m,
тогда P(n) — истинное предложение для любого
натурального n, n ≥ m.

В дальнейшем
рассмотрим примеры применения метода математической индукции.

Пример 1. Игрушка («Ханойские башни») имеет три
стержня. На одном

находится пирамидка из нескольких
колец (уменьшающихся снизу вверх).

Эту пирамидку нужно переложить на
другой стержень, соблюдая правила

игры: нельзя переносить сразу
несколько колец и нельзя класть большее

кольцо поверх меньшего.

Например, пирамидку из двух колец
можно переложить так: положить

меньшее кольцо на второй стержень,
затем большее на третий, а затем мень-

шее поверх большего (1 → 2, 1 → 3,
2 → 3, если стержни нумеровать слева

направо).

Наша задача — доказать, что
возможно переместить на другой стержень

пирамидку из любого числа колец,
соблюдая правила игры.

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

пирамидка из двух
колец, которую мы уже умеем перекладывать.

   Рисунок 1.

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

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

Записать их можно так: 1 → 2, 1 →
3, 2 → 3, 1 → 2, 3 → 1, 3 → 2, 1 → 2

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

верхнее кольцо).

Теперь, используя перекладывание
пирамидки из трёх колец как подпрограмму, мы можем переложить четыре кольца
(достаточно заменить на рис. 1 пирамидку из двух колец на пирамидку из трёх).

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

Рисунок 2.

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

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

Решение. Будем считать, что рукопожатия происходят по
очереди. Изначально все участники сделали 0 рукопожатий, а нуль — чётное число.

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

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

а. Два чётных участника жмут друг
другу руки. После этого каждый из них становится нечётным (чётное число плюс
единица | нечётное число). Общее число нечётных участников увеличивается на 2.

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

в. Чётный участник жмёт руку
нечётному. При этом они меняются местами: нечётный становится чётным и
наоборот. Поэтому общее число нечётных

участников не меняется.

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

В задаче о рукопожатиях мы
доказывали, что число нечётных участников после n рукопожатий будет чётным
(поскольку при переходе от n к n + 1 число рукопожатий либо не меняется, либо
меняется на 2).

Пример 3. Показать, что любую сумму, начиная с 8 копеек, можно уплатить монетами
в 3 и 5 копеек.

Решение. Покажем, как уплатить 8, 9 и 10 копеек:

8 = 5 + 3;

9 = 3 + 3 + 3;

10 = 5 + 5:

Добавив ещё одну трёхкопеечную
монету, получаем

11 = 8 + 3 = (5 + 3) + 3;

12 = 9 + 3 = (3 + 3 + 3) + 3;

13 = 10 + 3 = (5 + 5) + 3:

Ещё одна трёхкопеечная монета
позволит уплатить

14 = 11 + 3;

15 = 12 + 3;

16 = 13 + 3

копеек, и так далее.
Задача решена.

В задаче о монетах мы доказывали,
что n копеек (при n > можно уплатить монетами в 3 и 5 копеек. Сначала мы
проверили это при n = 8; 9; 10, затем заметили, что прибавлением одной
трёхкопеечной монеты можно получить n = 11; 12; 13, затем n = 14; 15; 16 и так
далее.

Мы нумеровали утверждения, начиная
с единицы, но это не обязательно.

В задаче о монетах
последовательность утверждений начинается с P8 (про 8 копеек). Мы сначала
доказываем утверждения P8;P9;P10, а затем все следующие по очереди. При этом
доказательство утверждения Pn опирается на Pn−3 (зная, как уплатить n −3
копейки монетами в 3 и 5 копеек, мы можем уплатить n копеек: достаточно
добавить одну трёхкопеечную монету).

Пример 4. На доске написаны сто цифр — нули и единицы (в любой комбинации).
Разрешается выполнять два действия:

(а) заменять первую цифру (нуль на
единицу и наоборот);

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

(Пример: в последовательности
0011001… можно заменить первую цифру или четвёртую — они подчёркнуты.)
Показать, что с помощью нескольких таких замен можно получить любую комбинацию
из ста нулей и единиц.

Решение. Докажем по индукции такое утверждение Pn : на
первых n местах можно получить любую комбинацию нулей и единиц.

Базис индукции. При n = 1 это нам
дано по условию: первую цифру можно менять, как угодно.

Шаг индукции. Предположим, что мы
уже доказали, что на первых n −1 местах можно получить любую комбинацию цифр.
Тогда, в частности, там можно получить и комбинацию 000… 0001 (единица на
(n−1)-ом месте и нули до неё). Эта комбинация позволяет заменить цифру, стоящую
на n-м месте, поскольку именно она оказывается цифрой, стоящей после первой
единицы. После этого мы можем снова воспользоваться предположением индукции
An−1 и получить на первых n−1 местах любые нужные нам цифры.

Задача решена? На самом деле нет.
Наше решение содержит не сразу заметный, но важный пробел: почему изменение n −
1 цифр на последнем шаге не испортит n-й цифры? Чтобы исправить положение, нам
придётся изменить решение и доказывать по индукции более сильное утверждение:
на первых n местах можно получить любые цифры, не трогая следующих цифр. Теперь
уже всё проходит гладко: проводя шаг индукции, мы получили нужные нам цифры на
первых n местах и не касались следующих цифр.

Теперь задача действительно
решена. Для самопроверки полезно записать

последовательность действий при
переходе, скажем, от 001 к 000. (Ответ:

001 ! 101 ! 111 ! 011
! 010 ! 110 ! 100 ! 000.)

Принцип наименьшего числа.

Часто рассуждения по индукции заменяют
ссылкой на «принцип наименьшего числа»: всякое непустое множество натуральных
чисел имеет наименьший элемент.

Например, мы доказывали, что любую
сумму, начиная с 8 копеек, можно уплатить монетами в 3 и 5 копеек. Теперь это
рассуждение будет выглядеть так.

Предположим, есть такие суммы
(целое число копеек, не меньшее 8), которые нельзя уплатить монетами в 3 и 5
копеек. Возьмём самую маленькую из них. Пусть это будет n. По предположению n
> 8, поскольку меньшие значения n мы не рассматриваем. Мы знаем, кроме того,
что n не может быть равно 8, 9 или 10, поскольку эти суммы уплатить можно.
Значит, n > 11.

Тогда n − 3 > 8 и, кроме того,
n − 3 < n. Значит (раз n было наименьшим плохим значением), сумму в n −3
копеек можно уплатить монетами в 3 и 5 копеек. Если добавить трёхкопеечную
монету, то получится n копеек. А мы предполагали, что n копеек уплатить нельзя.
Противоречие.

Некоторые задачи проще сразу
решать, исходя их принципа наименьшего числа.

Принцип Дирихле.

При решении многих задач используется
логический метод рассуждения «от противного». В данной пособии
рассмотрена одна из его форм — принцип Дирихле. Этот принцип утверждает, что
если множество из N элементов разбито на n непересекающихся частей, не имеющих
общих элементов, где N>n то, по крайней мере, в одной части будет более
одного элемента. Принцип назван в честь немецкого математика Дирихле
(1805-1859), который успешно применял его к доказательству арифметических
утверждений.

По традиции принцип Дирихле объясняют на
примере «зайцев и клеток».

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

Самая популярная формулировка принципа
Дирихле звучит так:

ФОРМУЛИРОВКА 1. «Если в n клетках сидит n+1
или больше зайцев, то найдётся клетка, в которой сидят по крайней мере два
зайца».

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

Принцип Дирихле можно сформулировать на
языке множеств и отображений.

ФОРМУЛИРОВКА 2. «При любом отображении
множества P, содержащего n+1 элементов, в множество Q, содержащее n элементов,
найдутся два элемента множества P, имеющие один и тот же образ».

Несмотря на совершенную очевидность этого
принципа, его применение является весьма эффективным методом решения задач,
дающим во многих случаях наиболее простое и изящное решение. Однако во всех
этих задачах часто нелегко догадаться, что считать «зайцем», что —
«клеткой», и как использовать наличие двух «зайцев»,
попавших в одну «клетку». С помощью принципа Дирихле обычно
доказывается существование некоторого объекта, не указывая, вообще говоря,
алгоритм его нахождения или построения. Это даёт так называемое
неконструктивное доказательство — мы не можем сказать, в какой именно клетке
сидят два зайца, а знаем только, что такая клетка есть.

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

Решение. Существует n-1
способов вращения стола, после каждого из них взаимное расположение флагов и
послов изменится. Каждому послу сопоставим вращение, после которого он окажется
рядом со своим флагом. Согласно принципу Дирихле при каком-то вращении два
(может, и больше) посла окажутся рядом со своим флагом. В решении задачи роль
«зайцев» играют, естественно, послы, а роль «клеток» —
положения стола при различных вращениях. Посол попадает в «клетку»,
если при соответствующем этой «клетке» вращении стола он оказывается
рядом с флагом своей страны. Таким образом, «клеток» у нас n-1, а
«зайцев» — n. Замечание Условие о том, что вначале ни один из послов
не находится рядом со своим флагом, существенно. На самом деле первоначальное
положение также является «клеткой», но эта «клетка» по условию
заведомо окажется пустой. Так что можно считать, что всего «клеток»
имеется n-1.

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

Решение. Введём на
клетчатой бумаге систему координат с началом координат в одном из узлов, осями,
направленными вдоль линий сетки, и единичным отрезком, равным стороне клетки.
Тогда все отмеченные точки будут иметь целочисленные координаты. Покажем, что найдутся
две точки из пяти, у которых одна и та же чётность координат x и координат y.
«Зайцами» у нас будут точки, а «клетками» — пары (Ч, Ч),
(Ч, Н), (Н, Ч), (Н, Н). Если, например, у точки (x, y) координата x чётна, а
координата y нечётна, то мы её поместим в «клетку» (Ч, Н). Итак, 5
«зайцев» и 4 «клетки». Пусть (x1, y1) и (x2, y2) — две
точки, попавшие в одну «клетку». Середина отрезка, соединяющего эти
две точки, имеет координаты ([(x1+x2)/ 2], [(y1+y2)/ 2]), которые являются
целыми числами в силу одинаковой чётности x1 и x2, y1 и y2. Таким образом,
середина этого отрезка лежит в узле сетки, т.е. данный отрезок является
искомым.

В ряде задач применяют
следующее обобщение принципа Дирихле.

ФОРМУЛИРОВКА 3. «Если nk+1
зайцев размещены в n клетках, то найдутся k+1
зайцев, которые посажены в одну клетку (n, k —
натуральные числа)».

Обобщенный принцип Дирихле также
достаточно очевиден: если бы в каждой клетке сидело не более k зайцев,
то во всех клетках было бы не более nk зайцев, что
противоречит условию.

Обобщение принципа используют,
когда требуется выявить несколько (три и более) объектов, обладающих некоторым
свойством. Разберём несколько примеров.

Пример 3. В классе 25
человек. Известно, что среди любых трёх из них есть двое друзей. Докажите, что
есть ученик, у которого не менее 12 друзей.

Решение. Выберем любых
двух учеников класса, которые не дружат между собой. (Если таких нет, то все
ученики класса дружат между собой, значит, у каждого имеется 24 друга, и задача
решена.) Из оставшихся 23 учеников каждый дружит с одним из этих двух, иначе мы
имели бы тройку учеников, среди которых не было бы друзей. Тогда у одного из
выбранных двух учеников не менее 12 друзей. (23 «зайца» рассажены в
двух «клетках».)

Пример 4. В прямоугольнике
5×6 закрашено 19 клеток. Докажите, что в нём можно выбрать квадрат 2×2, в
котором закрашено не менее трёх клеток.

Решение.

Разделим
прямоугольник на 6 частей по 5 клеток (Cм. рисунок). Согласно принципу Дирихле
в одной из этих частей будет закрашено не менее 4 клеток. Тогда в квадрате 2×2,
содержащемся в этой части, закрашено либо 3, либо 4 клетки. Это и будет искомый
квадрат.

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

Решение. Существует
n-1 способов вращения стола, после каждого из них взаимное расположение флагов
и послов изменится. Каждому послу сопоставим вращение, после которого он
окажется рядом со своим флагом. Согласно принципу Дирихле при каком-то вращении
два (может, и больше) посла окажутся рядом со своим флагом. В решении задачи
роль «зайцев» играют, естественно, послы, а роль «клеток» —
положения стола при различных вращениях. Посол попадает в «клетку»,
если при соответствующем этой «клетке» вращении стола он оказывается рядом
с флагом своей страны. Таким образом, «клеток» у нас n-1, а
«зайцев» — n. Замечание Условие о том, что вначале ни один из послов
не находится рядом со своим флагом, существенно. На самом деле первоначальное
положение также является «клеткой», но эта «клетка» по
условию заведомо окажется пустой. Так что можно считать, что всего
«клеток» имеется n-1.

Инварианты и полуинварианты.

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

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

Рассмотрим данный раздел на примере.

Имеется шахматная доска, из которой вырезали два
противоположных угловых поля. Можно ли покрыть её целиком фигурками домино
(размером 2×1 поля шахматной доски) таким образом, чтобы каждое поле было полностью
покрыто одной и только одной фигурой домино?

В данном контексте фразу «можно ли» следует считать,
как «докажите, что это невозможно». Так как в «можно ли»-задачах имеет смысл
попытаться доказать невозможность существования решения – это может помочь
найти его, если решение всё-таки существует.

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

Наиболее часто к задаче о «домино» приводится такое
решение.

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

Безусловно, предыдущий абзац является исчерпывающим
решением задачи. И в нём ни разу не встречается слово «инвариант». Тем не
менее, инвариант в этом решении присутствует. Переформулируем решение, чтобы
его разглядеть.

Что значит «замощение фигурами домино»? Этот процесс
выкладывания домино по одной «до победного», либо не до победного конца. Следуя
определению инварианта, назовём выкладывание одной фигуры домино (одну итерацию
процесса выкладывания) преобразованием.

Назовём состоянием S некоторый промежуточный результат в замощении
доски фигурами домино. Иными словами, состояние – это доска, на которую
некоторым образом положены первые N фигур домино после первых N
итераций. Число N может быть нулём – пустая доска также является
состоянием, которое называется начальным состоянием.

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

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

Инвариантом может быть, например, функция I(S)=B—W, где B –
число свободных от фигур домино тёмных полей доски, W –
светлых. Ясно что при добавлении новой фигуры домино, как B, так и
W уменьшаются на единицу (фигура домино всегда покрывает одно тёмное и
одно светлое поле), следовательно, B—W остаётся константой. В начальном состоянии  равно двум (или минус двум), в конечном
должно быть равно нулю – противоречие, невозможность требуемого замощения
доказана.

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

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

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

Решение. Решение задачи основано на одном свойстве наших
операций. Это свойство является инвариантным на множестве
позиций с чётным числом синих точек (понятно, что чётность числа синих точек не
меняется).
Определим для таких расстановок знакопеременную сумму

|m₁ – m₂ + m₃ – m₄ +
…+ m_{2k – 1} – m_2k|

длин серий красных точек: m₁ —
число красных точек, заключённых между первой и второй синими точками
(направление обхода и первая точка выбираются произвольно), m₂ —
число красных точек между второй и третьей синими точками, m₃ —
между третьей и четвёртой, …, m_2k — между
последней (2k-й) и первой синими точками; некоторые m_i могут
равняться нулю. Если синих точек в расстановке нет вовсе, то положим эту сумму
равной числу её красных точек. Делимость на 3 определённой таким образом суммы
— инвариант. (Докажите это, рассмотрев случаи, когда соседями красной точки
являются синие точки, красные точки, точки разных цветов.) Но для двух красных
точек наша сумма равна 2 (не делится на 3), а для двух синих точек — равна 0
(делится на 3).

Пример 2. На столе стоят 16 стаканов. Из них 15 стаканов стоят
правильно, а один перевернут донышком вверх. Разрешается одновременно
переворачивать любые четыре стакана. Можно ли, повторяя эту операцию, поставить
все стаканы правильно?

Решение. Посмотрим, как изменяется количество правильно
стоящих стаканов при каждой такой операции. Очевидно, что это зависит от того,
сколько из переворачиваемых стаканов стоят правильно, а сколько — вверх дном. А
именно: 
— если все четыре переворачиваемых стакана стоят правильно, то количество
правильно стоящих стаканов уменьшится на 4; 
— если из четырех стаканов правильно стоят три, то это количество уменьшится на
2; 
— если два, то количество не изменится; 
— если один, то увеличится на 2; 
— если все переворачиваемые стаканы стояли вверх дном, то количество правильно
стоящих стаканов увеличится на 4.

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

Пример 3. Над строкой из четырёх чисел 1, 9, 8, 8 проделаем
следующую операцию: между каждыми двумя соседними числами впишем число, которое
получится в результате вычитания левого числа из правого. Над новой строкой
проделаем ту же операцию и т.д. Найдите сумму чисел строки, которая получится
после ста таких операций.

Решение. Посмотрим, как изменяется сумма чисел строки после
одной операции. Пусть a₁, a₂,…, a_n — строка, к
которой применяется операция. Тогда новая строка имеет вид a₁, a₂ − a₁, a₂, a₃ − a₂,…, a_n−1,a_n − a_n−1, a_n. Сумма чисел
новой строки равна a₁ + … + a_n + (a₂ − a₁)
+ (a₃ − a₂) + … + (a_n − a_n−1)
= s + a_n − a₁,
где s — сумма чисел
исходной строки. Заметим теперь, что для любой строки, полученной из строки 1,
9, 8, 8 описанной в условии задачи операцией, a_n = 8, a₁ = 1. Следовательно, после каждой такой
операции сумма чисел увеличивается на семь. Сумма чисел исходной строки равно
26. Следовательно, сумма чисел строки, которая получится после ста таких
операций, равна 26 + 7 · 100 = 726.

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

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

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

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

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

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

Пример 5. Круг разбит на n секторов, в некоторых секторах стоят
фишки — всего фишек n+1. Затем позиция подвергается преобразованиям. Один шаг
преобразования состоит в следующем: берутся какие-нибудь две фишки, стоящие в
одном секторе, и переставляются в разные стороны в соседние секторы. 
Докажите, что через некоторое число шагов не менее половины секторов будет
занято.  

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

Раскраски.

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

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

Рассмотрим примеры.

Пример 1: Дан квадрат клетчатой бумаги
размером 8 x 8, из которого вырезаны две крайние диагональные клетки
(верхняя-правая и нижняя-левая). Можно ли полученную фигуру покрыть
прямоугольниками размером 1 x 2?

Решение: Раскрасим наш обрезанный квадрат
с помощью двух цветов в шахматную расцветку. Заметим, что отрезанные
диагональные клетки будут одного цвета. Отметим также, что в нашем раскрашенном
квадрате любые соседние две клетки (имеющие общую сторону) будут разного цвета.
Это значит, что любой прямоугольник размером 1 x 2, которым мы будем пытаться
покрыть обрезанный квадрат будет покрывать клетки обоих цветов. И если мы
сможем покрыть обрезанный квадрат прямоугольниками 1 x 2, то будет покрыто
одинаковое количество клеток с разными цветами; то есть фигура должна содержать
одинаковое количество клеток обоих цветов. Но так как мы отрезали диагональные
клетки одного цвета, то их количество в обрезанном квадрате на две меньше. Это
означает, что мы не сможем польностью покрыть указанный обрезанный квадрат
прямоугольниками 1 x 2.

Пример 2: Граф — это набор вершин,
причем некоторые из них соединены ребрами (каждое ребро соединяет ровно две
вершины графа). Раскраска вершин графа называется правильной, если вершины
одного цвета не соединены ребром. Некоторый граф правильно раскрашен в k
цветов, причем его нельзя правильно раскрасить в меньшее число цветов.

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

Решение: Цвета, в которые покрашен
граф, занумеруем от 1 до k. Те вершины цвета 2, которые не соседствуют ни с
какими вершинами цвета 1, перекрасим в цвет 1. Новая раскраска будет
правильной, поэтому в ней k цветов. Значит, какие-то вершины цвета 2 не
перекрашены и потому соседствуют с вершинами цвета 1. Аналогично, вершины цвета
3, которые не соседствуют с вершинами цвета 2, перекрасим в цвет 2, и т. д.
вплоть до последнего цвета.

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

Пример 3: На двух клетках шахматной
доски стоят чёрная и белая фишки. За один ход можно передвинуть любую из них на
соседнюю по вертикали или горизонтали клетку (две фишки не могут стоять на
одной клетке). Могут ли в результате таких ходов встретиться все возможные
варианты расположения этих двух фишек, причём ровно по одному разу? 

Решение: Назовём расположение фишек одноцветным,
если фишки стоят на клетках одного цвета, разноцветным — если на клетках
разного цвета. Заметим, что при перемещениях фишек одноцветные и разноцветные
расположения чередуются, значит, их должно быть поровну. Однако общее
количество разноцветных расположений равно 2*32², а одноцветных —
2*32*31, поскольку две фишки не могут стоять на одной клетке. Значит, все
возможные расположения встретиться не могут.

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

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

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

Решение: Рассмотрим «поддоску»
размера 61 x 61 бесконечной доски, на которой стоят 16² = 256
пешек. Допустим, что пешки находятся на чёрных полях. Тогда общее число чёрных
полей на рассмотренной доске 61 x 61 равно 1861, белых — 1860. Вычислим
количество чёрных полей, на которые может попасть конь с этих 1860 белых полей.
Внутри рассмотренной доски их 1861 – 256 (256 заняты пешками), вне доски их 248
— на рисунке 1 они показаны звёздочками. Всего таких полей 1861 – 256 + 248 = 1853
— слишком мало.

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

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

Особые, крайние объекты часто служат
«краеугольным камнем» решения. Так, например, рассматривают наибольшее число,
ближайшую точку, угловую точку, вырожденную окружность, предельный случай.
Поэтому полезно сразу рассматривать особые, крайние объекты. В задачах на метод
крайнего работает метод минимального контрпримера: допустим, утверждение задачи
неверно. Тогда существует минимальный в некотором смысле контрпример. И если
окажется, что его можно ещё уменьшить, то получится искомое противоречие.

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

Пример 1. У Пети всего 28 одноклассников. У каждых двух из 28
различное число друзей в этом классе. Сколько друзей у Пети?

Решение. У одноклассников Пети может быть 0, 1, 2, …, 28
друзей — всего 29 вариантов. Но, если кто-то дружит со всеми, то у всех не
меньше одного друга. Поэтому либо есть такой, кто дружит со всеми, либо есть
такой, кто не дружит ни с кем. В обоих случаях остается 28 вариантов: 1, 2,
…, 28 или 0, 1, …, 27.

Обозначим того, у кого больше всего друзей
через A, а того, у кого их меньше всего — через B. В
первом случае A дружит со всеми, а B — только
с одним человеком, т. е. только с A. Во втором случаеB не
дружит ни с кем, а A дружит со всеми, кроме одного, т. е.
со всеми, кроме B.

Итак, в каждом из случаев A дружит
с Петей, а B — нет. Переведем A и B в
другой класс. Как мы уже видели, A дружит со всеми из
оставшихся, а B — ни с кем из оставшихся. Поэтому после
перевода у каждого стало на одного друга меньше (среди одноклассников). Значит,
у оставшихся Петиных одноклассников снова будет разное число друзей среди
одноклассников.

Теперь снова переведем самого
«дружелюбного» и самого «нелюдимого» в другой класс
и т. д.

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

Пример 2. а) Дано шесть натуральных чисел. Все они различны и
дают в сумме 22. Найти эти числа и доказать, что других нет.

б) Тот же вопрос про 100 чисел, дающих в сумме
5051.

Решение. Расположим числа в порядке возрастания. Тогда
очевидно, что каждое число будет больше своего номера. Найдем сумму номеров
всех чисел:
а) 1 + 2 + 3 + 4 + 5 + 6 = 21;
б) 1 + 2 +  …  + 100 = 5050.
(Последнюю сумму можно посчитать следующим способом:
(1 + 100) + (2 + 99) +  …  + (50 + 51) = 50 • 101 = 5050.)
В обоих случаях эта сумма на единицу меньше суммы самих чисел. Значит, одно
число на единицу больше своего номера, а остальные — равны ему. Числом, большим
своего номера, может быть только последнее. Действительно, если какое-то число
больше своего номера, то все последующие числа тоже больше своего номера.

Поэтому искомыми числами будут в пункте а) 1,
2, 3, 4, 5, 7; а в пункте б)  1, 2, …, 99, 101.

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

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

Литература.

1.Журнал Потенциал
№9,2005 – Королёв Д.Н. «Инварианты в задачах по математике и программированию».

2. Научно-популярный физико-математический журнал
«Квант» – А.Толпыго «Инварианты»

3. Журнал
«Квант» — «Делимость чисел» И.Г.Булавко.

4. МОСКОВСКИЙ
ЦЕНТР НЕПРЕРЫВНОГО МАТЕМАТИЧЕСКОГО ОБРАЗОВАНИЯ, А. Я. Канель-Белов, А. К.
Ковальджи «КАК РЕШАЮТ НЕСТАНДАРТНЫЕ ЗАДАЧИ» под редакцией В. О. Бугаенко.

5. Ю.Ф.фоминых
«Принцип Дирихле» Журнал «Математика в школе», 1996 №3

6. В.Г.Болтянский
«Шесть зайцев в пяти клетках» Журнал «Квант», 1977г №2.

7. Д.Х. Муштари
«Подготовка к математическим олимпиадам: задачи, темы, методы». Казанский
университет, 1990г.

8. «Путеводитель в
мир науки для школьников» (математика) — «Формулировка принципа Дирихле»
Андреев А.А., Савин А.Н., Саушкин М.Н.

9.Андреев А.А.,
Горелов Г.Н., Люлев А.И., Савин А.И., «Принцип Дирихле», Самара «Пифагор»,
1997г.

10.И.Л.Бабинская
«Задачи математических олимпиад» Наука, 1975г.

11. http://www.math.md/school/krujok/inductr/inductr.html

12. http://www.chem-astu.ru/chair/study/algebra-geometry/?p=17

13. http://foxford.ru/wiki/matematika/poluinvariant

14. http://www.cleverstudents.ru/articles/induction.html

15. http://studyport.ru/referaty/tochnyje-nauki/3804-metod-matematicheskoj-induktsii

16. http://math4school.ru/zadachi.html

17. http://matworld.ru/teorija-chisel/delimost-chisel.php

18. http://mathus.ru/math/

19. http://school-collection.edu.ru/catalog/rubr/1040fa23-ac04-b94b-4a41-bd93fbf0d55a

Банк задач по представленной теме.

(приложение)

1 задача

2 задача

3 задача

4 задача

5 задача

6 задача

7 задача

8 задача

9 задача

10 задача

11 задача

12 задача

13 задача

14 задача

15 задача

16 задача

17 задача

18 задача

19 задача

20 задача

21 задача

22 задача

23 задача

24 задача

25 задача

26 задача

27 задача

28 задача

29 задача

30 задача

31 задача

32 задача

33 задача

34 задача

35 задача

36 задача

37 задача

38 задача

39 задача

40 задача

41 задача

42 задача

43 задача

44 задача

45 задача

46 задача

47 задача

48 задача

49 задача

50 задача

51 задача

52 задача

53 задача

54 задача

55 задача

56 задача

57 задача

58 задача

59 задача

60 задача

61 задача

62 задача

63 задача

64 задача

65 задача

66 задача

67 задача

68 задача

69 задача

70 задача

71 задача

72 задача

73 задача

74 задача

75 задача

76 задача

77 задача

78 задача

79 задача

80 задача

81 задача

82 задача

83 задача

84 задача

85 задача

86 задача

87 задача

88 задача

89 задача

90 задача

91 задача

92 задача

93 задача

94 задача

95 задача

96 задача

97 задача

98 задача

99 задача

100 задача

101 задача

102 задача

103 задача

104 задача

105 задача

106 задача

107 задача

108 задача

109 задача

110 задача

111 задача

112 задача

113 задача

114 задача

115 задача

116 задача

117 задача

118 задача

1 октября 2017

В закладки

Обсудить

Жалоба

Олимпиадные задачи по математике

30 заданий с решениями.

Данные задачи были использованы в олимпиаде учителей математике «Профи». Олимпиаду проводит высшая школа экономики с 2008 года. В прошлом году приняли участие 35 тыс. учителей. Листовка «Профи-2017»: 17.pdf

mo-u-m.pdf