Програма спеціального курсу
«Прикладна математика»
для учнів 8-11 (9-12) класів
з поглибленим вивченням математики

Опубліковано у збірниках Міністерства освіти і науки:
  1. Програми факультативних курсів та курсів за вибором з математики для загальноосвітніх навчальних закладів. К., «Навчальна книга», 2002.

  2. Програми для загальноосвітніх навчальних закладів. Навчальні програми для профільного навчання. Програми факультативів, спецкурсів, пропедевтичних курсів, гуртків. Інформатика. Запоріжжя, Прем'єр, 2003, 303 с.

  3. Збірник програм з математики для до профільної підготовки та профільного навчання. Ч. І. Допрофільна підготовка. Київ, Ранок, 2011, С. 239–256.

Рецензенти:
В.Б.Распопов, доцент, кандидат технічних наук;
Л.А.Федорів, Заслужений учитель України.

Пояснювальна записка

Кількість навчальних годин
(за рахунок регіонального і шкільного компонентів навчального плану або надання додаткових платних освітніх послуг): по 2 години на тиждень, щороку — 68 годин, на весь курс — 272 години. При цьому учні повинні мати можливість додаткової самостійної роботи за комп'ютером протягом 2 годин на тиждень. Допускається перерозподіл навчальних годин між темами — до 20% часу на кожну тему. Програму можна використовувати з розрахунку 3 години на тиждень з пропорційним збільшенням годин на кожну тему і детальнішим розглядом задач — як поданих у програмі, так і підібраних з інших джерел.

Мета курсу: розвинути логічне мислення і зв'язне мовлення учнів, закріпити базові математичні поняття на рівні практичного використання до програмної реалізації включно. Після вивчення курсу:

учні повинні знати: учні повинні вміти:

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

Тема 1 «Алгоритмічна мова» вивчають оглядово і лише для того, щоб учні знали, як користуватися довідковими інформаційними системами і літературою під час опанування наступними темами. Вивчення математичного апарату тем курсу потрібно здійснювати на уроках математики, випереджаючи розгляд цих тем при вивченні даного курсу — курсу практичного використання і програмної реалізації базових понять елементарної математики.

Зміст

8 клас

1. Алгоритмічна мова (8 годин).
Абетка. Структура програми. Прості типи даних. Сталі. Арифметичні й логічні функції. Оператори. Порядок виконання дій. Умовні оператори. Цикли. Структуровані типи змінних. Динамічні структури даних. Процедури й функції. Введення і виведення даних. Робота з файлами. Примітивна графіка. Рекурсивні функції та процедури. Інтегроване середовище програмування .

2. Математична логіка (20 годин). Найпростіші булеві функції. Нормальна форма булевої функції. Дешифрація запису арифметичної дії з цілими числами. Сюжетні задачі з відомою наперед кількістю персонажів (подій).

3. Комбінаторика (40 годин). Впорядкування чисел. Перестановки, розташуванння і комбінації: обчислення кількості й перебір. Реалізація невідомої наперед кількості вкладених циклів однією групою операторів. Період підстановки. Рекурентні співвідношення. Найдовша спільна підпослідовність двох послідовностей.

9 клас

4. Цілі числа й кільце многочленів. Подільність (46 годин).
Ділення цілих чисел з остачею. Найбільший спільний дільник. Алгоритм Евкліда. Найменше спільне кратне. Решето Ератосфена. Розклад на прості множники. Кількість дільників натурального числа. Класи еквівалентності остач. Позиційна система числення. Перехід від однієї системи числення до іншої. База мішаної системи числення. Факторіали й числа Фібоначчі як база системи числення. Перехід від багатовимірного масиву до лінійного й навпаки. Арифметичні дії з раціональними й багатоцифровими натуральними числами. Рекурентні співвідношення й різні системи числення. Десятковий запис дробу. Ланцюгові дроби.

Многочлени однієї змінної. Ділення многочленів з остачею. Найбільший спільний дільник многочленів. Раціональні корені многочлена з цілими коефіцієнтами. Схема Ґорнера (в тому числі для многочленів з раціональними коефіцієнтами й аргументами). Сума k-их степенів перших n натуральних чисел як многочлен змінної n. Числа Бернулі.

5. Оптимізація перебору (14 годин).

Відновлення запису арифметичних дій з цілими числами. Сюжетні задачі логічного характеру з невідомою наперед кількістю персонажів.

6. Дійсні числа (8 годин). Подання дійсного числа в ЕОМ. Арифметичний корінь. Наближене розв'язування нелінійних рівнянь відносно однієї змінної поділом відрізка навпіл.

10 клас

7. Планіметрія (24 години).
Визначення кута за його тригонометричними функціями. Перехід до екранних координат. Рівняння прямої. Симетрія відносно точки і прямої. Площа трикутника і многокутника. Взаємне розташування точки і трикутника, точки і многокутника (порівняння різних методів: кратність кількості перетинів, кут обертання радіус-вектора, обчислення площ). Обхід опуклого многокутника за периметром. Система лінійних невироджених рівнянь двох змінних. Сукупність прямокутників, сторони яких паралельні осям координат: площа і периметр об'єднання, перетину. Класифікація точок опуклого многокутника.

8. Стереометрія (24 години). Координатний простір. Рівняння площини і прямої. Кути мiж площинами, мiж прямими, мiж прямою та площиною. Паралельна й центральна проекції. Рух геометричних тіл. Векторний і мішаний добуток. Системи лінійних невироджених рівнянь трьох змінних. Модель многоґранника для побудови перерізу площиною. Відстань на поверхні многоґранника (на прикладі куба). Класифікація точок опуклого многоґранника. Розбиття опуклого многоґранника на трикутні піраміди без спільних внутрішніх точок.

9. Методи оптимізації (20 годин). Поняття про лінійне й опукле програмування функцій однієї і двох змінних, cимплекс-метод. Метод динамічного програмування для скінченного простору станів (оптимальне розміщення капіталу і придбання наборів товарів). Задача комівояжера.

11 клас

10. Графи (36 годин).
Вершина, ребро і дуга графа. Зв'язність. Матриця суміжності, її незвідність. Кількість маршрутів. Найкоротший шлях. Модель лабіринту. Вершини графа, які неможливо уникнути на шляху між даними вершинами. Розбиття графа на компоненти. Граф як модель многоґранника для побудови й аналізу розгорток.

11. Теорія ігор (32 години). Скінченні ігри з антагоністичними інтересами і повною інформацією. Поняття стратегії. Аналіз графа гри «з кінця». Класифікація позицій гри. «Симетричні» стратегії. Ізоморфізм ігор. Перехід від неперервного простору станів до дискретного. Тлумачення парадоксу гри «стоніжка».

Задачі

Математична логіка
  1. З'ясувати, яка з двох дат передує іншій.

  2. Розв'язати рівняння:
    а) ax + b = 0;
    б) a/x + b = 0;
    в) ax2 + bx + c = 0 .

  3. З'ясувати, чи прямокутний паралелепіпед з ребрами a, b, c має ґрань, що: а) містить квадрат; б) міститься у квадраті зі стороною d.

  4. Знайти взаємне розташування відрізків [a; b] і [c; d] на числовій прямій..

  5. Чи існує трикутник з даною ґрадусною мірою двох внутрішніх кутів? Визначити його вид..

  6. Чи існує трикутник з даними квадратами довжин сторін? Визначити його вид..

  7. Чи існує 4-кутник з даними довжинами сторін. Чи може він бути паралелограмом?

  8. Скільки різних трикутників (взагалі і з точністю до рухів площини) можна утворити з відрізків даної довжини (з вилученням і без вилучення останніх відповідно).

  9. Визначити тип впорядкованості даної послідовності чисел.

  10. Підрахувати ціну телеграми за її текстом. Числівники записати словами.

  11. Роздрукувати текст з файлу без переносів, без «рваного краю» та не більше 60 символів у рядку.

  12. Впорядкувати за частотою вживання сполучення з 1, 2 та 3 символів, які зустрічаються у даному тексті.

  13. Записати дане число n порядковим числівником у вказаному роді й відмінку, n < 109.

  14. Здійснити транслітерацію, (подання літер та їх сполучень відповідними літерами та сполученнями) з української абетки латиницею і навпаки.

  15. Знайти найменше та найбільше числа, які можна подати сумами (можливо, і всіх) елементів даного масиву.

  16. З'ясувати кінцевий стан термостату, який містить лід і розплавлений свинець.

  17. Вгадайте натуральне число, яке не перевищує n, задавши якнайменше запитань, відповідь на які «Так» або «Ні». Використати поділ відрізків числової прямо навпіл (тут і далі курсивом подано рекомендації щодо розв'язування задач).

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

  19. Серед 81 однакової на вигляд монет одна фальшива (вона легша). Як за допомогою 4-разового використання шалькових терезів без гир знайти фальшиву монету? Використати поділ на 3 групи з однаковою кількістю монет за 4 зважування.

  20. Є 27 рівних кубів одного кольору. 26 з них мають однакову вагу. Як за допомогою найменшої можливої кількості зважувань на терезах без гир відокремити куб, вага якого відрізняється від ваги інших, і дізнатися, важчий він чи легший від інших кубів? Використавши поділ на 3 рівні групи, за 4 зважування.

  21. Серед шести кубів однакового розміру і однакового кольору три мають однакову вагу, і важчі від решти кубів, які також мають однакову вагу. Скільки зважувань на шалькових терезах без гир треба здійснити, щоб відокремити важчі куби? 3важування за схемою: a + b > c + d, e ? f, c ? d або a + b = c+ d, e > f, a + c ? d + f.

  22. Комбінаторика
  23. Впорядкувати українські слова в алфавітному порядку.

  24. Впорядкувати за частотою вживання сполучення з 1, 2 та 3 літер у даному тексті.

  25. З'ясувати, чи задає дана послідовність перестановку.

  26. Визначити, якою перестановкою одну послідовність отримано з іншої.

  27. Нехай послідовність t1, t2, …, tn побудовано за деякою перестановкою P множини {1, 2, …, n } таким чином: tj — кількість чисел у перестановці P, які стоять лівіше числа j і більші за нього. Відновити перестановку P.

  28. У числовій послідовності вказати найдовшу підпослідовність, яка є арифметичною прогресією.

  29. З елементів даної множини утворити найдовшу арифметичну прогресію.

  30. З'ясувати: чи можна прямокутник (паралелепіпед) з даними довжинами сторін скласти (без розрізання) з прямокутників (паралелепіпедів) з даними довжинами сторін. Скількома способами це можна зробити?

  31. З даних слів сформувати чайнворд.

  32. Розв'язати даний кросворд, знаючи слова-відповіді, але не знаючи їх розташування.

  33. З даних слів сформувати кросворд. Те саме для кросворду з двома осями симетрії.

  34. Побудувати всі квадратні матриці розміру n на n, в яких у кожному рядку, стовпчику та на обох діагоналях розташовані всі натуральні числа від 1 до n. Вказати найбільшу групу таких матриць, що не отримуються одна з одної поворотами та осьовими симетріями.

  35. На кожну клітинку таблиці розміру n на m покладено не більше n на M монет. Рухаючи пішака вгору чи праворуч, забирають всі монети з-під нього. Як зібрати найбільше монет, рухаючись з нижньої лівої клітинки до верхньої правої?

  36. За відомими результатами шахового (футбольного) турніру розподілити місця.

  37. За відомими результатами незакінченого шахового (футбольного) турніру з'ясувати, чи може певний гравець (команда) посісти призове місце.

  38. На шахівниці розміру n на m розташувати певні шахові фігури таким чином, щоб жодна з них не знаходилась під боєм іншої.

  39. Скількома способами можна подати дане натуральне число сумою певних натуральних чисел з повторенням (задача про розмін монет)?

  40. Скільки існує n-цифрових чисел, сума всіх цифр яких дорівнює m? Те ж, якщо у записі чисел не використано певних цифр.

  41. Елементи масиву розділити на дві групи таким чином, щоб абсолютна різниця сум елементів цих груп була найменшою.

  42. Подати дане число арифметичним виразом даних чисел.

  43. Впорядкувати за зростанням нескоротні дроби, які лежать в межах від a до b включно, і знаменник яких не перевищує дане натуральне число m.

  44. Цілі числа
  45. Записати дане натуральне число римськими цифрами.

  46. За відомомим записом натурального числа римськими цифрами відновити його запис у десятковій системі числення.

  47. Обчислити чисельник і знаменник нескоротного дробу, який дорівнює:
    а) 1/2 + 1/6 + 1/12 + … + 1/(n - 1)n;
    б} 1 + 1/2 + 1/3 + … + 1/n.

  48. Обчислити: а) nm; б) n!; в) Ckn; г) ланцюговий дріб a + 1/(b + 1/(c + …)…))) для натуральних a, b, c …; д) перші n чисел Фібоначчі.

  49. Для натурального n з'ясувати, чи можна n! подати добутком k послідовних натуральних чисел.

  50. Знайти j-цифрове натуральне число у системі числення з основою p, k-ий степінь суми цифр якого дорівнює йому самому.

  51. З'ясувати, скільки існує j-цифрових чисел: а) з даними остачами при діленні на дані числа; б) остачі яких при діленні на дані цілі числа рівні.

  52. У старояпонському календарі кожен з 12-ти послідовних років має назву звіра (пацюк, бик, тигр, заєць, дракон, змія, кінь, вівця, мавпа, півень, собака, кабан), а кожен з 5-ти — має колір (зелений, червоний, жовтий, синій, чорний). З'ясувати, яка назва року n, якщо 1984 — рік зеленого пацюка.

  53. Дві арифметичні прогресії задано першими двома членами — натуральними числами. Розглянемо нову арифметичну прогресію — підпослідовность двох даних арифметичних прогресій з найменшою за абсолютною величиною різницею прогресії (серед таких підпослідов­ностей). Знайти суму перших n членів створеної арифметичної прогресії.

  54. Для натурального n обчислити значення функції f(n), заданої рекурентно:
    f (0) = 0,
    f (1) = 1,
    f (2n) = f (n),
    f (2n + 1) = f (n) + f (n + 1).
    Розгляньте
    g(n, i, j) = i f (n) + j f (n + 1), де
    g(2n, i, j) = g(n, i + j, j),
    g(2n + 1, i, j) = g(n, i, i + j),
    f (n) = g(n, 1, 0) = ... = g(0, i, j) = j.

  55. Даний звичайний дріб подати сумою (єгипетських) дробів, чисельники яких дорівнюють 1.

  56. Многочлени
  57. Звести подібні доданки у записі многочлена.

  58. Визначити степінь і коефіцієнти многочлена.

  59. Записати даний многочлен у порядку зростання (спадання) степенів.

  60. Записати суму даних одночленів у порядку зростання (спадання) степенів.

  61. Дійсні числа
  62. Не використовуючи подання чисел масивами, для дійсного x і натурального n обчислити:
    а) x(x + 1)(x + 2) ...(x + n – 1);
    б) (x + 1)(x + 3) ... (x + 2n – 1) : (x + 2)(x + 4) ... (x+2n)

  63. Для дійсного x та натурального n обчислити наближене значення ex як
    1 + x/1! + x2/2! + … + xn/n! і порівняти з точним значенням.

  64. Обчислити значення неперервної функції, означеної на множині дійсних чисел, графік якої складається:

    1. з 2 променів та (n – 2) відрізків, що сполучають точки (x1y1), (x2y2), …, (xnyn), де x1 < x2 < … < xn.

    2. з частин парабол y = ax2 + bx + c на проміжках (–oo; x3), (x3x5), (x5x7), …, (xn – 2; +oo) і проходить через точки (x1y1), (x2y2), …, (xnyn), де x1 < x2 < … < xn, n — непарне.

  65. Для неперервної функції f з [0; 1] у [0; 1] з'ясувати, для яких натуральних k існує розв'язок рівняння x = f ( f (... f (x)...)) (k-кратна суперпозиція), що не є розв'язком цього ж рівняння для менших значень k. Для прикладу розглянути k = 1, 2, 3, ... , 33, f (x) = ax(1 – x), a з (2;4]. Побудувати графік залежності розв'язків рівнянь від величини a.

  66. Планіметрія
  67. Визначити, якою нерівністю задається півплощина, що містить дану точку (a; b) і обмежена прямою, що проходить через дані точки A1(x1y1) і A2(x2y2)

  68. За сторонами трикутника обчислити його: а) площу; б) кути; в) медіани; г) висоти; ґ) бісектриси; д) радіус вписаного кола; е) радіус описаного кола; є) радіуси зовнівписаних кіл; ж) бісектриси внутрішніх кутів.

  69. За а) висотами; б) медіанами трикутника обчислити його сторони.

  70. За координатами вершин опуклого чотирикутника встановити: а) його вид (квадрат, ромб, прямокутник, паралелограм, трапеція); б) чи є він вписаним; в) описаним.

  71. З'ясувати, чи є многокутник з даними координатами вершин опуклим.

  72. Побудуйте коло, яке дотикається до трьох даних кіл координатної площини (задача Аполонія). Використайте рівність кривин — величин, обернених до радіусів кіл:

    2(a2 + b2 + c2 + d2) = (a + b + c + d)2.
  73. Зобразіть частину графіка функції чи кривої (еліпса, параболи, гіперболи, спіралі, циклоїди тощо), розташованої в [a; b]*[c; d]. Реалізуйте керування параметрами кривої та її повторну побудову без переривання виконання програми.

  74. Теорія ігор
  75. Гру «хрестики-нулики» проводять на полі, що містить 3×3 квадратних клітини. Двоє гравців по черзі заповнюють вільні клітини: перший — хрестиком, другий — нуликом. Переможцем вважають того, хто першим заповнить своїми символами горизонталь, вертикаль або діагональ з трьох квадратів. Якщо це не вдалося нікому, то гра закінчується внічию.

  76. Гра «9 цифр». На столі лежать 9 карток, на кожній з яких написано одну з цифр від 1 до 9 включно. Цифри на різних картках різні. Картки лежать написами догори. Двоє гравців по черзі беруть по одній картці зі столу. Переможцем вважають того, хто першим візьме 3 картки, сума цифр на яких дорівнює 15 (на руках у переможця можуть бути й інші картки).

  77. Гра «9 слів». На столі лежать 9 карток, кожна з них містить одне із слів: Лорен, какао, місто, хек, ліс, рама, Ала, меч, рік. Слова на різних картках різні. Картки лежать написами догори. Два гравці по черзі беруть по одній картці зі столу. Переможцем вважають того, хто першим візьме 3 картки зі словами, що мають одну спільну літеру (на руках у переможця можуть бути й інші картки).

  78. Гра «9 шляхів». На схемі — 9 доріг, що сполучають 8 міст. Двоє гравців по черзі зафарбовують своїм кольором (червоним або синім) позначення шляхів. Переможцем вважають того, хто перший зафарбує своїм кольором позначення всіх доріг, які проходять через одне місто.

  79. Гра Баше (Клод Гаспар Баше де Мезірака (1581–1638) — французький математик, поет і перекладач.}. У початковий момент в купці є n предметів. Два гравці по черзі забирають з цієї купки предмети (від 1 до p включно). Переможцем вважають того, хто примусить суперника зробити останній хід. Переможе той, хто робитиме остачу від ділення кількості предметів на (p + 1) рівною 1, 0 — для оберненого варіанту гри.

  80. Гра «на стежині». На кінцях стежини, розбитої на m клітин, стоять шашки різного кольору. Двоє гравців по черзі рухають шашку певного кольору на вільну клітину на довільну кількість клітин в межах від 1 до p включно в довільному напрямку, але без перескакування шашки суперника і виходу за межі стежини. Переможцем вважають того, хто зробить останній хід. Переможна стратегія має такий вигляд. Знайдіть r — остачу від ділення m – 2 на p + 1. Якщо r > 0, то перемістіть свою шашку на r клітин, а кожним наступним ходом зменшуйте кількість вільних клітин між шашками, зберігаючи її кратною p + 1. Після того, як шашки стануть впритул, повторюйте ходи суперника. Якщо ж r = 0, то право першого ходу потрібно запропонувати супернику, а далі дотримуватися вказаних рекомендацій.

  81. Певну кількість фішок розташовано в ряд. Два гравці по черзі забирають довільні 1 або 2 фішки, які стоять поруч. Переможцем вважають того, хто зробить останній хід. Переможе перший гравець, який першим своїм ходом створить два симетричні ланцюги, а всі його наступні ходи будуть відтворювати симетрію. Обернений варіант вимагає аналізу графа гри. Наприклад, якщо на початку гри є 3 фішки в ряду, то виграє перший гравець; якщо 4 фішки, то виграє другий гравець.

  82. Певну кількість фішок розташовано по колу. Два гравці по черзі забирають довільні 1 або 2 фішки, які стоять поруч. Переможцем вважають того, хто зробить останній хід. Переможе другий гравець, який першим своїм ходом створить два симетричні ланцюги, а всі його наступні ходи будуть відтворювати симетрію. Обернений варіант гри вимагає аналізу графа гри. Як і в попередній задачі, якщо на початку гри є 3 фішки на колі, то виграє перший гравець; якщо 4 фішки, то виграє другий гравець.

  83. На початку гри є k груп предметів. Перша група містить m1 предметів, друга — m2, третя — m3, ... , k-та група — mk предметів. Двоє гравців по черзі розбивають кожну групу, що містить більше одного предмета, на дві менші групи. Переможцем вважають того, хто виконає останнє розбиття. Переможець примушує суперника розбивати групи, серед яких найбільша містить 2n – 1 предмет.

  84. Два гравці по черзі виймають із скриньки предмети, кількість яких не перевищує половини наявних у скринці. Програє той, хто візьме останній предмет. Виграє той, хто своєму супернику залишає у скриньці 2n – 1 предмет. Для оберненого варіанту гри — 2n + 1.

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

  86. Є n шашок, розташованих у ряд, n < 15. Двоє гравців ходять по черзі. Першим ходом перевертається будь-яка шашка, а кожним наступним — будь-які одна або дві сусідні ще неперевернуті шашки. Переможцем вважають того, хто примусить суперника зробити останній хід. Якщо n = 5, 7, 10, 13, то переможе перший гравець, намагаючись отримати одну з наступних комбінацій сусідніх неперевернутих шашок: 10+2, 8+4, 6+6, 8+1, 7+2, 6+3, 5+4, 4+3+2, 4+2+2+1, 2+2+2+2, 3+3, 3+2+1, 2+2+1+1, 2+2, 1+1+1. Інакше, якщо n < 15, то виграє другий гравець.

  87. Гра «фан-тан» (нім). На початку гри є k груп предметів. Перша група містить m1 предметів, друга — m2, ... , k-та група — mk предметів. Двоє гравців по черзі забирають з будь-якої групи довільну додатну кількість предметів (можливо, й усі предмети групи). Переможцем вважають того, хто зробить останній хід. Переможець повинен створювати ті позиції, у яких для кожного розряду двійкової системи числення сума цифр кількостей предметів у групах парна. Для оберненого варіанту гри ці дії виконуються доти, поки не залишиться лише одна група, в якій кількість предметів більша за 1.

  88. Нім Фібоначчі. Два гравці по черзі виймають із скриньки предмети. Першим ходом можна взяти довільну додатну кількість, але не всі предмети. Починаючи з другого ходу, кожен гравець бере довільну кількість предметів в межах від 1 до подвоєної кількості предметів, взятих попереднім ходом. Переможцем вважають того, хто зробить останній хід. Кількість предметів у скриньці можна єдиним способом подати сумою чисел Фібоначчі, серед яких немає жодних двох сусідніх чисел Фібоначчі. Якщо кількість предметів не є числом Фібоначчі, то потрібно брати кількість предметів, що є найменшим доданком такого подання.

  89. Нім-ізоморфна гра. Прямокутна таблиця має розміри n на m клітин. На початку гри в кожному рядку таблиці розташовано по одній шашці. Два гравці по черзі рухають будь-яку шашку на довільну додатну кількість клітин праворуч. Переможцем вважають того, хто робить останній хід.

  90. Нім-ізоморфна гра. На m-клітинній лінійці розташовано n шашок. Два гравці по черзі рухають довільну шашку на довільну, відмінну від 0, кількість клітин праворуч. Переможцем вважають того, хто робить останній хід.

  91. Нім-ізоморфна гра. Дано певне натуральне число n. Два гравці по черзі замінюють це число на його частку від ділення на степінь простого числа за умови, що остача дорівнює 0. Переможцем вважаєть того, хто робить останній хід.

  92. Нім-ізоморфна гра Норткотта. Поле для гри — таблиця розміру m на n клітин. На початку гри кожна клітина першого і останнього стовпчиків містять відповідно по одній білій чи чорній шашці. Два гравці по черзі пересувають будь-яку шашку свого кольору на будь-яку додатну кількість клітин, не виходячи за межі відповідного рядка і не перестрибуючи через шашку суперника. Переможцем вважають того, хто зробить останній хід. Розгляньте вільні клітини між шашками у кожному рядку як предмети, які забирають з купи-рядка. Скористайтеся виграшною стратегією гри нім з незначною модифікацією: якщо суперник "відступає", то потрібно повторювати його хід.

  93. Гра Дьюдені (Генрі Ернест Дьюдені (1857-1930) — англійський математик, автор багатьох ломиголовок). Двоє гравців по черзі називають натуральні числа в межах від 1 до m включно, причому кожне назване число відмінне від попереднього. Знаходиться сума S всіх названих чисел. Переможцем вважають того, хто отримає рівність S = p або примусить суперника отримати нерівність S > p. Починаючи з S = p + 1, суми названих чисел програшних позицій відрізняються на m + 1, якщо m парне або m + 1 містить 2 у розкладі на прості множники парну кількість разів, і на m + 2 в усіх інших випадках.

  94. Гра Болтянського (Володимир Григорович Болтянський (1925) — російський математик). Двоє гравців по черзі називають натуральні числа в межах від a до b включно. Знаходиться добуток всіх названих чисел. Переможцем вважають того, хто перший отримає добуток, більший за c.

  95. Гра дат. Перший гравець називає будь-яку дату січня. Далі гравці по черзі збільшують або порядковий номер місяця в році, або номер дня у місяці. Переможцем вважають того, хто перший отримає дату 31 грудня. Програшні позиції для того гравця, чия черга ходити: 31 грудня, 30 листопада, 29 жовтня, 28 вересня, 27 серпня, 26 липня, 25 червня, 24 травня, 23 квітня, 22 березня, 21 лютого, 20 січня. Перемагає той, хто кожним своїм ходом переводить гру в одну з таких позицій.

  96. Давньокитайська гра «цзяньшицзи» (вибирання каменів). На початку гри є дві групи предметів. Два гравці по черзі забирають предмети з цих груп : або лише з однієї групи довільну кількість (можна всі предмети, але не менше, ніж один), або з обох груп однакову додатну кількість. Переможцем вважають того, хто зробить останній хід. Ізоморфна гра полягає в пересуванні шахової королеви клітинами шахівниці ліворуч, праворуч чи по діагоналі ліворуч і праворуч одночасно або у відповідному переміщенні в точки з цілими координатами першої чверті координатної площини. Послідовність програшних позицій: (0; 0), (1; 2), (3; 5), (4; 7), (6; 10), (8; 13), (9; 15), (11; 18), ... , (an; bn), ... побудуємо рекурентно:

    • an + 1 — найменше з натуральних чисел, відмінних від aj і bj для всіх j у межах від 0 до n включно;
    • bn + 1 = an + n + 1.

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

  97. «Одинокий король». На початку гри шаховий король стоїть на полі a1 (нижній лівий кут). Двоє гравців по черзі рухають короля на одне поле праворуч, вгору або по діагоналі праворуч і вгору одночасно. Переможцем вважають того, хто перший пересуне короля на поле h8 (правий верхній кут).

  98. Гра «перемагає парність». На початку гри є група предметів, що містить їх непарну кількість n = 2k + 1. Двоє гравців по черзі забирають з цієї групи предмети — від одного до p включно, накопичуючи їх в себе. Переможцем вважають того, хто наприкінці гри матиме парну кількість предметів.


  99. На початку гри на полі 5 розташовано білу шашку, а на полі 15 — чорну. Два гравці по черзі пересувають шашки: перший — лише білу (він починає гру), другий — лише чорну на сусіднє поле вздовж лінії. Перший гравець виграє тоді, коли не більше, ніж за 6 ходів поставить білу шашку на чорну. Інакше перемагає другий гравець, який ходить чорною шашкою. Розділимо поля на дві групи: {1, 3, 4, 6, 9, 11, 12, 14} і {2, 5, 7, 8, 10, 13, 15}. На початку гри шашки розташовані на полях однієї групи. Кожний хід переводить шашку на поле з іншої групи, крім ходів 1 ↠ 4 і 4 ↠ 1. Тому перші два ходи білою шашкою вимушені; 5 ↠ 4 або 5 ↠ 1 ↠ 4. Далі білу шашку потрібно пересувати назустріч чорній.


  100. Гра «Тригекс». Поле для гри містить 9 кругів з центрами на 9-ти прямих. Двоє гравців по черзі ставлять на круги по одній фішці свого кольору (білого або чорного). Переможцем вважають того, хто перший займе три круга на одній з проведених прямих. Перемагає той, хто робить перший хід на круг 1, 2 або 3. Подальші ходи потрібно робити таким чином, щоб ходи суперника, починаючи з другого, були вимушеними. Вимушеними в тому розумінні, що всякий інший хід-відповідь негайно призводить до програшу. Подамо таблицею приклад виграшної стратегії, перебравши всі відповіді на 1-ий хід в круг 1.

    1-2, 7-8, 9-3, 66, 3
    1-3, 8-7, 9-2, 66, 2
    1-4, 7-8, 9-3, 66, 3
    1-5, 8-7, 9-2, 66, 2
    1-6, 7-8, 4-2, 55, 2
    1-7, 4-5, 6-3, 99, 3
    1-8, 5-4, 6-2, 99, 2
    1-9, 5-4, 8-3, 77, 3
  101. Гра Піта Хейна «такс-тікс». Квадратну дошку розділено на однакові клітини квадратної форми. На початку гри кожна клітина містить по одній шашці. Грають двоє, ходять по черзі. За один хід забирають довільну кількість шашок з будь-якого вертикального стовпчика або горизонтального рядка. Брати шашки дозволяється лише підряд, не перескакуючи через порожні клітини. Переможцем вважають того, хто бере останню шашку. Якщо кількість клітин парна, то виграє 2-ий гравець, використовуючи «центрально-симетричні» ходи-відповіді. Якщо кількість клітин непарна, то виграє перший гравець: першим ходом звільняється центральна клітина (стовпчик, рядок), а далі — «центрально-симетричні» ходи-відповіді. Для оберненого варіанту гри потрібно провести аналіз графа гри.


  102. Гра Піта Хейна «гекс». Робмовидну дошку розбито на правильні шестикутники. Дві протилежні сторони ромба називають чорними, дві інші — білими. Два гравці по черзі виставляють на вільні шестикутники по одній фішці: один гравець — білі, інший — чорні фішки. Переможцем вважають того, хто перший побудує ланцюг із своїх фішок між "своїми" сторонами.

  103. Гра Ґранді (Ґвідо Ґранді (1671-1742) — італійський математик). На початку гри є одна загальна група предметів, що містить n предметів. Два гравці по черзі розбивають одну з наявних \grup на дві нерівні частини. Гра триває доти, доки всі групи не міститимуть 1-2 предмети. Переможцем вважають того, хто виконає останнє розбиття. Пошук стратегії вимає аналізу графа гри. Припущення, що програє перший, якщо n = 3k + 1, не справджується для n = 13 = 5 + 8.

  104. Гра «двоколірні шашки». Ігрове поле — прямокутна дошка, поділена на 8*8 квадратних клітин. На початку гри на кожній клітині встановлено по одній двоколірній шашці (одна сторона біла, інша чорна) довільним чином. Два гравці сидять з одного боку дошки і по черзі перевертають шашки у довільному прямокутному блоці клітин, правий нижній кут якого містить шашку з чорним верхом. Переможцем вважають того, хто отримає розташування всіх шашок білою стороною догори. Подамо рекомендації М.Гарднера (Scientific American, 1979, 2) без доведення. Розташуємо на кожній клітині ігрового поля натуральне число згідно поданою допоміжною таблицею.

    Допоміжна таблиця для гри «двоколірні шашки» має такий вигляд:

    1 2 1 4 1 2 1 8
    2 3 2 8 2 3 212
    1 2 1 4 1 2 1 8
    4 8 4 6 4 8 411
    1 2 1 4 1 2 1 8
    2 3 2 8 2 3 212
    1 2 1 4 1 2 1 8
    812 811 812 813

    Допоміжна таблиця для гри «двоколірні шашки», числа якої подано у двійковій системі числення, має такий вигляд.
    1 10 1 100 1 10 11000
    10 11 101000 10 11 101100
    1 10 1 100 1 10 11000
    1001000 100 110 1001000 1001011
    1 10 1 100 1 10 11000
    10 11 101000 10 11 101100
    1 10 1 100 1 10 11000
    10001100100010111000110010001101

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

  105. Гра Джона Конуея і Майкла Стюарта Патерсона «розсада». На аркуші паперу виділено n точок («ямок для розсади»). Два гравці по черзі проводять лінії, що починаються в одній з точок («розсада пускає росток»). Ці лінії або з'єднують дві різні виділені точки, або описують петлю й повертаються у початкову виділену точку. Кожна така лінія не має точок самоперетину, не перетинає інші проведені лінії і не проходить через виділену точку, що не є її початком або кінцем. При цьому з кожної точки має виходити не більше, ніж 3 лінії. Після проведення лінії гравець ставить на ній нову точку. Переможцем вважають того, хто проведе останню лінію.


  106. Гра L. Ігрове поле — квадратна дошка, поділена на 4×4 квадратних клітин. Двоє гравців мають по одній L-подібній фігурі різного (білого або чорного) кольору і дві спільні фішки. Виконати хід — це обов'язково змінити розташування своєї фігури, не покриваючи клітинки поля, зайняті фігурою суперника або фішками, при необхідності перевертаючи фігуру. Після цього можна, але не обов'язково, перемістити одну фішку на вільну клітину. Гравці ходять по черзі. Гру починають білі. Переможцем вважають того, хто зробить останній хід.

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

  108. На площині дано вершини правильного 6-кутника. Два гравці по черзі зафарбовують сторони і діагоналі 6-кутника синім та червоним кольором. Переможцем вважають того, хто примусить суперника побудувати трикутник з відрізків свого кольору.

  109. Ломиголовка «Ханойські башти». На одному стержні A нанизано диски таким чином, що діаметри основ дисків зменшуються знизу догори. Потрібно перекласти ці диски на інший стержень B, використовуючи допоміжний стержень C. При цьому заборонено розташовувати диск більшого діаметра над диском меншого діаметра. Використайте рекурсію.

  110. На прямій рухаються точки A і B з швидкостями vA > vB. Вказати одну з можливих стратегій (поведінок) точки А, за яких точка A, зіткнеться з точкою В незалежно від того, в яку сторону і на якій відстані точка B буде розташована відносно A у початковий момент, якщо відомо:
    а) vA та vB;
    б) vA.
    Обчислити час до зіткнення для обраної стратегії за певних значень vA , vB та початкового розташування точок A та B. Яка необхідна умова існування такої стратегії, якщо нерівність між змінними швидкостями точок не справджується у довільний момент часу? Перевірте послідовно припущення щодо величини координати B у початковий момент: +1, –1, +2, –2, +3, –3, … У варіанті б) перевірте ще й припущення про величину vB: vA(1 – 1/2), vA(1 – 1/3), vA(1 – 1/4), … . Для обґрунтування використайте графіки залежності координат від часу. Необхідна умова: інтеграли (за часом) різниці швидкостей необмежені зверху.

Література
  1. Арсак Ж. Программирование игр и головоломок. М.: Наука, 1990, 223 с.

  2. Бардадим В.О. Сьома міжнародна олімпіада з інформатики // У світі математики, 1995, том 1, № 2, с.57-65.

  3. Бардадим В.О., Бондаренко В.В., Данильченко С.В., Рубан І.І. IX Всеукраїнська олімпіада з інформатики // У світі математики, 1996, 2, № 3, с.90-94.

  4. Бардадим В.О., Гуржій А.М. Задачі IX Міжнародної олімпіади з інформатики // Комп'ютер у школі та сім'ї, 1998, 2, с.46-50.

  5. Бондаренко В.В., Грушецький О.М. X Міжнародна олімпіада з інформатики // Комп'ютер у школі та сім'ї, 1999, 1, с.46-52.

  6. Бондаренко В.В., Жук С.О. Задачі XII Всеукраїнської олімпіади з інформатики та обчислювальної техніки // Комп'ютер у школі та сім'ї, 1999, 3, с.41-45.

  7. Виленкин Н.Я. Комбинаторика. М.: Наука, 1969, 328 с.

  8. Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985, 406.

  9. Вишенський В.А., Дороговцев А.Я., Єжов І.І., Скороход А.В., Ядренко М.Й. Вибрані питання елементарної математики. К.: Вища школа, 1982, 455 c.

  10. Вишенський В.А., Перестюк М.О., Самойленко А.М. Збірник задач з математики. К.: Либідь, 1993, 344 c.

  11. Вишенський В.А. Гра фан-тан // У світі математики, 1995, том 1, № 2, с.69-74.

  12. Вишенський В.А. Гра цзяньшицзи // У світі математики, 1996, том 2, №o 1, с.75-81.

  13. Дэйкстра Э. Дисциплина программирования. М.: Мир, 1978, 274 с.

  14. Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0. М.: Диалог-МИФИ, 1995, 282 c.

  15. Касаткин В.В., Владыкина Л.И. Алгоритмы и игры. К.: Радянська школа, 1984, 95 c.

  16. Касаткін В.М. Кунст-камера алґоритмів // Комп'ютер у школі та сім'ї, 1998, 2, с.44-45.

  17. Ліо Кі (Левко Ковалів). Ломиголовки (ігри без партнера). К.: ТВіМС, 1996, 150 с.

  18. Лоповок Л.М. Збірник математичних задач логічного характеру. К.: Радянська школа, 1972, 151 c.

  19. Раков С.А., Білоусова Л.І. VIII Всеукраїнська олімпіада студентів з інформатики // Комп'ютер у школі та сім'ї, 1999, 4, с.47-50.

  20. Уэзерелл Ч. Этюды для программистов. М.: Мир, 1982, 287 с.

  21. Хижа О.Л. Розв'язування задач підвищеної складності з інформатики // Інформатика, 1999, 37, 38, 42.