Відповіді та вказівки до задач математичних олімпіад

1. Нехай а — одне із чисел 1, 2, …, p – 1. Обґрунтуйте, що не ділиться на а Тоді сума остач від ділення чисел і на дорівнює тобто сума остач від ділення чисел і і … на дорівнює Залишається визначити кіль-кість таких пар.

2. Доведення можна провести методом математичної індукції. Для можливості індуктивного переходу доведіть, що найбільший спільний дільник чисел дорівнює найбільшому спільному дільнику чисел тобто чисел

4. Доведіть, що: при n = 2k при n = 4k + 1 при n = 4k + 3

5. Припустимо, що при деякому існує трійка z, y, z натуральних чисел, для яких Не порушуючи загальності, можемо вважати, що Використовуючи формулу бінома Ньютона, матимемо:

Отже, Очевидно, що z > y. Для натуральних чисел y і z нерівність y < z < y + 1 неможлива.

6. Нехай числа x₀, y₀, z₀, u₀ задовольняють задане рівняння. Позначимо через а найбільше з чисел x₀, y₀, z₀. Тоді і звідки Отже, залишається розв’язати рівняння: x! + y! + z! = 1!; x! + y! + z! = 2!; x! + y! + z! = 3!. Перші два з них розв’язків не мають, а розв’язком третього є: x = y = z = 2. Таким чином, задане рівняння має один розв’язок: x = y = z = 2, u = 3.

7. Отже, число є цілим. Оскільки, крім цього, воно додатне, то

9. Обґрунтуйте, що A + B = (x + a)ⁿ, A – B = (x – a)ⁿ. Тоді A² – B² = (x² – a²)ⁿ.

10. Нехай Далі використайте розклад:

11. n кіл ділитимуть поверхню кулі на найбільшу кількість частин тоді, коли вони попарно перетинатимуться і жодні три з них не проходитимуть через одну точку. Якщо на поверхні кулі вже є k кіл і вони ділять її на певну кількість частин, то (k + 1)-е коло повинно перетнути дані k кіл у 2k точках. Ці точки поділять саме це коло на 2k частин, кожна з яких поділить область, у якій вона знаходиться, на дві частини. Отже, після проведення (k + 1)-го кола кількість частин збільшиться на 2k. Тому n кіл поділять поверхню кулі на 2 + 2 + 4 + 6 + … +2(n – 1) частин.

12. У таблиці залишимо вільними останній рядок і останній стовпець, а решту клітинок заповнимо довільним чином числами +1 та –1. Це можна здійснити способами. Доведіть, що як би ми не розставляли дані числа, вільний n-й рядок та n-й стовпець можна однозначно заповнити числами +1 і –1 так, щоб в утвореній таблиці добутки чисел кожного рядка і кожного стовпця дорівнювали 1. Тому шуканих таблиць буде

Список рекомендованої літератури

1. Антипов И. М. и др. Избранные вопросы математики. Факультативний курс. 9 кл. — М.: Просвещение, 1979. – 192 с.

2. Виленкин Н . Я. Популярная комбинаторика. — М.: Наука, 1975. – 208 с.

3. Виленкин Н . Я. Комбинаторика. — М.; Наука, 1969. – 328 c.

4. Дополнительные главы по курсу математики 9 класса для факультативних занятий. Сост. Стратилатов П. В. — М.: Просвещение, 1970. – 144 с.

5. Єжов I. I. , Скороход А. В. , Ядренко М. Й. Елементи комбінаторики. — К.: Вища шк., 1972. – 84 с.

6. Завало С. Т. Арифметика, алгебра і елементи аналізу. — К.: Рад. шк., 1969. – 504 с.

7. Збірник задач з математики для вступників до втузів. За ред. М. І. Ска­наві. — К.: Вища шк., 1992. – 448 с.

8. Лейфура В. М. Математичні задачі евристичного характеру. — К.: Вища шк., 1992. – 92 с.

9. Маланюк М. П. , Лукавецький В. Г. Олімпіади юних математиків. — К.: Рад. шк., 1985. – 88 с.

10. Математика. Посібник для факультативних занять у 10 класі. За ред. І. Є. Шиманського. — К.: Рад. шк., 1970. – 196 с.

11. Олимпиады: Алгебра. Комбинаторика. Под ред. Л. Я. Савельева. — Новосибирск: Наука, 1979. – 176 с.

12. Соминский И. C. , Головина Л. И. , Яглом И. М. О математической индукции. — М.: Наука, 1967. – 144 с.

ЗМІСТ

Передмова..................................................................................................................... 3

§ 1. Метод математичної індукції.................................................................. 8

§ 2. Прості задачі комбінаторного типу..................................................... 13

§ 3. Загальні правила комбінаторики......................................................... 17

§ 4. Основні поняття комбінаторики............................................................ 18

.. 4.1. Перестановки....................................................................................... 18

.. 4.2. Розміщення............................................................................................ 20

.. 4.3. Комбінації............................................................................................. 22

.. 4.4. Деякі комбінаторні тотожності....................................................... 23

§ 5. Сполуки з повторенням елементів........................................................ 25

.. 5.1. Перестановки з повтореннями........................................................ 26

.. 5.2. Розміщення з повтореннями............................................................. 27

.. 5.3. Комбінації з повтореннями.............................................................. 28

§ 6. Приклади розв’язування комбінаторних задач................................ 29

§ 7. Формула бінома Ньютона...................................................................... 32

Заключне зауваження............................................................................................. 36

Задачі для самостійного розв’язування............................................................. 37

Задачі для підготовки до математичних олімпіад.......................................... 42

Відповіді та вказівки до задач математичних олімпіад................................. 43

Список рекомендованої літератури.................................................................... 45

Навчальне видання

Мирон Петрович Маланюк,

Василь Ростиславович Кравчук

Метод математичної індукції

Та елементи комбінаторики

За редакцією В. О. Тадеєва

Обкладинка Михайла Окаринського

Видання 2-е, виправлене

Підписано до друку 18.11.2003. Формат 60х84/16. Папір офсетний.
Гарнітура Times. Друк офсетний. 2,79 ум. др. арк., 1,87 обл.-вид. арк.
Тираж 1000. Замовлення № 03-214
Редакція газети «Підручники і посібники». Свідоцтво ТР №189 від 10.01.96.
46020, м. Тернопіль, вул. Поліська, 6а. Тел.8-(0352)-43-15-15, 43-10-21, 43-10-31.
Факс: 8-(0352)-43-10-21. Електронна пошта: pp@pp.utel. net. ua

БІБЛІОТЕЧКА ЗАОЧНОЇ МАТЕМАТИЧНОЇ ШКОЛИ

Мирон Маланюк, Василь Кравчук