Блог учителя математики Синкевич Л.М.: Копилка олимпиадника

Числа

Общепринятые обозначения:

N= 1,2,3,4,5,6,7,8, ... - множество натуральных чисел;

Z= ..., -3,-2,-1,0,1,2,3, ... - множество целых чисел;

Q= множество рациональных чисел;

Иррациональные числа - это числа, которые нельзя представить в виде обыкновенной дроби , где m Z, n N;

R- множество действительных чисел - это объединение множеств рациональных и иррациональных чисел.

Простое число- натуральное число, имеющее ровно два натуральных делителя: себя и единицу. Первые простые числа: 2,3,5,7,11,13, ... Натуральное число 1 не является простым числом, так как имеет только один натуральный делитель.

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

Взаимно простые числа - натуральные числа, не имеющие общих натуральных делителей, отличных от 1.

"Простых чисел существует больше любого указанного числа их". (Евклид (конец IV - III в. до н.э. ), "Начала", девятая книга)

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

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

Метод математической индукции (ММИ) применяется для доказательства утверждений, зависящих от натуральной переменной. Основан он на принципе математической индукции: утверждение А(n), зависящее от натуральной переменной n, считается истинным, если проверена истинность А(1) (так называемое основание индукции) и для любого натурального числа из предположения, что верно А(k) (так называемое предположение индукции), выведено, что также А(k+1) (доказана возможность осуществления индуктивного перехода).

Задача 1.

Доказать , что при любом натуральном n число

3²ⁿ⁺¹+2ⁿ⁺² делится на 7.

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

Обозначим a_n=3²ⁿ⁺¹+2ⁿ⁺².

1) Начало индукции.

Если n=1 , то a₁=35 делится на 7.

(впрочем, здесь начать можно и с n=0)

2) Индуктивный переход.

Пусть a_k делится на 7. ( предположение индукции)

Докажем справедливость утверждения для n=k+1 a_k₊₁=3²⁽^k⁺¹⁾⁺¹+2⁽^k⁺¹⁾⁺²=3²^k⁺¹ 9+ 2^k⁺² 2= (3²^k⁺¹+2^k⁺²)9-7 *2^k⁺²=9a_k-7*2^k⁺²

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

Задача 2.

Доказать, что число 7ⁿ⁺¹+8²ⁿ^-1 делится на 19.

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

1) если n=1 , то 7²+8¹+57, а 57 делится на 19.

2) предположим, что утверждение верно при некотором натуральном n=k , т.е. число 7^k⁺¹+8²^k^-1 делится на 19.

Докажем верность утверждения для n=k+1

7⁽^k⁺¹⁾⁺¹+8²⁽^k^+1)-1=7^k⁺²+8²^k⁺¹=7*7^k⁺¹+64*8²^k^-1=7(7^k⁺¹+8²^k^-1)+57*8²^k^-1.

Так как каждое слагаемое полученной суммы делится на 19, то и 7^k⁺²+8²^k⁺¹также делится на 19. Утверждение доказано.

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

При решении задач "на доказательство" часто бывает полезен так называемый "принцип Дирихле" (Петер Густав Лежен Дирихле (1805-1859) - известный немецкий математик). В самой простой форме он звучит так: нельзя посадить трёх кроликов в две клетки так, чтобы в каждой клетке находилось не больше одного кролика. Или, если в N клетках сидит не меньше чем N+1 кроликов, то найдётся клетка, в которой сидит не меньше двух кроликов. если же в трёх клетках сидят два кролика, то хотя бы одна клетка пуста.

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

Иногда используют обобщённый принцип Дирихле:

Пусть в N клетках сидит не менее kN+1 кроликов, тогда в какой-то из клеток сидит, по крайней мере, k+1 кролик.

Следствие из принципа Дирихле:

Если сумма n чисел равна S, то среди них есть как число, не больше S/n, так и число, не меньшее S/n. Конечно же, ведь если, например, все числа больше S/n, то их сумма больше S, что противоречит условию или если все числа меньше S/n, то их сумма меньше S, что также противоречит условию.
Задачи.
1. В мешке лежат шарики двух разных цветов: черного и белого. Какое наименьшее число шариков нужно вынуть из мешка вслепую так, чтобы среди них заведомо оказались два шарика одного цвета?
2. В лесу растет миллион елок. Известно, что на каждой из них не более 600000 иголок. Докажите, что в лесу найдутся две елки с одинаковым числом иголок.
3. Дано 12 целых чисел. Докажите, что из них можно выбрать два, разность которых делится на 11.
4. В магазин привезли 25 ящиков с тремя разными сортами яблок (в каждом ящике яблоки только одного сорта). Докажите, что среди них есть по крайней мере 9 ящиков с яблоками одного и того же сорта.

Сосновый лес растет на участке квадратной формы площадью 1 га (100 х 100 метров). На этом участке растут 44 сосны и больше ничего (сосны считать точкой). Докажи, что на этом участке можно построить прямоугольной формы дом длиной 20 м и шириной 10 м, не срубив ни одной сосны.

Требование "не срубив ни одной сосны" расплывчатое: можно сжечь, выдернуть,...).
По принципу абстакции подразумеваем простейшие условия ("участок" имеет форму плоского квадрата, не строим "прямоугольный дом из сосен", а выбираем на "участке" "площадку" в форме плоского прямоугольника так, чтобы на этой площадке не росли сосны, занимающие пренебрежительно маленькую (точечную) площадь.
Так как задача по теме "принцип Дирихле", то формула ответа выглядит так: на участке площадью 1 га можно разместить 50 площадок, так как площадь каждой "площадки" 200 кв. м. Так как сосен всего 44, то на 6 площадках не окажется сосен, если на остальных площадках - по одной сосне. - See more at: http://e-science.ru/?q=comment/390778#sthash.HkcTi3bB.dpuf

Сосновый лес растет на участке квадратной формы площадью 1 га (100 х 100 метров). На этом участке растут 44 сосны и больше ничего (сосны считать точкой). Докажи, что на этом участке можно построить прямоугольной формы дом длиной 20 м и шириной 10 м, не срубив ни одной сосны.

Требование "не срубив ни одной сосны" расплывчатое: можно сжечь, выдернуть,...).
По принципу абстакции подразумеваем простейшие условия ("участок" имеет форму плоского квадрата, не строим "прямоугольный дом из сосен", а выбираем на "участке" "площадку" в форме плоского прямоугольника так, чтобы на этой площадке не росли сосны, занимающие пренебрежительно маленькую (точечную) площадь.
Так как задача по теме "принцип Дирихле", то формула ответа выглядит так: на участке площадью 1 га можно разместить 50 площадок, так как площадь каждой "площадки" 200 кв. м. Так как сосен всего 44, то на 6 площадках не окажется сосен, если на остальных площадках - по одной сосне.
- See more at: http://e-science.ru/?q=comment/390778#sthash.HkcTi3bB.dpuf

5.15 мальчиков собрали 100 орехов. Докажите, что какие-то два из них собрали одинаковое число орехов.

Сосновый лес растет на участке квадратной формы площадью 1 га (100 х 100 метров). На этом участке растут 44 сосны и больше ничего (сосны считать точкой). Докажи, что на этом участке можно построить прямоугольной формы дом длиной 20 м и шириной 10 м, не срубив ни одной сосны.

Требование "не срубив ни одной сосны" расплывчатое: можно сжечь, выдернуть,...).
По принципу абстакции подразумеваем простейшие условия ("участок" имеет форму плоского квадрата, не строим "прямоугольный дом из сосен", а выбираем на "участке" "площадку" в форме плоского прямоугольника так, чтобы на этой площадке не росли сосны, занимающие пренебрежительно маленькую (точечную) площадь.
Так как задача по теме "принцип Дирихле", то формула ответа выглядит так: на участке площадью 1 га можно разместить 50 площадок, так как площадь каждой "площадки" 200 кв. м. Так как сосен всего 44, то на 6 площадках не окажется сосен, если на остальных площадках - по одной сосне.
- See more at: http://e-science.ru/?q=comment/390778#sthash.HkcTi3bB.dpuf

Инвариант

Инвариантом некоторого преобразования называется величина или свойство, не изменяющееся при этом преобразовании.

Задачи на инварианты можно условно разбить на два вида: те, в которых требуется доказать, что заданная величина есть инвариант при заданных преобразованиях, и те, в которых инвариант используется при решении и сразу не очевиден. Второй вид, конечно, сложнее, так как найти, что же в задаче будет инвариантом, - большая удача, на которую можно рассчитывать лишь при наличии определённого опыта в решении подобных задач. Кроме того, если подобранный инвариант даёт одинаковые значения для двух данных объектов, то это ещё не означает того, что их можно получить друг из друга с помощью указанных в задаче операций. С уверенностью можно только сказать, что если подобранный к преобразованиям инвариант даёт разные значения для двух данных объектов, то их нельзя получить друг из друга указанными преобразованиями. Иногда инвариант применяется не для того, чтобы доказать, что какой-то объект нельзя получить из данного, а для того, чтобы узнать, какие объекты можно получить из исходного объекта.

Комбинаторика

Школьный курс комбинаторики обычно имеет дело с задачами выбора и расположения элементов некоторого, обычно конечного, множества, согласно неких правил.
Для формулирования и решения задач по комбинаторике используют следующие конфигурации: перестановки, размещения, сочетания.
Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n - число элементов множества.
Перестановка.
Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Перестановкой из n элементов называется такой набор элементов множества, которые отличаются от исходного лишь порядком элементов. Обычно перестановка обозначается как P_n и рассчитывается по формуле:
P_n = n!

Пример:
Найти число перестановок множества, состоящего из трех элементов: A, B, C.
Согласно формуле, количество перестановок будет равно 3! = 6.
Действительно, это наборы (ABC),(ACB),(BAC),(BCA),(CAB),(CBA).

Размещение.
Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Размещением из n элементов по k будет называться упорядоченное подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Обычно перестановка обозначается как A_n^k и рассчитывается по формуле:

A_n^k =

n!(n - k)!

Пример:
Найти число размещений множества, состоящего из четырех элементов: A, B, C, D по два, т.е. сколько различных размещений по два элемента можно составить из указанного множества.
Согласно формуле, количество размещений будет равно ^4!/_(4-2)! = ²⁴/₂ = 12.
Действительно, это наборы (AB),(BA),(AC),(CA),(AD),(DA),(BC),(CB),(BD),(DB),(CD),(DC).

Сочетание.
Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Сочетанием из n элементов по k будет называться подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Подмножества, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Обычно сочетание обозначается как С_n^k и рассчитывается по формуле:

С_n^k =

n!k!(n - k)!

Пример:
Найти число сочетаний множества, состоящего из четырех элементов: A, B, C, D по два.
Согласно формуле, количество сочетаний будет равно ^4!/_2!(4-2)! = ²⁴/₄ = 6.
Действительно, это наборы (AB),(AC),(AD),(BC),(BD),(CD).

Свойства сочетаний:
1. С_n⁰ = 1.
2. С_n^k = С_n^{n - k}.
3. С_n^k = С_{n - 1}^{k - 1} + С_{n - 1}^k
4. С_n⁰ + С_n¹ + С_n² + ... + С_n^{n - 1} + С_nⁿ = 2ⁿ.
Сочетание играет важную роль в математике. В частности, он используется в биноме Ньютона.
Бином Ньютона.
Бином Ньютона - это отношение, позволяющая представить выражение (a + b)ⁿ (n ∈ Z⁺) в виде многочлена, а именно:
(a + b)ⁿ = aⁿ + С_n¹a^{n - 1}b + С_n²a^{n - 2}b² + ... + С_n^ka^{n - k}b^k + ... + С_n^{n - 1}ab^{n - 1} + bⁿ.
Числа С_n¹, С_n², ... , С_n^{n - 1} называются биномиальными коэффициентами.
С помощью следующей таблицы можно определить значения биномиальных коэффициентов для любой степени. Строится он следующим образом - любое число образуется суммой рядом стоящих чисел над ним. Именно потому эта таблица имеет название треугольник Паскаля.

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

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

Пример:
Представить в виде многочлена (a + 1)⁴.
Согласно таблице, в случае четвертой степени коэффициенты результирующего многочлена будут равны 1, 4, 6, 4, 1.
И, действительно (a + 1)⁴ = a⁴ + 4a³ + 6a² + 4a + 1.
Произведение всех натуральных чисел от 1 до n включительно в математике используется очень часто. Поэтому для него ввели специальное обозначение n!, читается: "эн-факториал".

Например, 1!=1, 2!=1*2=2, 3!=1*2*3=6, 4!=1*2*3*4=24, 5!=1*2*3*4*5=120 и т.д. Для удобства написания некоторых комбинаторных формул принято считать 0!=1.

Круги Эйлера – задачи на пересечение или объединение множеств

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

Любимые мультфильмы Среди школьников шестого класса проводилось анкетирование по любимым мультфильмам. Самыми популярными оказались три мультфильма: «Белоснежка и семь гномов», «Губка Боб Квадратные Штаны», «Волк и теленок». Всего в классе 38 человек. «Белоснежку и семь гномов» выбрали 21 ученик, среди которых трое назвали еще «Волк и теленок», шестеро – «Губка Боб Квадратные Штаны», а один написал все три мультфильма. Мультфильм «Волк и теленок» назвали 13 ребят, среди которых пятеро выбрали сразу два мультфильма. Сколько человек выбрали мультфильм «Губка Боб Квадратные Штаны»? Решение В этой задаче 3 множества, из условий задачи видно, что все они пересекаются между собой. Получаем такой чертеж:

Учитывая условие, что среди ребят, которые назвали мультфильм «Волк и теленок» пятеро выбрали сразу два мультфильма, получаем:

21 – 3 – 6 – 1 = 11 – ребят выбрали только «Белоснежку и семь гномов».
13 – 3 – 1 – 2 = 7 – ребят смотрят только «Волк и теленок».
Получаем:

38 – (11 + 3 + 1 + 6 + 2 + 7) = 8 – человек смотрят только «Губка Боб Квадратные Штаны».
Делаем вывод, что «Губка Боб Квадратные Штаны» выбрали 8 + 2 + 1 + 6 = 17 человек.
Ответ. 17 человек выбрали мультфильм «Губка Боб Квадратные Штаны».

Олимпиадные задачи с решением.

1. Можно ли разрезать клетчатый прямоугольник размерами 20×2011 на две равные части так, чтобы из получившихся частей нельзя было вырезать крестика из пяти клеток?

Ответ: да, можно. Решение. Так как одна сторона четная, то надо действовать по принци-пу см. рис. При этом длина горизонтальной стороны не имеет роли, а вертикальная сторона должна быть четной.
2. Когда у Васи спросили, сколько ему лет, он сказал: «Я втрое моло-же папы, но зато втрое старше брата Алеши». А его родная сестра Аня сказала, что она вдвое моложе папы, зато вдвое старше своей сестры Кати. Известно, что папе не больше 60 лет. А сколько ему лет?

Ответ: 36 лет. Решение. Из высказывания Васи следует, что воз-раст папы делится на 9, а из высказываний Ани следует, что он де-лится на 4. Следовательно, он делится на 36. Единственное число, которое меньше 60 и делится на 36, это само число 36.
3. В школе прошел забег с участием 10 спортсменов. На следующий день каждого из них спросили, какое место он занял, и каждый, ес-тественно, назвал одно число от 1 до 10. При этом один соврал, а ос-тальные сказали правду. Сумма их ответов оказалась равна 47. Какое место занял совравший спортсмен и что именно он сказал? Приведи-те все примеры и докажите, что других нет.

Ответ: Спортсмен, занявший 10 место, сказал, что занял второе, или спортсмен, занявший 9 место, сказал, что занял первое. Решение. Если бы никто не врал, то в сумме получилось бы число 1+2+3+4+5+…+10 = 55. А получилось число, которое на 8 меньше, то есть один назвал номер места, на 8 выше. Это могли сделать только спорт-смены, занявшие 9 или 10 места, назвав первое или второе место соответственно.
4. Первоклассница Катя умеет только умножать числа на 2, а её младшая сестрёнка Оля может лишь поменять цифры в числе местами (ставить 0 на первое место нельзя). Могут ли они со-обща получить из числа 3 число 2011?

Ответ: нет. Решение. Изначальное число делится на 3, после умножения и перестановки цифр дели-мость на три не меняется, поэтому получить число 2011, не кратное 3, невозможно.
5. Трехзначное число А записывается только двойками и тройками, а трехзначное число В – только чет-верками и пятерками. Докажите, что произведение АВ не может записываться одними шестерками и се-мерками.

Решение. Самые маленькие возможные числа А и В – это 222 и 444. Их произведение равно 98568. Са-мые большие возможные числа А и В – это 333 и 555. Их произведение равно 184815. Все остальные возможные произведения АВ лежат между этими числами. Но в этом промежутке нет чисел, начинаю-щихся на 7.
6. В мешке у Деда Мороза лежат конфеты трёх видов: шоколадные, ириски и леденцы. Дед Мороз знает, что если вынуть любые 100 конфет из мешка, то среди них обязательно найдутся конфеты всех трёх ви-дов. Какое наибольшее количество конфет может быть в мешке у Деда Мороза?

Ответ: 148 конфет. Решение. Гарантировать, что точно найдутся конфеты всех трех сортов, можно, если число взятых конфет больше, чем конфет в сумме в двух наибольших сортах и еще одна конфета. Итак, в сумме в двух наибольших по численности сортах 99 конфет, поэтому во втором по численности сорте конфет не более 49 конфет. Значит, и в оставшемся сорте не более 49 конфет, а значит, конфет не более 148.
7. В первых трех классах учится 80 детей, причем третьеклассников вдвое больше, чем второклассников. На Новый Год ученики первых трех классов дарили друг другу подарки. Известно, что каждый второклассник подарил на один подарок больше, чем получил, а каждый третьеклассник - на два больше, чем получил. Зато каждый первоклассник получил на пять подарков больше, чем подарил. Сколько учеников учится в третьем классе?

Ответ: 40 третьеклассников. Решение: Если количество второклассников взять за x, то третьеклассни-ков всего 2x. «Убыль» по подаркам среди 2-3 классов составляет x+22x = 5x, при этом она обязательно равна «прибыли» первоклассников. Но тогда всего первоклассников 5x:5 = x, поэтому x+x+2x = 4x = 80, x = 20, отсюда ответ.
8. В нескольких вазочках лежат конфеты. Если во всех вазочках лежит разное количест-во конфет, то Андрей добавляет несколько конфет (не очень много, не больше, чем ко-личество остальных вазочек) в ту вазочку, в которой меньше всего конфет. Докажите, что рано или поздно количество конфет в каких-то двух вазочках сравняется.

Решение. Обозначим число вазочек за n+1. Андрей кладет не более n конфет. Если разница между наи-меньшей и следующей по величине вазочкой больше или равна n, тогда Андрей кладет туда конфеты, пока она не стане меньше n. Если вазочки не сравнялись, то рано или поздно одна перерастет другую, при этом, так как было добавлено не более n конфет, то разность между ними не превысит n, и так будет продолжаться до конца. В то же время численность конфет постоянно увеличивается до тех пор, пока эта разность со следующей по величине вазочкой не станет меньше n. Если вазочки не будут сравниваться, то так будет продолжаться до тех пор, разность между всеми вазочками не станет меньше n. Так как ва-зочек всего n+1, то если количество в каждой вазочке свое, то разность между крайними должна быть равна n, и в то же время она должна быть меньше n.
9. Можно ли переложить показанную на рисунке пирамидку из кубиков так, чтобы ее форма сохрани-лась, а все соседи у каждого из кубиков стали новыми? Ответ обоснуйте.

Ответ: Нельзя. Решение. Кубик 5 соседствует со всеми остальными кубиками, кроме 1. После перекладывания у него будет не меньше двух соседей. Значит, среди них останется хотя бы один старый сосед.
10. Дно квадратного бассейна выложено квадратными плитками двух цветов, как показа-но на рисунке. Прораб заказал светлых плиток на 1000 больше, чем темных. Найдите размеры бассейна.

Ответ: 1000×1000. Решение. Каждая новая белая полоска на 2 квадратика больше, чем черная. Если белых полосок n, то белых плиток больше на 2n. Если после этого идет еще черная полоска, она имеет номер 2n+1, и в ней 2(2n+1)–1=4n+1 плитка. В этой ситуации черных плиток становится на 2n+1 больше. Следовательно, все заканчивается белой полосой, причем белых полос 500, и черных полос 500.
11. На плоскости стоит шахматный конь. Известно, что он совершал прыжки двух видов: либо на два мет-ра на север и метр на восток, либо на два метра на восток и метр на север. В итоге он удалился от на-чальной точки на 40 м на север и на 50 м на восток. Сколько прыжков сделал конь?

Ответ: 30 прыжков. Решение. Сумма перемещений коня на север и восток за один прыжок, независимо от его вида, равна 3 метрам. Общее перемещение коня по условию составило 90 м. Поэтому он совершил 90:3 = 30 прыжков.
12. Дорогу разделили на пять частей (не обязательно равной длины). Коля знает длину дороги. Ему раз-решено спросить, чему равно расстояние между серединами любых двух частей, а он хочет точно узнать длину хоть какой-нибудь части. Докажите, что он может сделать это за два вопроса.

Решение. Первым вопросом Коля должен спросить расстояние между серединами первой и последней части. Вычитая это число из общей длины дороги, он получит сумму половин первой и последней части. Умножив на 2, он получит сумму первой и последней части. Вычитая из общей длины, он получает сумму второй, третьей и четвертой частей, то есть средней части дороги. Второй вопрос он задает про расстоя-ние от середины второй части до середины четвертой части. Действуя аналогично, он может узнать дли-ну третьей части дороги.

Копилка олимпиадника

Круги Эйлера – задачи на пересечение или объединение множеств

Комментариев нет:

Отправить комментарий