При розв’язуванні задач зручно користуватися правилами суми та добутку.

Правило суми: якщо деякий об’єкт А можна вибрати m способами, а інший об’єкт В можна вибрати n способами, то вибір "Або А, або В" можна здійснити m+n способами.

При використанні правила суми потрібно слідкувати, щоб жоден із способів вибору об’єкта А не співпадав із жодним способом вибору об’єкта В.

Приклад 1.

У вазі лежать чотири яблука та три груші. Скількома способами можна обрати один фрукт?

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

Якщо у вазі лежать 4 яблука, то одне яблуко можна обрати чотирма способами (можемо взяти одне із 4 яблук). Якщо у вазі лежать 3 груші, то одну грушу можна обрати трьома способами (можемо взяти одну із трьох груш). А обрати один фрукт можна 4+3=7 способами.

Правило добутку: якщо деяк ... Читати далі »

Принцип Діріхле найпростіше зрозуміти, використавши таку його жартівливу форму: "Якщо в N клітках сидять не менше N+1 кроликів, то у якійсь із кліток сидить не менше двох кроликів". Звернемо увагу на невизначеність висновків – "у якійсь із кліток", "не менше". Ця невизначеність часто призводить до цікавих висновків на основі, здавалось би, недостатніх даних. Часто при розв’язуванні задач на принцип Діріхле точне доведення міркувань можна дати за допомогою доведення від супротивного.

Приклад 1.

У мішку лежать кульки двох кольорів: чорного та білого. Яку найменшу кількість кульок  потрібно дістати з мішка наосліп, щоб серед них точно виявились дві кульки одного кольору?

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

Зрозуміло, що двох кульок може не вистачити: може виявитись, що вони різних кольорів. Тому слід взяти не менше 3 кульок. Доведемо, що 3 кульок досить. Припустимо протилежне &nd ... Читати далі »