Задачі на стратегію гри

Методи розв’язування та приклади задач на стратегію гри

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

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

Сформулюємо принцип Діріхле на прикладі кроликів і ящиків.

Якщо по п ящикам розсадити >п кроликів, то обов’язково знайдеться ящик або кілька ящиків, в яких сидить більше одного кролика.

Сформулюємо узагальнений принцип Діріхле.

Якщо в n ящиках сидить не менше nk+1 кроликів, то принаймі в одному ящику сидить більше k кроликів.

Задача 1. У школі 20 класів. В найближчому будинку живуть 23 учні цієї школи. Чи можна стверджувати, що серед них знайдуться хоча б двоє однокласників?

Розв’язання. Оскільки в даній задачі n=20, а учнів 23>n, то можна стверджувати, що в будинку живуть хоча б двоє однокласників.

Задача 2. У ящику лежать 105 яблук чотирьох сортів. Доведіть, що серед них принаймні 27 яблук одного сорту.

Доведення. В даній задачі n=4, де 4 – це кількість сортів яблук. Якщо взяти по 26 яблук кожного сорту, то k=26. Тоді nk=4x6+1=105. Отже яблук одного певного сорту буде 27, всіх інших – 26.

Задача 3. На 5 полицях шафи стоять 160 книг. На одній з них – 3 книги. Доведіть, що знайдеться полиця, на якій стоїть не менше 40 книг.

Доведення. Якщо такої полиці немає, тоді на 5 полицях 3+4×39=159 книг, але це суперечить умові задачі, оскільки маємо 160 книг. Тому на одній з полиць 40 книг.

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

Комбінаторикою називають галузь математики, яка вивчає питання, пов’язані з визначення кількості різних комбінацій за даних умов та заданих об’єктів. Більшість задач розв’язуються за допомогою двох основних правил – правило суми та правило добутку.

Правило суми. Якщо об’єктАможна вибрати m способами, а об’єкт В – n способами, то об’єкт А або В можна вибрати m+n способами.

Правило добутку. Якщо об’єктАможна вибрати m способами, і після кожного такого вибору об’єкт В можна вибрати n способами, то пару об’єктів А і В можна вибрати m×n способами.

Задача 4. З міста А до міста Б ведуть дві дороги, з міста А в місто Г – чотири дороги, з Б в В – три дороги, з Г в В – п’ять.

а) Скільки різних доріг ведуть з А в В через Б?

б) Скільки взагалі різних доріг з А в В?

Розв’язання.

а) за правилом добутку 2×3=6.

б) Розглянемо два випадки: шлях проходить через Б і через Г. В першому випадку за правилом добутку маємо 2×3=6, в другому - 4×5=20 доріг. За правилом суми 20+6=26 доріг.

Задача 5. Скількома способами можна вибрати чотирьох чергових з 30 учнів класу?

Розв’язання. Першого чергового можна вибрати 30, другого – 29, третього – 28, четвертого – 27 способами.Отже, всього 30×29×28×27=657720 способів.

Задача 6. В магазині є 6 примірників олімпіадних задач з математики, 3 з фізики і 4 з біології. Крім того, є 5 комбінованих примірників з математики і фізики і 7 – з фізики і біології. Скількома способами можна придбати примірник, який містить задачі з одного предмету.

Розв’язання. Можна придбати або примірник з кожного предмету, або примірник з двох предметів і примірник з одного. За правилами добутку і суми отримаємо 6×3×4+5×4+7×6=134 способи.

Переливання

Задача 7. Як за допомогою 3-літрового і 5-літрового відер набрати 1 літр води? У розпорядженні є водопровідний кран і раковина, куди можна виливати воду.

Розв’язання. Розв’язання цієї задачі можна записати у вигляді таблиці. Спочатку обидва відра порожні. Наповнюємо 3-літрове відро і виливаємо воду з нього у 5-літрове. Знову наповнюємо 3-літрове відро і виливаємо її у 5-літрове, поки воно не наповниться. У

3-літровому відрі залишиться 1 літр води.

Задача 8. Маємо три ємності: 9 л, 5 л, 3 л. Перша наповнена водою, а інші дві порожні. Як за допомогою цих ємностей відміряти 1 л води? Як відміряти 4 л води?

Розв’язання.

Задача 9. У трьох купках лежать 22, 14 і 12 горіхів. За допомогою трьох перекладань зрівняйте кількість горіхів у купках.

Розв’язання: Оскільки горіхів всього 48, то в кожній купці повинно опинитися по 16. Перекладати з однієї купки в іншу можна стільки горіхів, скільки їх є в купці в яку перекладають. Схематично перекладання можна показати так:

(22,14,12) — (8,28,12) — (8,16,24) — (16,16,16).