2.4. Метод таблиць і графів

При розв’язуванні логічних задачах для систематизації даних дуже часто

використовуються таблиці та графи. Графи – це рисунки, за допомогою яких

показується залежність між деякими об’єктами логічної задачі.

Приклад 1. Три подружки Таня, Оля і Катя прийшли на свято в сукнях

різного кольору: одна – в білому, друга – в червоному, третя – в зеленому. Таня

– не в червоному, Оля – не в червоному і не в зеленому. Скажіть в якій сукні

кожна з дівчаток?

Для розв’язання задачі складемо і заповнимо таблицю:

Таня Оля Катя

Біла сукня – + –

Червона сукня – – +

Зелена сукня + – –

Таким чином, Таня була в зеленій сукні, Оля – в білій, Катя – в червоній.

Завдання. Зобразити розв’язання задачі у вигляді графів.

Приклад 2. В понеділок, вівторок, середу повинні чергувати в класі Ваня,

Олег і Саша. Але хлопці сказали свої бажання:

- Мене не призначайте на середу, бо я в цей день займають в музичній

школі, - сказав Ваня.

- У вівторок я іду на тренування в спортивну школу, - повідомив Олег.

- А мене призначте на вівторок, - попросив Саша.

Всі побажання друзів були виконані. Як чергували хлопці?

Математична логіка

39

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

понеділок вівторок середа

Ваня + – –

Олег – – +

Саша – + –

Отже, Ваня чергував у понеділок, Олег – в середу, а у вівторок чергував Саша.

Завдання. Зобразити розв’язання задачі у вигляді графів.

Приклад 3. В одній сім’ї багато дітей. Семеро з них люблять капусту, шестеро –

моркву, п’ятеро – огірки, четверо – капусту і моркву, троє – капусту і огірки,

двоє – моркву і огірки, а один любить і капусту, і моркву, і огірки. Скільки дітей

в сім’ї?

Розв’язання. Зручно розв’язувати задачу з кінця за допомогою таблиці:

1 2 3 4 5 6 7 8 9 10

Люблять капусту + + + + + + +

Люблять моркву + + + + + +

Люблять огірки + + + + +

Отже, в сім’ї повинно бути 10 дітей.

Завдання. Зобразити розв’язання задачі у вигляді графів.

ЗАДАЧІ

1. Три однокласниці Соня, Таня, Женя займаються в спортивних секціях:

одна – в гімнастичній, друга – в лижній, третя – по плаванню. Яким видом

спорту займається кожна з них, якщо відомо, що Соня не вміє плавати,

Таня в лижну секцію ніколи не ходила, а Женя – призер в змаганнях по

лижам?

2. Володимир, Ігор та Сергій викладають математику, фізику і літературу.

Живуть вони в Києві, Львові та Одесі. Відомо також, що Володимир живе

не у Львові, Ігор живе не в Одесі, одесит – не фізик, Ігор – не математик,

львів’янин викладаєлітературу. Хто де живе та що викладає.

Математична логіка

40

3. Іваненко, Петренко, Леоненко і Симоненко – 4 талановитих молодих

чоловіка. Один з них танцюрист, другий – художник, третій – співак,

четвертий – письменник. Про них відомо, що:

1) Іваненко і Леоненко сиділи в залі консерваторії тоді, коли співак

виступав на сцені.

2) Художник малював портрети Петренка і письменника.

3) Письменник написав біографічне оповідання про Симоненка і

збирається написати про Іваненка.

4) Іваненко ніколи не чув про Леоненка.

Хто чим займається?

2.5. Принцип діріхле

У своїй доповіді «Про професію математика» академік А. М. Колмогоров

підкреслив, що навіть довести, що у хвойному лісі з восьмисот тисяч ялинок, на

кожній з яких не більше 500 000 глиць, принаймні на двох ялинках число

хвоїнок однакове, викликає труднощі у багатьох учнів. У олімпіадних задачах,

які пропонувались за останні роки, логічний наголос ставився саме на таких

запитаннях. Подібні задачі можна умовно назвати задачами на принцип Діріхле.

Під цим принципом розуміють таке твердження: «Якщо п + 1 об'єктів розміщати

на п місцях, то знайдеться принаймні два об'єкти, які розмістяться на одному і

тому самому місці». Цей принцип допоміг

німецькому математикові П.Діріхле (1805—1859)

досягти значних успіхів у своїх дослідженнях з теорії

чисел. У жартівливій формі принцип Діріхле часто

формулюють так: «П'ять кроликів не можна поса-

дити у чотири клітки так, щоб кожний з них сидів в

окремій клітці».

Розглянемо деякі задачі, які розв'язуються за допо-

могою принципу Діріхле.

1. У школі 740 учнів. Довести, що принаймні троє з

Математична логіка

41

них в один і той самий день святкують свій день народження.

Доведення. Якби щодня двоє учнів святкували свій день народження, то в школі

було б 732 учні.

2. Довести, що серед 101 цілого числа можна вибрати два, різниця яких ділиться

на сто.

Доведення. Нагадаємо, що при діленні числа на 100 може бути 100 остач: 0, 1, 2,

..., 99. Серед 101 остачі, які ми дістаємо від ділення даних в умові 101 числа

на 100, принаймні дві однакові. Різниця цих двох чисел і ділиться на 100.

3. П’ять школярів з’їли шість цукерок. Чи правильно, що хоча б один з’їв не

менше двох цукерок? Чи правильно, що один з’їв дві цукерки?

4. На складі є 28 пар взуття трьох розмірів. Доведіть, що серед них можна

вибрати не менше 10 пар однакового розміру.

5. У класі 15 учнів. Чи знайдеться місяць, у якому святкують свій день

народження не менше ніж два учні цього класу?

6. У школі 30 класів і 1000 учнів. Доведіть, що у школі є клас, в якому не менше

34 учнів.

Доведення. Якби такого класу не було, то в школі було б не більше ніж

30·33=990 учнів.

7. У школі навчається 677 учнів. Доведіть, що принаймні у двох із них

збігаються перші літери імені та прізвища.

8. У класі навчається 41 учень. Під час диктанту учень Помилкин зробив 13

помилок, а всі інші – менше. Доведіть, що є принаймні 4 учні, які зробили

однакову кількість помилок.