Завдання учнівської олімпіади з математики
Клас
1. Розставте на колі 6 різних чисел так, щоб кожне з них дорівнювало добутку двох сусідніх.
2. У родині 4 особи. Якщо Марійці підвищити стипендію удвічі, то загальний прибуток усієї родини зросте на 5%, якщо замість цього мамі підвищити зарплату удвічі, то – на 15%, а якщо ж підвищити удвічі зарплату татові, то – на 25%. На скільки відсотків зросте прибуток усієї родини, якщо підвищити удвічі пенсію дідусеві?
3. Дядько Іван купив на оптовому ринку партію ручок і пропонує покупцям або одну ручку за 5 гривень, або три ручки за 10 гривень. Від кожного покупця він отримує однаковий прибуток. Яка оптова ціна ручки?
4. У країні 15 міст, деякі з них з'єднані авіалініями, що належать трьом авіакомпаніям. Відомо, якщо навіть будь-яка з авіакомпаній припинить польоти, то можна буде дістатися з будь-якого міста в будь-яке інше (можливо, з пересадками), користуючись рейсами інших двох компаній. Яка найменша кількість авіаліній може бути в країні?
Клас
1. У книзі рекордів Гіннесса написано, що найбільше відоме просте число дорівнює 23021377–1. Чи не друкарська це помилка?
2. Приходячи до тиру, гравець вносить у касу 100 гривень. Після кожного вдалого пострілу кількість його грошей збільшується на 10%, а після кожного промаху зменшується на 10%. Чи могло після кількох пострілів у нього залишитися 80 гривень 19 копійок?
3. Наталя та Інна купили однакові коробки чаю в пакетиках. Відомо, що одного пакетика вистачає на дві або три чашки чаю. Наталі вистачило пакетіків із коробки лише на 41 чашку чаю, а Інні – лише на 58 чашок чаю. Скільки пакетиків чаю було в коробці?
4. Іванко і Петрик на уроці креслення намалювали пуголовків (чотири кола на малюнку – одного радіуса, трикутник – рівносторонній, горизонтальна сторона цього трикутника – діаметр кола). Який з пуголовків має більшу площу?
Клас
1. Розв’яжіть рівняння 
для всіх значень параметра а.
2. Вітя, Антон та Сергійко грали сніговими кульками. Першу снігову кульку кинув Антон. Потім у відповідь на кожну кульку, що в нього влучила, Вітя кидав 6 кульок, Сергійко – 5 кульок, а Антон – 4 кульки . Через деякий час гру було закінчено. Знайдіть, в кого скільки снігових кульок влучино, якщо повз ціль пролетіли 13 кульок. (У себе самого сніговими кульками не кидаються.)
3. Придумайте таке десятизначне число, у записі якого немає нулів, щоб при додаванні до нього добутку його цифр було отримано число з таким самим добутком цифр.
4. У трикутнику ABC на сторонах AC і BC взяті такі точки X і Y, що 
ABX= YAC, AYB= BXC, XC=YB. Знайдіть кути трикутника ABC.
Клас
1. Розв’яжіть рівняння 
для всіх значень параметра а.
2. Добуток п'яти чисел не дорівнює нулю. Кожне з цих чисел зменшили на одиницю, при цьому їх добуток не змінився. Наведіть хоча б один приклад.
3. У магазині три поверхи, переміщуватися між якими можна тільки ліфтом. Дослідження відвідуваності поверхів магазину показало, що з початку робочого дня і до закриття магазину:
а) з покупців, що входять у ліфт на другому поверсі, половина їде на перший поверх, а половина – на третій;
б) серед покупців, які виходять з ліфта на третьому поверсі, менше третини.
На який поверх покупці частіше їздили з першого поверху, на другий чи на третій?
4. У коло вписаний прямокутний трикутник АВС з гіпотенузою АВ. Нехай K – середина дуги ВС, що не містить точку А; N – середина відрізка АС, М – точка перетину променя KN з колом. У точках А і С проведені дотичні до кола, які перетинаються в точці Е. Доведіть, що ЕМK=90o.
Клас
1. Розв’яжіть рівняння 
для всіх значень параметра а.
2. Чи існують такі натуральні числа a, b і c, що у кожного з рівнянь
ax2+bx+c = 0, ax2+bx–c = 0, ax2–bx+c = 0, ax2–bx–c = 0 обидва кореня – цілі?
3. У деяких країнах сумарна зарплата 10% найбільш високооплачуваних працівників становить 90% зарплати всіх працівників. Чи може так бути, що в кожному з регіонів, на які ділиться ця країна, зарплата будь-яких 10% працівників становить не більше 11% всієї зарплати, що виплачується в цьому регіоні?
4. Усередині кута з вершиною M позначена точка A. З цієї точки випустили кульку, яка відбилася від однієї сторони кута в точці B, потім від іншої сторони в точці C і повернулась у точку A («кут падіння» дорівнює «куту відбиття»). Доведіть, що точка O – центр кола, описаного навколо трикутника BCM, лежить на прямій AM.
Клас
1. Розв’яжіть рівняння 
для всіх значень параметра а.
2. По ребрах опуклого многогранника з 2011 вершинами проведена замкнена ламана, що проходить через кожну вершину рівно один раз. Доведіть, що в кожній з частин, на які ця ламана ділить поверхню многогранника, кількість граней з непарним числом сторін – непарна.
3. Чи існують три квадратних тричлена, такі що кожен з них має два різних дійсних кореня, а сума будь-яких двох тричленів не має дійсних коренів?
4. Натуральне число N в 999 ... 99 (k дев'яток) разів більше суми своїх цифр. Зазначте всі можливі значення k і для кожного з них наведіть приклад такого числа.
Вказівки до розв’язання задач олімпіади з математики.
Класс
1. Если рядом стоят числа a и b, то следующим стоит число b/a, за ним 1/a, потом 1/b, наконец, a/b. Эти шесть чисел удовлетворяют условию задачи. Конечно, при неудачном выборе чисел a и b какие-то из указанных чисел совпадут, но нас это не остановит: для решения задачи достаточно предъявить один пример. Например, взять a=2, b=3.
2. Ответ: 55%.
Решение. Если Маше удвоят стипендию, семейный доход возрастёт на размер этой стипендии. Следовательно, Машина стипендия составляет 5% общего дохода. Аналогично, мамина зарплата составляет 15%, а папина – 25%. Оставшаяся доля 100%–5%–15%–25%=55% приходится на дедушкину пенсию. Значит, если ему удвоят пенсию, доход всей семьи возрастёт на 55%.
3 Ответ: оптовая цена ручки – 2 рубля 50 копеек. Если оптовая цена ручки – x рублей, то 5–x=10–3x, откуда x=2,5.
4. Ответ: 21 авиалиния.
Докажем, что меньше, чем 21 линией не обойтись. Вначале докажем, что если 15 городов соединены авиалиниями так, что можно добраться от любого города до любого другого, то авиалиний не меньше 14.
Обозначим число авиалиний через k. Если мы уберём одну из них, города могут распасться на две разрозненные группы, между которыми нет воздушного сообщения, а могут и не распасться. После удаления следующей авиалинии не более одной группы может распасться ещё на две, количество разрозненных групп увеличится не более чем на одну. Продолжая аналогичные рассуждения, получим, что после удаления последней авиалинии количество разрозненных групп не может превысить k+1. Поскольку 15 городов без авиалиний – это 15 групп, то k>14.
Обозначим количество линий у авиакомпаний через a, b и c. По доказанному, у любых двух компаний вместе не менее 14 линий, т. е. у трёх компаний в сумме не менее 21 авиалинии.
Класс
1. Ответ: конечно, это опечатка. Любая степень числа, оканчивающегося цифрой 1, тоже оканчивается цифрой 1. Поэтому разность 23021377-1 оканчивается на 0 и, следовательно, не является простым числом.
2. Ответ: да, могло, если он один раз попал и три раза промахнулся. Решение проще всего найти, если разложить 8019 на множители: 8019=93*11. После удачного выстрела количество денег умножается на 1,1, а после неудачного - на 0,9, и 100*1,1*0,93=80,19
3. Ответ: 20 пакетиков. Поскольку Инна выпила на 17 чашек чая больше Наташи, значит, хотя бы из 17 пакетиков она приготовила по три чашки чая. Оставшиеся 7=58-17*3 чашек можно было получить только одним способом: 2 пакетика на 2 чашки каждый и 1 пакетик на 3 чашки. Значит, в коробке было 17+3=20 пакетиков. При этом Наташа из 19 пакетиков приготовила по 2 чашки, а из двадцатого - 3 чашки чая.
4. Ответ: площади фигур равны.
Идея решения. Наложим одного головастика на другого как показано на рисунке. Нетрудно проверить, что если отрезать от первого головастика заштрихованные сегменты, и повернуть их вокруг точек A1 и B1 на 180o, то получится в точности второй головастик.
Класс
1. 
, если 
, корней нет, если 
, любое число, если 
2. Ответ: в Сергей, Витю и Антона попали по одному разу. Если в Витю, Антона и Сергей попали x, y и z снежков соответственно, то всего было брошено 13+x+y+z снежков (поскольку 13 снежков не достигли цели). С другой стороны, Витя бросил 6x, Сергей – 5y, а Антон – 4z+1 снежков (вместе с первым снежком). Получаем уравнение: 6x+5y+4z+1=13+x+y+z, откуда 5x+4y+3z=12. Так как x, y, z - целые неотрицательные числа, x может быть равен 0, 1 или 2, y - 0, 1, 2 или 3, z - 0, 1, 2, 3 или 4. Перебором находим решения (1,1,1), (0,3,0) и (0,0,4). Но, поскольку в самого себя кидать снежки нельзя, то среди чисел x, y, z не может быть двух нулей. Поэтому возможен только первый случай.
3. Ответ: например, 1111111613.
Найдём какое-нибудь число, удовлетворяющее условию задачи, не обязательно десятизначное. Например, попробуем найти такое число, что после прибавления к нему произведения цифр они попросту меняются местами. Если последние цифры числа - 13, то, чтобы поменять их местами, нужно прибавить 18. Чтобы произведение цифр было 18, нужно дописать ещё цифру 6. Искомым является число 613: 613+6*1*3=631.
Теперь, чтобы получить десятизначное число, припишем слева недостающее число единиц. Произведение цифр от этого не изменится. Например, 1111111613+18=11111111631.
4 Ответ: треугольник равносторонний, все углы по 60o.
Решение. Для внешних углов BXC и AYB треугольников ABX и CAY запишем равенства
BXC= ABX+ BAX, AYB= CAY+ YCA. Так как по условию BXC= AYB, ABX= CAY, получаем, что BAX= YCA, т. е. треугольник ABC является равнобедренным, AB=BC.
Рассмотрим треугольники XBC и YAB. У них равны две стороны и угол не между ними: BXC= AYB, XC=YB, BC=AB. Такие треугольники либо равны, либо XBC+ YAB=180o (мы докажем это ниже), но второй случай невозможен, поскольку XBC+ YAB< ABC+ CAB=180o– ACB<180o. Значит, DXBC=DYAB, следовательно, ABC= BCA, и треугольник ABC равносторонний.
Теперь докажем сформулированный выше факт. Итак, в треугольниках XBC и YAB равны две стороны и угол не между ними: BXC= AYB, XC=YB, BC=AB. Отметим на луче XB точку B' на расстоянии XB'=YA. Точка B' может оказаться как внутри, так и вне отрезка XB. Треугольники XB'C и YAB равны по двум сторонам и углу между ними (XC=YB, XB'=YA, CXB'= BYA). Тогда CB'=CB. Если B и B' совпадают, треугольники XBC и YAB равны. Если же B' не совпадает с B, то в равнобедренном треугольнике B'CB углы B'BC и BB'C равны, а значит, XBC+ XB'C=180o, и XBC+ YAB=180o.
Класс
1. 
, если , 
; корней нет, если 
, 
.
Задание 1. 
, при 
; 
, при 
2. Ответ: например, 5, 6, 7, 8, -1.
3. Ответ: с первого на третий этаж за этот день приехало меньше покупателей, чем с первого на второй.
Предположим, что за весь день на первом этаже в лифт вошло x покупателей, на втором – y, на третьем - z. Заметим, что количество покупателей, вышедших из лифта на каждом из этажей, равно количеству покупателей, вошедших на этом же этаже.
По условию, из покупателей, вошедших на втором этаже, половина едет вниз, а половина - вверх. Значит, со второго этажа на третий едет y/2 покупателей, и столько же со второго на первый. Второе условие можно записать так: z<(x+y+z)/3. Это равносильно тому, что 2z<x+y.
С первого этажа на третий было совершено z–(y/2) поездок, так как всего на третьем этаже вышли из лифта z человек, а y/2 из них приехали со второго этажа. А с первого на второй поднимались те покупатели, входившие в лифт на первом этаже, кто не ехал на третий, т. е. x-(z-(y/2)). Для решения задачи требуется сравнить эти два выражения. Но неравенство z-(y/2)<x-(z-(y/2)) равносильно уже доказанному неравенству 2z<x+y. Тем самым мы доказали, что с первого этажа на третий за этот день приехало меньше покупателей, чем с первого на второй.
4. Пусть точка O - центр окружности. Так как треугольник ABC прямоугольный, точка O совпадает с серединой гипотенузы AB. Угол NOK прямой: действительно, средняя линия NO треугольника ABC параллельна его стороне BC, а прямая OK является высотой равностороннего треугольника BOC (так как она является биссектрисой этого треугольника).
Нетрудно видеть, что точки E, N и O лежат на одной прямой. Действительно, прямоугольные треугольники ECO и EAO равны по катету и гипотенузе, поэтому EO – биссектриса угла AEC. С другой стороны, треугольник AEC - равнобедренный, так как касательные, проведённые к окружности из одной точки равны. Поскольку отрезок EN - медиана в этом треугольнике, то он также является и биссектрисой. Поэтому лучи EN и EO совпадают как биссектрисы угла AEC.
Точки A, E, C и O лежат на одной окружности, так как /ECO=/EAO=90o. Из теоремы о пересекающихся хордах окружности следует, что AN*NC=EN*NO. (1)
Применяя ту же теорему к хордам AC и MK исходной окружности, получаем AN*NC=MN*NK. (2)
Комбинируя (1) и (2), получаем, что MN*NK=EN*NO.
По теореме, обратной к теореме о пересекающихся хордах получаем, что точки М, K, E и O лежат на одной окружности.
Углы EMK и EOK равны, как опирающиеся на одну дугу. Но угол EOK - прямой, значит, и угол EMK – прямой.
Класс
1. х=3а, х=–2а, при 
, корней нет, если 
2. Ответ: да, например, a=1, b=5, c=6.
3. Ответ: да, может. Допустим, что в каждом регионе все получают одинаковую зарплату и есть регион, в котором живут те самые 10% работников, которые получают 90% всей зарплаты.
4. Перпендикуляры к сторонам угла, восставленные в точках B и C, пересекаются в точке M', диаметрально противоположной M. Из равенства углов падения и отражения следует, что M' - точка пересечения биссектрис треугольника ABC. С другой стороны, точка M лежит на пересечении биссектрис углов B'BC и BCC'(см. рис.), следовательно, равноудалена от прямых AB и AC. Поэтому M также лежит на биссектрисе угла BAC. Значит, весь диаметр MM', включая точку O, лежит на биссектрисе AM угла BAC.
Класс
1. 
, при 
; 
, при 
;
2. Выберем любую из получившихся частей. Рассмотрим сумму a1+a2+...+an, где ai – количество сторон i-й грани.
Каждое ребро многогранника, по которому ломаная не проходит, посчитано в этой сумме дважды и поэтому чётность суммы не зависит от числа таких рёбер. Каждое ребро, через которое проходит ломаная, входит в сумму ровно один раз. Таких рёбер 2011, поэтому вся сумма нечётна.
Если бы количество граней с нечётным числом сторон было чётно, то рассмотренная сумма также была бы чётна. Значит, это количество нечётно.
3. Ответ: да, существуют. Например, таковыми являются многочлены (x-10)2-1, x2-1 и (x+10)2-1
4. Ответ: такое число существует для любого k: Nk=9k*(10k-1). Пусть 9k=s1...st0...0 (st не равно 0, нулей на конце может и не быть). Проверим, что сумма цифр числа Nk равна 9k. Запишем разность чисел 9k*10k и 9k, учитывая, что 9k<10k при любом k:
| - | s1s2...st-1 | st | 0...0 | ... | 0...0 | |||
| s1 | ... | st-1 | st | 0...0 | ||||
| s1s2...st-1 | st-1 | 9...9 | (9-s1) | ... | (9-st-1) | (10-st) | 0...0 |
В нижней строчке записано число Nk. Легко видеть, что сумма его цифр равна
s1+...+st–1+9+...+9+(9+1)–s1–...–st=9k. в записи левой части k девяток.
Незважаючи на унікальність олімпіадних завдань, можна все-таки виділити кілька типових ідей, які складають суть задач. Зрозуміло, за визначенням, такий список буде неповним.
· Задачі на інваріант
· Задача – гра
· Комбінаторика
· Теорія графів
· Геометрія
Не існує єдиного методу розв’язання олімпіадних задач. Навпаки, кількість методів постійно поповнюється. Деякі зазачі можна розв`язати кількома різними методами або комбінацією методів. Характерна особливість олімпіадних задач в тому, що розв’язання з вигляду нескладної проблеми може зажадати застосування методів, що використовуються в серйозних математичних дослідженнях. Нижче наводиться (за визначенням) неповний список методів розв’язання олімпіадних задач:
· Доведення выд супротивного
· Принцип Діріхле
· Метод розмальовки
· Контр приклад
· Математична індукція
· Рекурсія
· Метод додаткової побудови
· Метод Гауса
1.1. Інваріант
У цьому розділі розглянемо одне, але дуже важливе математичне поняття - інваріант. Буває воно в задачах, де ми маємо справу з якимись операціями, з якимось процесом, який змінює даний в умові об'єкт. От якщо у об'єкта є якась властивість або характеристика, яка не змінюється при цих операціях - вона і називається інваріантом. Якщо у об'єкта є два стани, при яких інваріант приймає різні значення, то з одного з них не можна перейти в інший (і з другого в перше теж). Але однакове значення інваріанта ще не означає, що так перейти можна.
Задача 1.1. У файлі зберігаються 2003 одиниці і 232 нуля. Програма читає з файлу два довільних числа, видаляє, і записує на їх місце 0, якщо вони були рівні, і 1, якщо ні. Програма запускається багаторазово. Наприкінці у файлі залишається тільки одне число. Чому воно дорівнює, 0 або 1?
Розв’язання: Незважаючи на те, що варіантів дії програми дуже багато, ми можемо встановити відповідь однозначно. Що може прочитати програма за кажний окремий запуск? Або 0 і 0 (і записати 0), або 0 і 1 (і записати 1), або 1 і 1 (і записати 0). У перших двох випадках сума всіх чисел у файлі не змінюється, в останньому - зменшується на 2. У кожному разі, парність цієї суми залишається колишньою. Початково сума була 2003 * 1 +232 * 0 = 2003 - непарна, значить, і в кінці буде непарна. Але наприкінці залишається тільки одне число - воно і дорівнює сумі всіх - тому воно непарне. А так як у файлі бувають тільки нулі й одиниці, то це 1.
Задача 1.2. Є три числа, які можна замінювати за такими правилами: числа a, b і c стираються і замість них записуються (a + b) / 2, (b + c) / 2 і (a + c) / 2.Можно Чи з чисел 101, 73, 125 отримати 77, 79 і 83?
Розв’язання: А давайте так, "про всяк випадок", подивимося, як міняється сума чисел. Було a + b + c, а стало ... замість них записуються (a + b) / 2 + (b + c) / 2 + (a + c) / 2 = (2a +2 b +2 c) / 2 = a + b + c - не змінилася. Тобто, як не крути, а сума трьох чисел не змінюється. Але 101 +73 +125 = 299, а 77 +79 +83 = 239 - суми вихідної та кінцевої трійки різні. Тому з однієї не можна отримати іншу.
(!) А ті, хто захоче взяти в якості інваріанта парність суми або її залишок по якомусь модулю, швидше за все, помиляться, так як початкова та кінцева суми розрізняються на 60, а дільників у 60 ох як багато.
Задача 1.3. Знову є три числа, які можна замінювати вже за іншими правилами: a, b і c - на ab/c, ac/b і bc/a. Чи можна з 5, 17/6 і 3/5 отримати 16/5, 9/4 та 7/6?
Розв’язання: Ну, про те, куди тут переходить сума чисел, навіть думати не хочеться. Що ще буває, крім суми? Добуток, наприклад. Перед операцією добуток чисел - abc, а після: (ab/c) * (ac/b) * (bc/a) = a2b2c2/abc=abc - не змінилося!З начить, добуток трьох чисел залишається постійним при всіх операціях. Але на початку воно було рівним 5*(17/6)*(3/5)= 8,5, а наприкінці (16/5)*(9/4)*(7/6) = 8,4 - не рівні. Тому відповідь "не можна".
(!) Якщо у нас є якийсь набір чисел, над яким здійснюються операції, то завжди варто перевірити, як змінюються при цих операціях сума і добуток всіх чисел. Дуже часто вони самі або їхні залишки по якомусь модулю є інваріантом, за допомогою якого розв’язується завдання.
Зауваження. У завданнях, де питається "чи можна" за допомогою інваріанта можна доводити тільки відповідь "не можна"! Якщо придуманий вами інваріант нічому не суперечить (його значення на початку і наприкінці передбачуваної послідовності операцій не зміниться), то це не означає, що відповідь "можна". По-перше, зазвичай це означає, що придуманий поганий інваріант. По-друге, відповідь "можна" доводиться пред'явленням конкретного прикладу і ніяк інакше.
Інваріант як характеристика нечислових об'єктів. У всіх попередніх прикладах в задачі фігурували числа, від яких ми в якості інваріанта брали якусь функцію. Але, звичайно, у початковому формулюванні може не бути ніяких чисел! Що тоді робити? Звичайно, ці числа придумати.
Задача 1.4. У мові програмування MustDie всього дві команди, для стислості званих M і D. Через збій в компіляторі, дія програми не зміниться, якщо з неї викинути шматок коду MDDM, а також якщо в будь-яке її місце вставити шматок коду DMMDMD або MDMD. Чи можуть програми MMDMD і DMMDD виконуватися однаково?
Розв’язанная: Наше кажучи: чи існує таке рівнозначне перетворення коду, яке переводить одну програму в іншу? Ні, звичайно, і ви вже здогадалися що інваріант тільки треба придумати. В одному шматку 2 команди M 2 команди D, у другому тих і інших по 3, у третьому - знову по 2. Здається, ясно: у будь-якому вставленомк або видаленому шматку команд M і D порівну. Значить не змінюється, правильно, різниця між числом тих і інших команд. Вона буде нашим інваріантом - і дуже добре, так як в одній програмі на одну більше команд M, а в інший на одну більше команд D (значення різниці помінялося в 1 на -1).
Вправа 1.1. Доведіть, що всі білки можуть зібратися на одній ялинки тоді і тільки тоді, коли їх непарне число. (Тобто, для парних чисел узагальнити дане вище рішення, для непарних - придумати приклад.)
(!) Різниця якихось кількостей і набір попарних різниць - теж типові інваріанти. Після суми і твори наступним справою треба перевіряти саме різниці.
Розв’язання: Де ж шукати інваріант? Із сумою чисел у файлі якось складно, тому що третя програма змінює її чорт знає як. В тому сенсі, що знаючи суми чисел у двох вхідних файлах ми не можемо визначити суму чисел у вихідному файлі. З різницею чисел у файлі все краще: перша програма не змінює різницю ((X+1)-(Y +1) =XY), друга -ділить її на 2
(X/2-Y/2 = (XY) / 2) , а третя - складає різниці (XZ = (XY) + (YZ)). Що ж не змінюється при всіх цих перетвореннях - так відразу і не збагнеш ...
Поставимо ескперімент (так, математика - наука експериментальна!).
Вихідний файл (5, 19) можна пропустити тільки через першу програму і отримати файл (6, 20). З нього можна далі робити послідовність (7, 21), (8, 22) і т.д., а можна запустити другу програму і отримати файл (3, 10). З нього можна зробити послідовність (4, 11), (5, 12) ... (19, 26). Потім можна запустити третю програму на (5, 19) і (19, 26) і отримати файл (5, 26) ...
Порахуємо різниці: 5-19 = -14 = 6-20 = 7-21 = 8-22 = ...; 3-10 = -7 = 4-11 = 5-12 = ... = 19-26; 5-26 = -21. Що ж спільного у чисел -14, -7, -21? Звичайно, вони всі на 7 діляться. От нехай ця подільність і буде інваріантом.
Дійсно, коли різниця не змінюється, то й подільність збережеться; коли різниця ділиться на 2, то подільність на 7 не зникне (2 і 7 взаємно прості); а коли різниці, що діляться на 7, складаються, то сума теж ділиться на 7.Зрозуміло, що, маючи на початку файл з різницю чисел, що ділиться на 7, ми тільки такі різниці і будемо отримувати. Але різниця 1-2004 = -2003 на 7 не ділиться, і такий файл ми отримати не зможемо.
Вправа 1.2. Доведіть, що тут можна отримати всі ті і тільки ті файли, де перше число менше другого, а їх різниця ділиться на 7.
Глибокий сенс тут у чому: інваріант може залежати не тільки від правил, за якими проводяться перетворення, але і від початкових даних. Як тут: значення різниці за модулем 7, взагалі кажучи - не інваріант при вироблених перетвореннях. Але при конкретних початкових умовах, коли це значення з самого початку дорівнює 0 - тоді воно стає інваріантом.
Безумовно, якщо типові інваріанти (сума, добуток, різниці та їх значення за якимось,зразу помітним, модулем) не підходять, то корисно поставити експеримент: проробити кілька перетворень і пошукати деякі закономірності в тому, що при цьому буде виходити.
Виділення зазначеної частини. Нерідко допомагає інваріант, який приймають за характеристику не всього об'єкта, а тільки його окремої частини. Придумується вона щоразу по своєму. Якась загальна логіка: ця частина повинна бути регулярною за своїм устроєм і містити всі нерегулярності для початкового або кінцевого стану. Взагалі, може підійти всяка частина, на якій перетворення загального вигляду буде виглядати більш просто.
Задача 1.5. На дошці 3x5 всі клітини білі, а один кут чорний. За хід можна поміняти колір всіх клітин в одному рядку або стовпці. Чи можна всі клітини зробити білими?
Розв’язання: Парність числа чорних клітин на всій дошці, на жаль, змінюється дуже часто, а тому нам не допоможе. Де б знайти таку частину дошки, на якій ця парність незмінна? У нас тут в умові нерегулярність в кутку - так візьмемо 4 кута. При операції перефарбування змінює колір рівно два кути, або жоден - тобто парність числа чорних кутів - інваріант. Але на початку такий кут один, а наприкінці хочеться нуль - не можна.
Задача 1.6. На колі стоїть 12 точок, в одній написано -1, в інших +1. Можна змінити знак у трьох одиниць підряд. Чи можна здвинути єдину -1 до сусідньої вершину?
Розв’язання: Нехай, для визначеності, ми зрушили -1 до сусідньої проти годинникової стрілки вершину (інакше можна всю картинку дзеркально відобразити і отримати саме таку). Давайте занумеруем вершини, починаючи з вихідної -1, вже за годинниковою стрілкою (тоді те місце, куди зрушила -1 - це вершина 12). Давайте виділимо таку частину (безліч вершин), де є перша вершина, немає 12-й, а парність кількості-1 - інваріант (тоді ця кількість в даній частині треба буде змінити з 1 до 0, а це неможливо з- за парності).
Інваріант і розмальовки дощок у клітинку. Дуже важливий клас задач на інваріант - якісь перетворення на кліткових дошках. Або ми ходимо чим-небудь по дошці, або заставляємо дошку фігурами. У будь-якому разі, дуже корисною може бути розмальовка дошки в два або більше кольорів, що володіє якимись особливими властивостями. Найбільш поширені розмальовки:
- Шахова (два кольори чергуються так, що будь-які дві сусідні по стороні клітини - різних кольорів);
- "матрас" (чередування строк, викрашенних у два кольори - або стовбців);
- "Матрац" (чергування рядків, пофарбованих у два кольори - або стовпців);
- Збільшена шахова (у шаховому порядку фарбуються не окремі клітини, а цілі блоки 2x2, 3x3 і т.д.);
- Збільшений"матрац" (чергуються не рядки, а однакові по товщині блоки з рядків);
- "Матрац" в N кольорів: чергуються рядки, пофарбовані у кольори, 1-й, 2-й, ... N-й, 1-й, 2-й і т.д.
- Шахова в N кольорів - легше показати, ніж написати; приклад для 3-х кольорів; можна і по-іншому, щоб одноколірні діагоналі були нахилені в інший бік.
Звичайний інваріант - колір клітин, по яких ми ходимо (або якесь чергування кольорів, або якісь кольору, на які ми ніколи не потрапляємо ...), або кількості клітин тих і інших кольорів на всій дошці і в фігурах замощення (якщо не збігаються, то замостити не можна
Задача 1.7. Доведіть, що шахову дошку не можна замостити 15-тима прямоугольничками 1x4 і однієї фігуркою виду .
Розв’язання: Шахова розмальовка тут не допоможе. Вона, так скажемо, не відрізняє особливу фігурку від прямокутничка: і в ній і в них рівно 2 білих і 2 чорних клітини. І ніщо не суперечить тому, що дошку можна замостити 16-ю фігурами з такою властивістю. Спробуємо іншу розмальовку, скажімо, "матрац". Тоді в прямокутнички 1x4 чи то 0, то 2, чи то 4 чорні клітини (дивлячись як він лежить). А в особливій фігурці - чи то 1, чи то 3. Коротше, там-парне, тут - непарне. А сума 15 парних чисел і одного непарного непарна і не може тому бути дорівнює 32 (числу чорних клітин на шаховій дошці).
Власне, інваріантом тут можна назвати парність кількості чорних клітин. Тільки ми тут не перетворимо об'єкт або набір об'єктів, а складаємо один об'єкт (дошку) з інших.
Задача 1.8. Фішка ходить по дошці NxN, зрушуючи на 1 клітину вгору, вправо або вниз-вліво по діагоналі. Чи може фішка обійти всі клітини дошки по разу і закінчити шлях зверху від початкової клітини.
Розв'язання : Підберемо розмальовку, при якій фішка буде однаково міняти колір при будь-якому ході. Просто шахова і "матрац" не підійдуть. А зате шахова розмальовка в 3 кольори - просто чудово Наша фішка буде ходити з червоного на жовтий, з жовтого на зелений, з зеленого на червоний і т.д. Нехай, скажімо, початкова клітина червона - тоді кінцева буде жовта. Кольори чергуються по циклу довжини 3, тому число ходів: 3k +1 (тобто = 1 по mod 3). Але те ж число ходів на дошці NxN одно N2 -1. Звідси N 2 = 2 (mod 3), чого, з міркувань теорії чисел не буває. Відповідь "не можна".
(!) Інваріант інваріантом, але і про інші галузі математики по ходу справи не треба забувати. Часто рішення може прийти саме звідти.
Треба акуратно підходите до завдань про різні процеси з питанням "чи можна". Так, більша частина з них - з відповіддю "не можна", який доводиться через інваріант. Але трапляються іноді завдання з відповіддю "можна", де треба будувати приклад. Іноді, захопившись пошуком інваріанта, можна не помітити існування простого прикладу.
1.2. Ігри
Задачі про ігри - вельми популярний вид олімпіадних завдань, особливо в молодших класах. Найбільш загальна проблема у початківців - зрозуміти, "що взагалі від нас хочуть", які міркування є правильним рішенням завдання, а які - ні.
Звичайно передбачається що грають двоє, роблячи ходи по черзі (пропускати свій хід не можна!), А в задачі запитують "хто виграє при правильній грі?" Стандартна помилка по суті - розуміти слова "при правильній грі" так, як ніби обидва супротивники грають оптимальним для себе чином (тим більше, що розв’язуючий задачу часто неправильно розуміє, що таке "оптимальним чином"!). Тоді придумується виграшна стратегія, яка дає відповідь тільки на оптимальний хід супротивника (зазвичай ще "оптимальним" вважається такий хід, коли супротивник слід придуманої нами ж стратегії - хоча для іншого гравця така стратегія може бути, навпаки, зовсім нікчемною!). Насправді, треба вміти придумувати відповідь на будь-який хід противника, яким би ідіотським він нам не здавався. Зазвичай правильна стратегія, на відміну від неправильної, не має випадків різної складності, а з однаковою легкістю знаходить гідну відповідь на будь-який хід!
Ігри-жарти. Найперший і простий клас ігор - ігри-жарти, в яких, насправді, немає ніякої стратегії (а нас хочуть обдурити, що вона нібито є!). Просто як би хто не ходив, або завжди виграє перший гравець (той, хто починає гру), або завжди другий. Задача - в тому, щоб математично довести таку закономірність (а помітити її можна, зігравши самому з собою рази 3-4). Для доказу зазвичай знаходиться якась величина, яка зрозуміло чому дорівнює на початку і кінці і зрозуміло як змінюється на кожному ходу - тут навіть часто число ходів до кінця однозначно порахувати можна. Або якийсь інваріант (тобто щось, що не міняють ні за якого ходу), однозначно залежить від початкової позиції (найчастіше - від парності) і визначальний вигравшого у кінці.
Задача 2.1. Двоє по черзі ламають шоколадку 5x8. За хід можна розламати будь-який шматок по прямій лінії між часточками. Програє той, хто не може зробити хід (І це стандартна умова, що ми її будемо мати на увазі, якщо не сказано протилежне. Питання "хто виграє при правильній грі?")
Розв'язання: Що значить, що гра закінчилася? Звичайно, що шоколадка вже вся розламані на окремі часточки. Часточок завжди буде 5x8 = 40 штук, а шоколадка на початку була одна. Зауважимо, що на кожному ходу один шматок шоколадки завжди розламується на 2, тобто кількість різних шматків шоколадки збільшується на 1. На початку ця кількість дорівнює 1, а в кінці, як ми помітили, 40. Значить, гра тривала рівно 39 ходів ("ходом" ми називаємо хід одного гравця, а не пару "хід - хід"). Тому останній (39-й) хід був обов'язково ходом першого (його ходи - перший, третій і всі з непарними номерами) - і перший виграв.
Ось такий вийшов жарт - як не ходи, перший завжди виграє.
Задача 2.2. На дошці написані 10 нулів і 10 одиниць. За хід можна стерти дві будь-які цифри і написати замість них 0, якщо вони були однакові або 1, якщо вони були різні. Якщо на дошці залишається 1 - виграє перший. Якщо 0 - другий.
Розв'язання : Ну, оскільки число цифр з кожним ходом зменшується рівно на 1 (2 стираємо, одну пишемо), а на початку їх 20 і в кінці повинна залишитися одна, то гра буде продовжуватися рівно 19 ходів. Останнім ходом буде хід першого , тільки в цьому завданні не факт, що перший тоді виграє.
Виграш залежить від парності останнього числа, звернемо на це увагу. Такий стандартний інваріант, як парність суми всіх чисел, не змінюється при ходах. Дійсно, сума двох однакових цифр - парна і, віднімаючи її, ми додаємо парний нуль. А сума двох різних цифр - непарна (0 +1 = 1), і ми додаємо замість неї непарну одиницю. Початкова сума всіх чисел парна, тому що серед них парне число непарних – одиниць, тому і в кінці буде парна. А це означає, що останнє число, що залишилося в кінці гри, буде парне, тобто воно буде нулем - і виграє другий.
Заодно ми переконалися, що не в будь-якій грі той, хто робить останній хід, виграє: можна змусити (як воно тут і відбувається) суперника зробити хід, після якого він програє.
Ідея "ідіотських ходів":
Задача 2.3. На дошці 10x12 можна за хід викреслити одну лінію (горизонталь або вертикаль, тобто рядок або стовпець) якщо в ній ще є одна невикреслена клітина.
Розв’язання : (Так, програє той, хто не може зробити хід - якщо хто не зрозумів.) Давайте злегка переформулюємо задачу інакше: нехай лінія не викреслюється, а вирізається з дошки зі склеюванням країв розрізу. Тоді правило зміниться на - "можна вирізати будь-яку існуючу лінію" і гра закінчується, коли від дошки нічого не залишається.
Нехай раптом після свого ходу залишили, скажімо, дошку з одним рядком. Звичайно, своїм ходом суперник може вирізати цей рядок - і ми програємо. Тому такий хід був «ідіотським» - давайте так його і називати. Подивимося, коли не можна буде не зробити «ідіотського» ходу. Якщо дошка 1xN (або Nx1) - то такий хід уже зробив супротивник. Якщо ширина і висота дошки не менше 2, а більша з них - не менше 3 - то виріжемо лінію поперек більшої розмірності - і залишиться дошка хоча б 2x2. А от якщо перед ходом дошка - 2x2, то хід обов'язково буде «ідіотський». Ясно, що виграє той, хто залишить противнику дошку 2x2. На кожному ходу висота або ширина дошки зменшується на 1 (тобто, їх сума зменшується на 1). Початково ця сума дорівнює 10 +12 = 22, в кінці повинна стати 2 +2 = 4. Різниця 22-4 = 18 - парне число ходів, тому дошка 2x2 залишиться після ходу другого - і другий виграє (як у звичайній грі-жарті!).[42]
Строго кажучи: стратегія другого - грати як завгодно, тільки не роблячи «ідіотських» ходів. Якщо перший десь зробить «ідіотський» хід (а це формально заважає загнати його на дошку 2x2) - наступним ходом виграємо. Якщо ніхто не зробить «ідіотського» ходу - то після 18 ходів у першого буде дошка 2x2 - і тут він все одно зробить «ідіотський» хід.
Симетрія. Це потужний красивим, але дуже простий методом розв’язання ігрових завдань - симетрична стратегія. Суть його - робити щоразу хід, симетричний ходу супротивника або доповнює його до чого-небудь. Доказ правильності нашої стратегії буде користуватися тим, що після кожного нашого ходу позиція симетрична: раз так, то якщо противник зумів зробити свій хід, то і ми зможемо зробити хід, симетричний йому. Неправильно думати що симетрія - стратегія тільки для другого гравця. Якщо вихідна позиція - несиметрична, то зазвичай перший гравець може її якось зробити симетричною, а потім грати по симетрії, відповідаючи на ходи другого.
Задача 2.4 . Двоє по черзі кладуть п'ятаки на круглий стіл так, щоб вони не накладалися один на одного. (Програє, як звичайно, той, хто не може зробити хід.)
Розв’язання : Як би так першому гравцеві зробити свій хід, куди можна покласти п'ятак на порожньому круглому столі? А давайте його в центр покладемо! Увага: після такого ходу розташування п'ятаків на столі стало центрально симетричним Тепер давайте відповідати на кожен п'ятак другого гравця центрально симетричним йому п'ятаком. Чому ж стратегія ніколи не підводить (і ми не програємо)? Крах стратегії означає ,що другий поклав кудись п'ятак, а ми не змогли покласти п'ятак в симетричне місце (там вже щось лежить). Після нашого попереднього ходу позиція була симетричною (з симетричності не тільки зроблених ходів, а й самого столу), а місце, куди другий поклав п'ятак було вільне. Центрально симетричне йому місце, куди ми хочемо покласти свій п'ятак, теж було вільно. Але не міг же другий зайняти це місце своїм п'ятаком (це теж важливо відмітити, не у всіх задачах так буде!). Значить, не може бути так, щоб нам не було куди покласти свій п'ятак. Перший виграє.
Задача 2.5. Двоє по черзі ставлять слонів в клітини шахової дошки так, щоб вони не били один одного (колір слонів значення не має).
Розв’язання : Ну тут, здавалося б, без фокусів. Дошка має розмір 8x8, і ніяка клітина центром симетрії не буде. Тому другий може завжди відповідати на ходи першого симетричними ходами і виграє. АЛЕ: Нехай перший гравець поставив слона на діагональ дошки. Якщо другий гравець ставить свого слона в центрально симетричну клітку, то він опиниться на тій же діагоналі ... якраз під боєм слона, поставленого першим гравцем! Дійсно, буває так, що черговому симетричному ходу заважає хід, щойно зроблений супротивником (тому треба уважно стежити за такими ситуаціями!).
Вихід з положення - застосувати симетрію не центральну, а осьову (відносно середньої лінії дошки). Неважко переконатися, що клітку, симетричну своєї позиції щодо осі, слон ніколи не б'є. Після кожного ходу другого вся позиція симетрична, в т.ч. розташування не б'ющихся полів; хід першого теж не ставить під бій поле, симетричне тому, куди він був зроблений. Тому симетричне поле не б'ється. Другий завжди може зробити хід і виграє.
Задача 2.6. Є дві купки каміння, по 17 у кожній. За хід можна взяти кілька каменів, з однієї купки.
Розв’язання : І це теж симетрія! Виграє другий - він бере з іншої купки стільки каменів, скільки перший взяв з однієї. При цьому після кожного ходу другого каменів в обох купках буде порівну - тому стратегію можна продовжувати.
А якби купки були нерівні, то виграв би перший. Першим ходом він взяв би з більшою купки стільки каменів, щоб зрівняти її з меншою, а далі користувався б стратегією симетрії. [24]
Насправді, нерідке явище: в залежності від вихідних даних одна і та ж стратегія приносить успіх то першому, то другому гравцеві.
Аналіз виграшних позицій.
Безперечно, самий потужний і універсальний спосіб розв’язання задачі -гри - пошук виграшних позицій. Тут називається виграшною та позицію, яку вигідно залишати після свого ходу, а програшною, відповідно, ту, яку невигідно (у згоді з однією половиною методичної літератури і на противагу іншій половині ) Тоді фінальна позиція, з якої вже не можна зробити хід - виграшна. Основні властивості позицій такі:
1.) Кожна позиція - або виграшна, або програшна (проміжних варіантів немає!);
2.) З виграшної позиції можна піти тільки на програшну;
3.) З будь-якої програшної позиції можна піти на виграшну.
Тоді, якщо початкова позиція - програшна, виграє перший, якщо виграшна - другий. Стратегія однакова: кожен раз ходити на виграшну позицію. Тоді суперник повинен буде походити на програшну позицію (властивість 2), а ми знову зможемо піти на виграшну (властивість 3).
Задача 2.7. "Хрома тура" може ходити по прямій вправо або вгору. Початково вона стоїть в нижньому лівому кутку дошки. Грають двоє. Виграє той, хто поставить туру у верхній правий кут.
Розв’язання : Початково тура стоїть на головній (в даному випадку) діагоналі дошки. Перший гравець своїм ходом веде її з діагоналі в бік. Тоді другий гравець може повернути туру назад на діагональ. Потім перший знову зрушить її з діагоналі (ходів з головної діагоналі на неї ж немає), а другий знову зможе повернути і т.д. Так як клітка призначення лежить на головній діагоналі, то на ній тура обов'язково виявиться після ходу другого - і другий виграє. [23]
Читаємо між рядків: "безліч виграшних позицій - це головна діагональ".
Аналіз з кінця: як же шукати виграшні позиції, якщо вгадати їх не вдалося? Можна просто послідовно розібрати всі позиції, починаючи з останньої (бажано, для зручності, щоб безліч позицій вміщувалося на двовимірної дошці або таблиці). Фінальна позиція виграшна. Тому всі, з яких на неї можна піти - програшні. Тепер повинні утворитися позиції, з яких можна піти тільки на програшні - вони будуть виграшними. Всі позиції, з яких можна піти на якусь із цих виграшних - програшні і т.д., поки не дійдемо до початкової позиції.
1.3. Комбінаторика
Комбінаторика - це математична наука, грубо кажучи, про підрахунок числа способів зробити що-небудь. Незважаючи на вузькість предмета вивчення, наука ця вельми глибока. Крім того, в олімпіадних задачах комбінаторика використовується настільки часто, що її знання абсолютно необхідно кожному математику-олімпіаднику.
Хоча багато комбінаторних задач здаються очевидними, але багато школярів, особливо початківці, плутаються в них, приймаючи задачу одного типу за іншу. Уникнути плутанини в голові можна саме систематичним вивченням теорії.
Основні комбінаторні формули і міркування:
1.Адитивність взаємовиключних випадків. Якщо у задачі з комбінаторики є декілька взаємовиключних випадків/варіантів вибору, загальна кількість способів дорівнює сумі кількостей способів в кожному з цих випадків.
2.Мультипликативність незалежних випадків. Якщо спосіб (кількість яких треба порахувати) повністю визначається декількома незалежними один від одного етапами вибору (на кожному етапі вибір варіантів - взаємовиключний!), То загальне число способів дорівнює добутку кількостей варіантів вибору на кожному етапі.
Доведення Нехай всього є k етапів. Позначимо кількість варіантів вибору на першому етапі - n1, на другому етапі - n2, на останньому - nk. На першому етапі у нас є n1 варіантів вибору, тобто утворюється n1 випадків. На другому етапі в кожному з цих випадків ми може вибрати будь який з n2 варіантів, утворивши n2 подвипадків. Таким чином, після двох етапів буде вже n1* n2 випадків. На третьому етапі в кожному з них ми можемо вибрати будь-який з n3 варіантів і після трьох етапів буде n1 * n2 * n3 випадків. Продовжуючи цей процес, ми отримуємо після всіх етапів n1 * n2 * ... * nk випадків - і це будуть вже остаточні способи. Їх кількість якраз дорівнює добутку кількостей варіантів вибору.
Знову ж, у розв’язанні задач цю властивість можна навіть не формулювати якщо впевнені, що застосували його в правильній ситуації.[9]
Насправді, доводячи п.2, ми користуємося твердженням п.1. Наприклад, як докладніше пояснити, чому після двох етапів є n1*n2 випадків? У нас є взаємовиключні випадки - варіанти вибору на першому етапі, яких n1 штук. У кожному з них є n2 способів зробити вибір на двох етапах (на першому етапі варіант вже відомий, залишилося вибрати n2 варіантів на другому етапі). А щоб знайти загальне число способів зробити вибір на перших двох етапах, треба (відповідно до п.1) скласти n1 чисел, рівних n2, тобто помножити n1 на n2.
3.Загальне правило мультипликативности подвипадків. Якщо спосіб повністю визначається декількома, можливо залежними один від одного, етапами вибору, але кількість варіантів вибору на кожному етапі не залежить від того, як був зроблений вибір на попередніх етапах, то загальне число способів дорівнює добутку кількостей варіантів вибору на кожному етапі.
Доведення: Нічим не відрізняється від доведення попередньго, тому що там користувалися незалежністю від попередніх етапів вибору тільки кількость варіантів на даному етапі.
Дуже поширеною помилкою є переплутування області застосування п.1 та п.2, аж до повного нерозуміння, де і чому треба складати варіанти, а де - множити. Тому тут же проілюструємо їх відмінність на прикладах.
Приклади:
Задача 3.1. З міста А в місто Б веде 6 доріг, з міста Б у місто В - 4 дороги, і більше ніяких доріг з цих міст не виходить. Скількома шляхами можна проїхати з міста А в місто В?
Розв’язання : На першому етапі нам треба вибрати дорогу, по якій ми поїдемо з А в Б, і тут у нас є 6 варіантів. На другому етапі треба вибрати дорогу, по якій ми поїдемо з Б в В, і там у нас 4 варіанти. Ці два етапи повністю визначають шлях проїзду. Вибір незалежний, тому що по якій би дорозі ми не поїхали в Б, ми зможемо потім поїхати в В за кожної з доріг. Таким чином, ми маємо справу з незалежними етапами вибору, і повинні перемножать варіанти. Всього отримуємо 6 * 4 = 24 різних шляху.
Задача 3.2. З глухого глухого міста Г, де зроду не було ніяких доріг, проклали 2 нові дороги в місто В з попередньої задачі. Крім того, з міста А з попередньої задачі в місто Г проклали ще 2 нові дороги. Скількома шляхами тепер можна проїхати з міста А в місто В?[47]
Розв’язання : У цій задачі треба на самому початку виділити два взаємовиключних випадку: коли ми їдемо через місто Б, і коли їдемо через місто Г. Знайти кількість шляхів у першому випадку - це в точності завдання 1, і відповідь буде 6 * 4 = 24 ( по п.2). Знайти кількість шляхів у другому випадку - це завдання, аналогічна завданню 1, але з відповіддю 2 * 2 = 4. Тепер, за п.1, ці кількості шляхів треба скласти, і у відповіді виходить 24 +4 = 28 шляхів проїзду.
Тепер займемося такими видами задач, де треба вибирати якісь предмети або елементи множин (для стандартизації, скажімо, що нам треба з n елементів вибрати k):
4. Вибір з повтореннями, з урахуванням порядку (заповнення позицій елементами множини).
Загальна задача може формулюватися так: "Є алфавіт з n букв. Скільки в цьому алфавіті" слів "які складаються з k літер?" Відповідь буде -nk.
Доведення 1 : У нас є n способів вибрати першу літеру, n способів вибрати другу літеру ... n способів вибрати k-у букву. Всього має k етапів вибору, по n варіантів на кожному. При цьому вибір незалежний (які б не були перші кілька букв, ми можемо вибрати будь-яку наступну). Тому, можна застосувати п.2 і отримати відповідь nk.
Доведення 2: (Тут покажемо, як можна не ссилатися на затвердження п.2, а відтворити його доведення прямо в розв’язанні.) У нас є n способів написати першу букву (це дає n випадків). У кожному з них ми можемо n способами приписати до першої букви другу і отримати n двобуквений слів (утворюється n подвипадків). Всього буде n * n = n2 способів написати перші дві букви. У кожному з цих n2 випадків ми можемо n способами приписати в перших двох буквах третю і отримати n трибуквених слів (знову утворюється n подсвипадків). Всього буде n2 * n = n3 способів написати перші 3 літери. І так далі, поки ми не напишемо все слово - тут число способів буде n в степені, що дорівнює довжині слова, тобто nk.
5. Вибір без повторень, з урахуванням порядку (розкладка в ряд).
Загальна задача може формулюватися так: "Є купа з n різних предметів. Ми послідовно беремо з них k предметів і ставимо в ряд. Скільки є різних способів заповнення ряду?" Число у відповіді має своє спеціальне позначення: Ank і обчислюється за формулою
An k = n * (n-1) * (n-2) * ... * (n-k +1) або Ank = n!/(n-k)! (друга формула виходить при множенні і діленні першою на (n-k)!)
Доведення: У нас є n способів вибрати (взяти і поставити в ряд) перший предмет (назвемо це першим етапом вибору). Далі у нас є, незалежно від того, як обраний перший предмет, n-1 способів взяти другий предмет - в будь-якому випадку, це може бути який завгодно предмет, крім першого обраного. Потім є n-2 способи взяти третій предмет - він може бути який завгодно, крім перших двох обраних и так далі. Звернемо увагу, що число способів вибрати останній, k-й предмет - не n-k, а n-k +1 = n-(k-1), тому що їм може бути будь-який, крім перших k-1 обраних. Разом, ми має k етапів вибору, на кожному з яких число варіантів одно (незалежно від того, як зроблено вибір на попередніх етапах), відповідно, n, n-1 ... n-k +1. Тому, відповідно до п.2 ', ми отримуємо загальне число способів вибору k предметів n*(n-1)* ... * (n-k +1).
Вправи: Придумати доказ з повною підстановкою міркування з п.2, тобто схоже на док-во № 2 попереднього пункту.
6. Перестановки n предметів.
Мається n різних предметів. Скільки у нас способів виставити їх усі в ряд?
Зазвичай це завдання розглядають як окрему і повторюють окремо всі комбинаторні міркування (як в дов-нні 2 п.4). Але зауважимо, що це завдання - окремий випадок п.5 при k = n. Тому відповідь буде Ann = n!
7. Вибір без повторень, без урахування порядку (число сполучень).
Загальна задача може формулюватися так: "Є купа з n різних предметів. Ми беремо з них k предметів і кидаємо в мішок. Скільки є різних способів заповнення мішка?" Число у відповіді має своє спеціальне позначення: Cnk і обчислюється за Сnk=Ank/k! або Cnk=(n*(n-1)*(n-2)*...*(n-k+1))/k! або Cnk=n!/(k!*(n-k)!) (друга і третя формули виходять при підстановці в першу формулу формул для Ank) .[2]
Доведення : Досить довести тільки першу формулу. Нехай ми спочатку вибираємо k предметів послідовно і ставимо в ряд, а потім закидаємо цей ряд у мішок. Число можливих рядів і є An k. Доведемо, що заповнень мішка рівно в k! разів менше, ніж різних рядів - тоді формула буде доведена. (Зауважимо, що один і той же ряд не може переходити в два різних заповнення мішка!) Тепер обгорнемо процес закидання ряду в мішок: нехай у мішку лежать якісь k предметів, а ми дістаємо їх і ставимо в ряд. Згідно п.6, у нас для кожного заповнення мішка буде рівно k! різних рядів. Крім того, за нашим зауваженням, з двох різних заповнень мішка не можна отримати один і той же ряд. Тому рядів рівно в k! разів більше, ніж заповнення мішка.
Взагалі кажучи, Cnk = Cnn-k для будь-якого n> = 0 і 0 <= k <= n.
Приклади застосування пп.4-7:
Задача 3.3. Скільки існує 6-цифрових чисел, в запису яких є хоча б одна парна цифра?
Розв’язання : Розбирати випадки, скільки парних цифр і на яких місцях стоїть у нашому числі - занадто довго і противно. Скористаємося хитрим прийомом: порахувати те, що нам не потрібно. Тобто, вважати будемо числа з одних непарних цифр. Непарні цифри - це "алфавіт" з 5 "букв", а 6-значне число - "слово" з 6 "букв" цього "алфавіту". Таких слів-чисел, згідно п.4, буде рівно 56 штук. А чисел, які нас цікавлять (це всі інші) - рівно 900000-56 = 900000-15625 = 984375 (всього 6-значних чисел 900000).
Задача 3.4. За Конституцією, прапор країни складається з трьох однакових горизонтальних смуг трьох різних кольорів, причому на прапорі можуть бути тільки білий, червоний, жовтий, зелений, блакитний і чорний кольори. Скільки різних прапорів дозволяє така Конституція?
Розв’язання : Ми маємо справу з вибором 3-х з 6. Вибір відбувається без повторень (кольори повинні бути різні) і з урахуванням порядку (важливо, який колір вгорі, який внизу і який в середині). Згідно п.5, відповіддю буде число A63 = 6 * 5 * 4 = 120.
Задача 3.5. Один професор математики написав 6 книг, інший - 8. Кожен з хоче подарувати іншому 3 свої книги з автографом. Скількома способами вони можуть обмінятися подарунками?
Розв’язання: Перший професор може вибрати для подарунка 3 книги зі своїх 6, а це можна зробити C63 = 20 способами (див. п.6). Другий професор може вибрати для подарунка 3 книги зі своїх 8, вже C83= 56 способами. Обидва вибори відбуваються незалежно і однозначно визначають спосіб обміну, тому варіанти потрібно перемножувати. Відповідь: C63*C83=56*20=1120 способів.
8. Перестановки предметів, серед яких є однакові. Ми розглянемо тут на прикладах один стандартний метод такого підрахунку. Загальний вигляд відповіді краще зрозуміти і запам'ятати не у вигляді формули, а у вигляді правила: "взяти факторіал кількості всіх предметів і поділити на факторіали розмірів всіх груп однакових предметів".
Приклади:
Задача 3.6. Скільки "слів" можна отримати, переставляючи букви в слові ЛІНІЯ?
Розв’язання: У цьому слові є 2 однакові літери (І). Будемо тимчасово вважати їх різними: І1 і І2. За п.6 отримуємо, що тепер можна скласти 5! = 120 слів. Насправді, це в кілька разів більше, ніж потрібно. У скільки ж саме? Зрозуміло, що слова, різняться тільки перестановкою літер І1 і І2 на тих же місцях (наприклад, ЛІ 1 ЯНІ 2 і ЧИ 2 ЯНІ 1), насправді однакові, хоча ми порахували їх як різні. Всього на одних і тих же місцях можна розставити букви І1 і І2 рівно 2! = 2-ма способами, отже, кожного разу ми замість одного слова отримуємо 2 різних. Значить, ми отримали 120:2 = 60 різних слів. [30]
"Цешка", трикутник Паскаля і Біном Ньютона:
У попередніх прикладах ми обчислювали числа Cnk безпосередньо за формулою, роблячи багато множень і ділень. Виявляється, є метод обчислювати відразу багато різних "цешок", використовуючи тільки додавання. Особливо важливо це при програмній реалізації, оскільки комп'ютер складає числа набагато швидше, ніж примножує і тим більше ділить. Cn +1 k +1 = Cnk + Cnk +1.
Побудуємо з чисел два нескінченних трикутник