сло міст. Число доріг дорівнює числу міст х, помноженому на 3 (число виходять із кожного міста доріг) і розділеному на 2. Тоді 100=Зх/2= gt; Зх=200, чого не може бути при натуральному х. Значить 100 доріг в такій державі бути не може.
. У класі 30 чоловік. Чи може бути так, що 9 осіб мають по 3 одного, 11 - по 4 одного, а 10 - по 5 друзів?
Відповідь. Ні (теорема про парність числа непарних вершин).
. У короля 19 васалів. Чи може виявитися так, що у кожного васала 1, 5 або 9 сусідів?
Відповідь. Ні, не може.
. У Квітковому місті кожен коротун знайомий з 6 малятами, а кожна малятко - з 6 коротунами. Доведіть, що в цьому місті число маляток дорівнює числу коротишек.
Рішення. Якщо знайомство виду «коротун - маля» - це ребро графа, то n - число коротишек, m - число маляток. Тоді всіх знайомств (ребер) коротишек 6n, а маляток 6m. Значить 6n=6m, тоді в цьому місті число маляток дорівнює числу коротишек.
. Діма, приїхавши з Мехеево, розповів, що там є кілька озер, з'єднаних між собою річками. З кожного озера випливають 3 ріки, і в кожне озеро впадають 4 річки. Доведіть, що він помиляється.
Рішення. Якщо випливають 3 річки, а впадають 4 - це неможливо, т. К. Кількість «втікають», має дорівнювати кількості «випливають». Діма не прав.
. Волейбольна сітка - прямокутник 50x600 клітин. Яке найбільше число мотузочок можна перерізати, щоб сітка не розпалася?
Рішення. Будемо розглядати волейбольну сітку як граф, вершинами якого є вузли сітки, а ребрами - мотузочки. У цьому графі потрібно видалити якомога більше ребер так, щоб він залишився зв'язковим. Зауважимо, що поки в графі є цикл, можливе видалення будь-якого ребра цього циклу. Зв'язний граф, який не має циклів, є деревом. Тому, тільки отримавши дерево, ми не зможемо прибрати жодного ребра. Спочатку в графі було 601 · 50 + 600 · 51=60 650 ребер і 51 · 601=30651 вершин, т. Е. Дерево матиме 30650 ребер. Таким чином, розрізати можна 60650-30650=30000 мотузочок.
. Всі міста країни, крім столиці, розташовані вздовж шосе. Зі столиці в кожне місто веде пряма дорога. Дві компанії хочуть приватизувати дороги і ділянки шосе так, щоб кожна компанія могла проїхати з будь-якого міста в будь-який інший тільки за своїми дорогами. Чи зможуть вони це зробити при якому-небудь числі міст, більшому одного?
Рішення. Припустимо, що це можливо, тоді нехай на шосе n міст, значить доріг всього (2n - 1). Оскільки дороги однієї компанії з'єднують всі міста в зв'язне безліч, то цих доріг не менше n. Тоді доріг двох компаній не менше 2n, що нам суперечить, а значить не зможуть виконати умови.
. У місті Н від кожної площі відходить рівно 5 вулиць, що з'єднують площі. Доведіть, що число площ парно, а число вулиць кратно 5.
Рішення. По теоремі, що число непарних вершин будь-якого графа парно, випливає, що число площ (вершин графа) 2n, а число вулиць (ребер графа) буде (2n · 5): 2, а значить, число площ парно, а число вулиць кратно 5.
