Усі 10000 комбінацій з 4 цифр. Чи важко вгадати PIN-код пароль

Незважаючи на важливу роль PIN-кодів у світовій інфраструктурі, досі не проводилося академічних досліджень про те, як, власне, люди обирають PIN-коди.

Дослідники з університету Кембриджу Sören Preibusch та Ross Anderson виправили ситуацію, опублікувавши перший у світі кількісний аналіз складності вгадування 4-циферного банківського PIN-коду.

Використовуючи дані про виток паролів з небанківських джерел та онлайн анкетування, вчені з’ясували, що до вибору PIN-кодів користувачі ставляться набагато серйозніше, ніж до вибору паролів для веб-сайтів: більшість кодів містять практично випадковий набір цифр. Тим не менш, серед вихідних даних присутні і прості комбінації, і дні народження, тобто при деякому везенні зловмисник може просто вгадати заповітний код.

Відправною точкою дослідження був набір 4-циферних послідовностей у паролях з бази RockYou (1.7 млн), та бази з 200 тисяч PIN-кодів від програми блокування екрану iPhone (базу надав розробник програми Daniel Amitay). У графіках, побудованих за цими даними, проступають цікаві закономірності — дати, роки, цифри, що повторюються, і навіть PIN-коди, що закінчуються на 69. На основі цих спостережень вчені побудували лінійну регресійну модель, яка оцінює популярність кожного PIN-коду в залежності від 25 факторів, – наприклад, чи є код датою у форматі ДДММ, чи він зростаючою послідовністю, і так далі. Цим загальним умовам відповідають 79% та 93% PIN-кодів у кожному наборі.

Отже, користувачі вибирають 4-циферні коди на основі лише кількох простих факторів. Якби так вибиралися і банківські PIN-коди, 8-9% із них можна було б вгадати лише за три спроби! Але, звичайно, до банківських кодів люди ставляться набагато уважніше. Зважаючи на відсутність скільки-небудь великого набору справжніх банківських даних, дослідники опитали більше 1300 осіб, щоб оцінити, наскільки реальні PIN-коди відрізняються від розглянутих. Враховуючи специфіку дослідження, у респондентів запитували не про самі коди, а лише про їх відповідність якомусь із вищезгаданих факторів (зростання, формат ДДММ тощо).

Виявилося, що люди справді набагато ретельніше вибирають банківські PIN-коди. Приблизно чверть опитаних використовують випадковий PIN, згенерований банком. Більше третини вибирають свій PIN-код, використовуючи старий номер телефону, номер студентського квитка або інший набір цифр, який виглядає випадковим. Згідно з отриманими результатами, 64% власників карток використовують псевдовипадковий PIN-код, – це набагато більше, ніж 23-27% у попередніх експериментах з не-банківськими кодами. Ще 5% використовують цифровий патерн (наприклад, 4545), а 9% віддають перевагу патерну на клавіатурі (наприклад, 2684). Загалом, зловмисник із шістьма спробами (три з банкоматом та три з платіжним терміналом) має менше 2% шансів вгадати PIN-код чужої картки.

Все б добре, але, на жаль, істотна частина опитаних (23%) обирає PIN-код у вигляді дати, і майже третина з них використовує дату свого народження. Це суттєво змінює справу, адже майже всі (99%) респонденти відповіли, що зберігають у гаманці з банківськими картками різні посвідчення особи, на яких цю дату надруковано. Якщо зловмисник знає день народження власника картки, то за грамотного підходу ймовірність вгадування PIN-коду злітає до 9%.

100 найпопулярніших PIN-кодів

0000, 0101-0103, 0110, 0111, 0123, 0202, 0303, 0404, 0505, 0606, 0707, 0808, 0909, 1010, 1101-12 1956-2015, 2222, 2229, 2580, 3333, 4444, 5252, 5683, 6666, 7465, 7667.

PS На практиці, зрозуміло, зловмиснику набагато простіше підглянути ваш PIN-код, ніж вгадувати його. Але й від підгляду можна захиститись — навіть, здавалося б, у безвихідному становищі:

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

Опис алгоритму генерації під калькулятором

Алгоритм

Комбінації генеруються у лексикографічному порядку. Алгоритм працює з порядковими індексами елементів множини.
Розглянемо алгоритм з прикладу.
Для простоти викладу розглянемо безліч із п’яти елементів, індекси в якому починаються з 1, а саме, 1 2 3 4 5.
Потрібно згенерувати всі комбінації розміру m = 3.
Спочатку ініціалізується перша комбінація заданого розміру m – індекси в порядку зростання
1 2 3
Далі перевіряється останній елемент , тобто i = 3. Якщо його значення менше n – m + i, він інкрементується на 1.
1 2 4
Знову перевіряється останній елемент, і знову він инкрементируется.
1 2 5
Тепер значення елемента дорівнює максимально можливому: n – m + i = 5 – 3 + 3 = 5, перевіряється попередній елемент з i = 2.
Якщо його значення менше n – m + i, він інкрементується на 1, а всіх наступних за ним елементів значення прирівнюється до значення попереднього елемента плюс 1.
1 (2+1)3 (3+1)4 = 1 3 4
Далі знову йде перевірка для i = 3.
1 3 5
Потім – перевірка для i = 2.
1 4 5
Потім настає черга i = 1.
(1+1)2 (2+1)3 (3+1)4 = 2 3 4
І далі,
2 3 5
2 4 5
3 4 5 – останнє поєднання, тому що всі його елементи дорівнюють n – m + i.Друзі! Якщо вже є в мене цей мертвий блокнот, використовую його для того, щоб задати вам завдання, над яким вчора билося три фізики, два економісти, один політехівський і один гуманітарій. Ми зламали собі весь мозок і в нас постійно виходять різні результати. Можливо, серед вас є програмісти та математичні генії, до того ж, завдання взагалі шкільне і дуже легке, у нас просто не виводиться формула. Тому що ми кинули заняття точними науками і натомість навіщось пишемо книги і малюємо картини. Вибачте.

Мені видали нову банківську картку і я, як водиться, граючи вгадала її пін-код. Але не підряд. У сенсі, скажімо, пін-код був 8794, а я назвала 9748. Тобто, я тріумфально вгадала всі цифри , які містилися в цьому чотиризначному числі. Ну так, не саме число , а просто його складові у гадала. Але цифри всі вірні! ПРИМІТКА – я діяла навмання, тобто мені не треба було розставити вже відомі числа в потрібному порядку, я просто діяла в дусі: ось тут є невідомі мені чотири цифри, і я вважаю, що серед них можуть бути 9, 7, 4 і 8, а порядок їх важливий. Ми відразу запитали, скільки в мене взагалі було варіантів (напевно, щоб зрозуміти, наскільки це круто, що я взяла і вгадала). Тобто, із скількох комбінацій чотирьох цифр мені треба було обирати? І тут, природно, почалося пекло. У нас весь вечір вибухала голова, і у всіх, зрештою, вийшли абсолютно різні варіанти відповіді! Я навіть почала виписувати всі ці комбінації в блокнот поспіль у міру зростання, але на чотирьох сотнях зрозуміла, що їх більше чотирьох сотень (принаймні це спростувало відповідь фізика Треша, який запевняв мене, що комбінацій чотири сотні, але все одно це не абсолютно однозначно) – і здалася.

Власне, суть питання. Яка ймовірність вгадування (у будь-якому порядку) чотирьох чисел, що містяться у чотиризначному числі?

Або ні, переформулюємо (я гуманітарій, вибачте, хоча до математики завжди мав велику слабкість), щоб було ясніше і чіткіше. Скільки не повторюваних комбінацій цифр міститься у ряді порядкових числівників від 0 до 9999? ( Будь ласка, не плутайте це з питанням “скільки комбінацій цифр, що не повторюються “!! ! цифри можуть повторюватися! в сенсі, 2233 і 3322 – це в даному випадку одна і та ж комбінація!!).

Або ще конкретніше. Мені потрібно чотири рази вгадати одну цифру із десяти. Але не підряд.

Ну чи ще якось. Загалом потрібно дізнатися, скільки у мене було варіантів числової комбінації, з якої складався пін-код картки. Допоможіть, люди добрі! Тільки, будь ласка, допомагаючи, не починайте одразу писати, що варіантів цих 9999 (вчора таке всім спадало на думку спочатку), тому що це ж дурниці – адже в тому ракурсі, який нас хвилює, число 1234, число 3421, число 4312 і так далі є одним і тим же! Ну і так, цифри можуть повторюватися, адже буває пін-код 1111 або там, наприклад, 0007. Можна уявити замість пін-коду номер машини. Припустимо, яка можливість вгадати всі однозначні цифри, з яких складається номер машини? Або щоб взагалі прибрати теорію ймовірності – зі скількох числових комбінацій мені потрібно було вибрати одну?

Будь ласка, підкріпіть свої відповіді та міркування якими-небудь точними формулами, бо ми вчора і так мало не збожеволіли. Заздалегідь усім дякую!

PS Одна розумна людина, програміст, художник і винахідник, щойно дуже вірно підказав правильне вирішення проблеми, подарувавши мені кілька хвилин прекрасного настрою . більше на її місці хвилювало не питання «яка ймовірність», а питання «чого я звертаю увагу на всі ці цифри?» Загалом навіть нічого додати:)

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

Стаття “Основні типи задач комбінаторики”

Пропонована стаття є маленьким науковим посібником, збірником задач з комбінаторики з розв’язками. Ним можуть користуватися як учні, так і вчителі. Задачі різного характеру. Обсяг – від 6 класу до 11-го. Надіюсь, що моя праця принесе користь учням у вивченні комбінаторики.

ОСНОВНІ ТИПИ ЗАДАЧ КОМБІНАТОРИКИ

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

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

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

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

Комбінаторика стає наукою лише в ХVIII столітті в період, коли виникла теорія ймовірностей. Щоб розв’язувати теоретично – ймовірнісні задачі, треба було вміти підраховувати число різних комбінацій, підлеглим тим чи іншим умовам. Після перших робіт, виконаних в XVI столітті італійськими вченими Дж. Кардано, Н. Тартальє і Г. Галілеєм, такі задачі вивчали французькі математики Б. Паскаль і П. Ферма. Першим розглядав комбінаторику як самостійну гілку науки німецький філософ і математик Г. Лейбніц, який опублікував у 1666 р. роботу “ Про мистецтво комбінаторики”, в якій вперше появляється термін “комбінаторний”. Чудові відкриття в області комбінаторики належать Л.Ейлеру. До комбінаторних задач мали інтерес і математики, що займалися складанням і розгадуванням шифрів, вивчанням стародавніх письменностей. Зараз комбінаторика застосовується в багатьох областях науки: в біології, де вона застосовується для вивчення складу білків та ДНК, в хімії, в механіці складних споруд і т.д.

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

1. ОСНОВНА ЛЕМА КОМБІНАТОРИКИ

Лема: Якщо множина А складається з n елементів, а множина В – з m елементів, то можна скласти рівно n∙m пар виду (a_i,b_j), де а_і Є А, b_j Є В.

Твердження леми і наслідок можна розуміти таким чином: якщо для заповнення першого місця послідовності елементом з множини А₁ маємо n₁ можливостей, другого місця – елементом з множини А₂ – n₂ можливостей, … ,k-го місця – елементом з множини А_к – n_k можливостей, то всього таких послідовностей буде n₁n₂…n_k.

Задача 1. На паралельних прямих а і в розміщено n і m точок відповідно. Скільки існує відрізків, що з’єднують точки прямих а і в ?

Розв’язання: Нехай а₁, а₂, …, а_n – точки на прямій а, в₁, в₂, …,в_m— точки на прямій в. Для кожної точки а_і матимемо m відрізків, що сполучають цю точку з точками прямої в. Кожному відрізку відповідатиме пара (а_і ,в_j). За основною лемою комбінаторики таких пар буде nm.

Задача 2. На сторонах АВ і ВС трикутника АВС взято точки

P₁, P₂, … , P_n і Q₁, Q₂, …. , Q_m відповідно. Проведено відрізки AQ_j і CP_i . Скільки будемо мати точок перетину цих відрізків ? На скільки частин поділиться трикутник цими відрізками ?

Задача 3. У просторі ( або на площині ) взято n синіх точок , m червоних та k зелених точок. Скільки існує відрізків з кінцями різного кольору ?

Розв’язання: Не обмежуючи загальності, розмістимо точки на паралельних прямих a, b, с відповідно по n, m, k штук. За результатами задачі 1 кількість відрізків дорівнюватимете nm+mk+kn.

Задача 4. Світланці на день народження подарували 4 плюшевих іграшки, 2 м’ячі і 5 ляльок (іграшки, м’ячі і ляльки різні ). Мама поклала все це у велику коробку. Скількома способами Світлана може дістати набір з 1 іграшки, 1 м’яча і 1 ляльки ?

Розв’язання: Світланка має 4 варіанти вибору плюшевих іграшок, 2 варіанти вибору м’ячів та 5 варіантів вибору ляльок. Тому загальна кількість варіантів за наслідком з леми буде дорівнювати 4∙2∙5=40 варіантів.

Задача 5. Скільки парних двозначних чисел можна скласти з цифр 0,2,3,6,7,9 ?

Розв’язання: Для вибору першої цифри є 5 можливостей (цифри 2,3,6,7,9. Нуль на першому місці стояти не може). Для вибору другої цифри числа є 3 можливості (цифри 0,2,6 – ознака по-дільності на 2).

Задача 6. Скільки існує чотирицифрових чисел, що діляться на 5, записаних за допомогою цифр: а) 1,2,3, … ,8,9; б) 0,1,…,9 ?

Розв’язання: а) Для запису перших трьох цифр числа на місце кожної цифри є по 9 можливостей. На місце останньої цифри – одна можливість – цифра 5. Остаточно матимемо 9∙9∙9∙1= 729 чисел; б) 9∙10∙10∙2=1800 чисел.

Задача 7. Скільки чотирицифрових натуральних чисел, які діляться на 25, можна записати, використавши цифри

Розв’язання: Ознака подільності на 25: запис числа повинен закінчуватися парою цифр 00, 25, 50, 75. У нашому випадку можливі тільки пари 25 і 75. Тому будемо мати 7∙7∙2∙1=98 чисел.

Задача 8. Міс Марпл, розслідуючи вбивство, замітила від’їжджаюче від дому містера Девідсона таксі. Вона запам’ятала першу цифру 2 номера машини. В місті номери машин були чотирьохзначними і складалися з цифр 1,2,3,4,5. Після цифр йшли дві букви з множини букв A,B,C,D. Скількох водіїв у найгіршому випадку їй прийдеться опитати, щоб знайти справжнього злочинця

Відповідь: (1∙5∙5∙5)∙(4∙4)=2000 водіїв.

2. ПЕРЕСТАНОВКИ

Задача 9. Нехай М – множина, що складається з n елементів : М=a₁,a₂, … , a_n>. Скількома способами можна лінійно упорядкувати цю множину, тобто розмістити її елементи один за одним, утворити з них n-членну послідовність, в якій жодний елемент з М не повторюється ?

Розв’язання: Для вибору першого члена послідовності маємо n можливостей ( будь-який елемент з М ). Незалежно від того, який елемент з М взято як перший член послідовності, для вибору її другого члена у нашому розпорядженні буде (n-1) можливостей ( будь-який елемент з М, крім використаного на першому кроці ). Взагалі, якщо перші k членів послідовності вже вибрано, то для вибору її (k+1)-го члена буде (n-k) можливостей. Тому згідно з наслідком основної леми комбінаторики ( комбінаторного правила множення ) з елементів множини М всього можна побудувати n(n1)(n-2)∙…∙3∙2∙1 різних n-членних послідовностей. Цей добуток коротко позначають через n!.

Лінійно упорядковані скінченні множини називаються перестановками. Тому останній результат можна сформулювати так: з n елементів можна утворити n! різних перестановок. Число всіх перестановок будемо позначати символом Р_n. Отже,

Задача 10. Олександр, Іван, Петро, Денис, Оля та Настя часто ходять в кафе. Кожен раз, обідаючи там, вони розсаджуються порізному. Скільки днів друзі можуть це зробити без повтору ?

Відповідь: 6!=6∙5∙4∙3∙2∙1=720 днів (приблизно два роки . ).

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

Розв’язання: Загальне число перестановок дорівнює 10!. Але відношення сусідства буде зберігатися, якщо усі 10 чоловік разом встануть і пересядуть на місце, наприклад, правого сусіда. Таких пересадок можна зробити 10 разів, поки люди не сядуть на ті ж самі місця. Так само сусіди будуть ті ж самі при симетричному відображенні. Тому всього способів (10!⁄10): 2 = 9!:2 = 181440.

Відповідь: 181440 способів.

Задача 12. Скількома способами можна посадити за круглий стіл 5 чоловіків і 5 жінок так, щоб ніякі дві особи однієї статі не сиділи поряд ?

Розв’ язання: Перенумеруємо місця від 1 до 10-ти. Для жінок і чоловіків можна вибрати місця двома способами – місця з парними номерами, або місця з непарними номерами. Після цього чоловіків на обраних місцях можна посадити 5! способами. На інших місцях 5! способами можна посадити жінок. Всього 2∙(5!) 2

способів.

Відповідь: 2∙(5!) 2 = 28800 способів.

Задача 13. На книжній полиці n=10 книжок. Скількома способами можна переставити книги на полиці так, щоб m=3 виділених книг були поряд в будь-якому порядку ?

Розв’язання: Зв’яжемо m виділених книг в групу і будемо рахувати їх як одну книгу. Всього перестановок із зв’язаними книгами буде (n-m+1)!. Так як зв’язані між собою m книг теж можна переставити m! способами, то остаточно матимемо (nm+1)!m! способів.

Відповідь: (n-m+1)!m! способів. Якщо n=10, m=3, то

3. ЧИСЛО РОЗМІЩЕНЬ З n ЕЛЕМЕНТІВ ПО k

Задача 14. Нехай М=a₁, a₂,…,a_n>. Лінійно впорядковані kелементні підмножини (або послідовності, 0≤k≤n) множини М називають k-розміщенням елементів цієї множини. Число всіх таких розміщень позначають 𝐴 𝑘 _𝑛 . Чому дорівнює це число ?

Розв’язання: Будь-яке k-розміщення (α₁,α₂,…,α_k) можна дістати за допомогою такої послідовної процедури: спочатку вибираємо з множини М перший елемент k-розміщення α₁ (це можна зробити n різними способами), потім вибираємо елемент α₂ (n-1 можливостей), потім α₃ (n-2 можливостей) і, нарешті, α_k (nk+1 мож-ливостей). Згідно з комбінаторним правилом множення в підсумку матимемо:

Щоб ця формула була правильною для k=n, вважаємо 0!=1.

Задача 15. Скількома способами можна скласти трьохкольоровий прапор, якщо є матерії 8-ми різних кольорів ?

Розв’язання: Оскільки на прапорі використовуються різні кольори і порядок їх важливий, то кожному прапору відповідає одне з розміщень з 8 елементів по 3. Число всіх можливих прапорів вказаного виду дорівнює А

Задача 16. Скільки є п’ятицифрових чисел, записаних за допомогою цифр а) 1,2,…,9 ; б) 0,1,2,…,9 , якщо цифри числа не повторюються ?

Розв’язання: а) на першому місці запису п’ятицифрового числа може стояти одна з дев’яти даних цифр, на другому – одна з восьми і т.д. Тому у відповіді матимемо число розміщень з 9 елементів по 5: А у випадку а), але враховуючи те, що нуль не може бути першим у запису числа, отримаємо таку відповідь: 9∙9∙8∙7∙6 = 27216 чисел.

Цю ж саму відповідь можна отримати, міркуючи так:

Знайдемо всі розміщення 5-ти цифр з 10-ти : А ₁₀ 5 — усі п’ятизначні числа, враховуючи на першому місці нуль. Відкинемо тепер ті, на першому місці у яких є нуль. Їх буде А 4 ₉ . Матимемо:

Зупинимося ще на цій задачі, змінивши її умову. Нехай цифри числа можуть повторювати-ся. Тоді у випадку а) на кожному місці цифр числа може стояти будь-яка з дев’яти цифр, тому будемо мати 9∙9∙9∙9∙9=9 5 =59049 чисел.

Будь-який впорядкований набір k елементів з множини М=a₁,a₂,…,a_n> називається розміщенням з повтореннями.

Число різних розміщень з повтореннями дорівнює

У випадку б) попередньої задачі з умови, що цифри числа

Задача 17. В кабінеті завідуючого ювелірним магазином є код, що складається з двох різних голосних букв українського алфавіту (не йотованих), за якими слідують три різні цифри. Скільки варіантів у найгіршому випадку прийдеться перебрати злодію, щоб добути коштовності, які там зберігаються ?

Розв’язання: Голосних не йотованих букв в українському алфавіті 6, цифр – 10. Записати дві різні букви з шести можна 𝐴 2 ₆ способами, три різні цифри з десяти 𝐴₁₀ 3 способами. За комбінаторним правилом множення матимемо:

Відповідь: 21600 варіантів.

Зокрема, якби в задачі не наголошувалось про те, що цифри і букви різні, було б 𝐴 =36000 варіантів перебору.

Задача 18. В студентському гуртожитку в одній кімнаті живуть троє студентів. В них є 6 чашок, 8 блюдець і 10 ложечок (всі приналеж-ності відрізняються одне від одного). Скількома способами хлопці можуть накрити стіл для чаювання ?

Розв’язання: 1 спосіб. Для одного з студентів з 6 чашок, 8 блюдець і 10 ложечок існує 6∙8∙10 способів вибору. Після того, як для цього студента набір готовий, для другого студента є 5∙7∙9 способів вибору. І нарешті, третій студент матиме 4∙6∙8 способів вибору. За комбінаторним правилом множення матимемо

(6∙8∙10)(5∙7∙9)(4∙6∙8) способів накриття столу для чаювання.

Розв’язання: 2 спосіб. 6 чашок між трьома студентами можна розподілити А 3 ₆ способами, 8 блюдець А 3 ₈ способами, 10 ложечок

А ₁₀ 3 спо-собами. За правилом добутку матимемо

4. ЧИСЛО КОМБІНАЦІЙ З n ЕЛЕМЕНТІВ ПО k

Позначимо через С 𝑘 _𝑛 кількість невпорядкованих kелементних послідовностей (підмножин) n-елементної множини(0≤k≤n). Оскільки кожну k-елементну множину можна впорядку-вати k! способами, то

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

Приклад. Задача (1). Скільки різних тризнач-них чисел можна записати за допомогою цифр 1,2,3,4,5 ? Відповідь: А

Задача (2). На площині є 5 точок, жодні три з них не лежать на одній прямій. (Такі точки дуже зручно розміщати на колі ). Скільки існує трикутників з вершинами у цих точках ?

Перенумеруємо точки номерами 1,2,3,4,5. Кожному трикутнику ставиться у відповідність трійка чисел. Наприклад, трикутник (2,4,5). Цей трикутник можна назвати і інакше, а саме: (2,5,4), (5,2,4), (5,4,2), (4,2,5), (4,5,2). Усі ці 3!=6 назв є тим самим трикутником, хоча в задачі (1) числа 245, … , 452 різні. Тому в результаті матимемо С 3 ₅ = А 3 ₅ /3! = = 10 трикутників.

Отже, у числі 𝐴 𝑘 _𝑛 порядок елементів послідовності чисел важливий, у числі С 𝑘 _𝑛 – порядок не важливий (. ).

Саме на число комбінацій існує найбільше задач, особливо геометричного змісту. На дея-ких з них зараз і зупинимося.

Задача 19. Скільки діагоналей у опуклого n-кутника ?

Розв’язання: Не обмежуючи загальності, припустимо, що nкутник можна вписати в коло. Отже, n вершин многокутника належать колу. Дізнаємося, скільки відрізків сполучають ці точки. Перенумеруємо точки номерами 1,2,…,n. Кожному відрізку відповідатиме пара (i,j)=(j,i). Тому кількість відрізків буде 𝐶_𝑛 2 =

. Відкинемо тепер n відрізків – сторони многокутника.

Кількість діагоналей даного многокутника дорівнюватиме

Задача 20. На колі взято n точок і сполучено їх відрізками так, що жодні три з них не перетинаються в одній точці. Скільки існує точок перети-ну цих відрізків ?

Розв’язання: Перенумеруємо точки кола. Кожній точці перетину двох відрізків ставиться у відповідність четвірка чисел (s,t,u,v), яка для цієї точки єдина. Так як порядок чисел s, t, u, v не суттєвий, маємо число комбінацій з n елементів по 4.

Задача 21. У просторі взяли n червоних (Ч) і m синіх (С) точок, причому жодні 4 з них не лежать в одній площині.

1) Скільки є відрізків типу (СЧ) – один кінець синя точка, другий – червона ?

2) Скільки є відрізків типу а)(СС), б)(ЧЧ) ?

3) Скільки є трикутників типу а)(ССС), б)(ЧЧЧ), в)(ССЧ), г)(СЧЧ) ?

4) Скільки є тетраедрів типу а)(СССС), б)(СССЧ), в)(ССЧЧ) ?

в) Для кожної червоної вершини існує 𝐶_𝑚 2 про-тилежних сторін із синіми кінцями. Тому маємо 𝐶_𝑚 2 трикутників. г) m 𝐶_𝑛 2 трикутників.

Задача 22. На одній стороні трикутника взяли n точок, на другій – m точок і на третій k точок, причому жодна з них не збігається з вершинами трикутника.

Скільки є трикутників з вершинами в цих точках ? Скільки є чотирикутників з вершинами в цих точках ?

Розв’язання: 1) Всього комбінацій з n+m+k точок по три є 𝐶_𝑛 3 _+𝑚+𝑘 . Але серед цих точок жодні три не повинні лежати на одній прямій. Тому ми повинні виключити з загальної кількості комбінацій числа 𝐶_𝑛 3 , 𝐶_𝑚 3 , 𝐶_𝑘 3 − комбінації точок , що лежать на сторонах трикутника. Отримаємо результат: S₁ = 𝐶_𝑛 3 _+𝑚+𝑘 – 𝐶_𝑛 3 –

𝐶_𝑚 3 – 𝐶_𝑘 3 . ( Зрозуміло, якщо j≤2, то 𝐶_𝑗 3 = 0 ). Можна міркувати поіншому. Підрахуємо трикутники з вершинами на кожній стороні даного трикутника. Їх буде mnk. Зафіксуємо одну вершину на

стороні (n). З стороною (m) матимемо 𝐶_𝑚 2 , а з стороною (k) – 𝐶_𝑘 2 трикутників. Так як на стороні (n) n точок, то всього буде n( 𝐶 2 _𝑚 + 𝐶_𝑘 2 ) трикутників. Аналогічно для сторін (m) і (k) матимемо ще m( 𝐶_𝑛 2 + 𝐶_𝑘 2 ) i k( 𝐶_𝑛 2 + 𝐶_𝑚 2 ) трикутників. Всього тепер

Числа S₁ i S₂ рівні між собою, що можна перевірити за допомогою елементарних перетворень.

Задача 23. В ювелірну майстерню привезли 6 смарагдів, 9 алмазів та 7 сапфірів. Ювеліру замовили браслет, в якому 3 смарагди, 5 алмазів і 2 сапфіри. Скількома способами він може вибрати каміння на браслет ?

Задача 24. 20 карток для гри в лото роздаються чотирьом гравцям, по 5 карток кожному. Скількома способами можна роздати ці картки ?

Розв’язання: Першому гравцю, який має отримати 5 карток з 20-ти є С 5 ₂₀ можливостей вибору. Для другого гравця треба вибрати 5 карток з 15-ти тих, що залишились, тобто С ₁₅ 5 способами, для третього гравця будемо мати С ₁₀ 5 варіантів вибору, а для четвертого є 1=С 5 ₅ варіант вибору. За комбінаторним правилом множення 20 карток чотирьом гравцям можна роздати

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

Розв’язання: Розв’яжемо рівняння: 𝐶_𝑛 2 =153, n 2 -n-306=0, n=18.

Задача 26. Довести, що = 2 n .

Доведення: Нехай М=a₁,a₂,…,a_n>. Будь-якій підмножині Р, що належить М поставимо у відповідність послідовність довжини n, місця в якій зайняті нулем або одиницею, причому, якщо і-й елемент належить множині Р, на і-му місці стоїть одиниця, якщо ні – то нуль. Наприклад, підмножині Р₁=a₁,a₂,a₄> відповідає послідовність . Таким чином між множиною таких послідовностей та множиною усіх підмножин існує взаємнооднозначна відповідність. Зокрема порожній множині відповідає послідовність з усіх нулів, самій множині М – послідовність з одиниць. Оскільки для заповнення кожного місця послідовності маємо 2 можливості, то відповідно з комбінаторним правилом множення отримуємо, що число послідовностей такого типу, і отже, число всіх підмножин дорівнює ⏟ = 2 n .

З іншого боку, існує С 0 _𝑛 підмножин, що не містять жодного елемента, С 1 _𝑛 підмножин з одним елементом, … , С 𝑘 _𝑛 підмножин, що містять k елементів, і т. д. Тому існує всього 𝐶_𝑛 0 + 𝐶_𝑛 1 + 𝐶_𝑛 2 +…+ 𝐶_𝑛 𝑛 підмножин. Отже, 2 n = ∑ 𝑛 _𝑘=0 𝐶_𝑛 𝑘 .

Задача 27. Відомо, що крокодил має не більше 68 зубів. Довести, що серед 16 17 крокодилів може не знайтися двох крокодилів з одним і тим самим набором зубів.

Доведення: Підрахуємо максимальне число крокодилів з різними наборами зубів. Їх число дорівнює числу всіх підмножин у 68-елементній множині, тобто дорівнює 2 68 =16 17 . Ясно, якщо крокодилів більше 16 17 , то серед них обов’язко-во знайдуться по крайній мірі два з одним і тим самим набором зубів.

Задача 28. Букви азбуки Морзе представ-ляють собою набір точок і тире. Скільки букв може бути в азбуці Морзе, якщо буква не повинна мати більше 4-х знаків ?

Розв’язання: Різних букв, у запису яких вико-ристовуються k символів, буде стільки, скільки існує підмножин k-елементної множини. Їх, як відомо, 2 k . За умовою задачі загальна кількість букв дорівнюватиме 2+2 2 +2 3 +2 4 = 30.

5. ПЕРЕСТАНОВКИ З ПОВТОРЕННЯМ

Якщо розглядати впорядковані k-елементні підмножини (послідовності) з множини М, то отримаємо перестановки з повторенням.

Приклад 1. Скількома способами можна переставити букви слова МАМА так, щоб отримати різні “слова”. Можливі перестановки такі: ММАА, МААМ, ААММ, АМАМ, АММА.

Приклад 2. Скільки існує п’ятизначних чисел, що складаються з двох одиниць, двох двійок і однієї трійки ? Попробуємо записати всі ці числа.

11223 22113 12213 21123 12123 21213

11232 22131 12231 21132 12132 21231

11322 22311 12321 21312 12312 21321

13122 23211 13221 23112 13212 23121

31122 32211 31221 32112 31212 32121

Якби повтору цифр не було, то ми б отримали 5!=120 чисел. В нашому випадку ми отримали в 4 рази менше чисел. Чому ? Помінявши місцями в будь-якому числі з нашого прикладу дві одиниці або дві двійки, ми отримаємо одне й те ж число. Кількість перестановок з двох елементів дорівнює 2!=2. Тих елементів, під час перестановки яких число не змінюється – дві пари – (1,1) і (2,2). Тому загальна кількість перестановок буде у 2!∙2! рази менше, тобто .

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

Нехай М=a₁,a₂,…,a_n>—непорожня множина з n елементів, і і₁,і₂,…,і_n – натуральні числа такі, що їх сума дорівнює певному числу k. Кожний упорядкований набір k чисел, що містить в собі елемент a_j рівно i_j раз (1≤j≤n), називається перестановкою множини М з повторенням.

Примітка: При і₁=і₂=…=і_n=1, отримаємо перестановки множини з n елементів.

Число Р_к(і₁,і₂,…,і_n) різних перестановок множини М з повторенням дорівнює

У прикладі 1 М = , і₁=2 – двічі зустрічається буква М, і₂=2 – двічі зустрічається буква А. Р₄(2,2) = = 6.

У прикладі 2 М=, і₁=2 – дві цифри 1, і₂=2 – дві цифри 2, і₃=1 – одна трійка.

Примітка: Число комбінацій 𝐶_𝑛 𝑘 є частинний випадок числа перестановок з повторенням P_n(k₁,k₂), де k₁=k, k₂ = n-k.

Задача 29. Скільки існує перестановок букв слова МАТЕМАТИКА ?

Розв’язання: Дане слово має 10 літер. Тому k=10. Літера М зустрічається 2 рази. і₁=2. Літера А зустрічається 3 рази, і₂=3. Літера Т зустрічається 2 рази, і₃=2. Інші літери – Е,И,К – по одному разу.

Відповідь: 151200 перестановок.

Задача 30. Скількома способами можна розселити 8 учнів по трьом кімнатам – одномісній, тримісній, чотиримісній ?

Розв’язання: В тримісній кімнаті три учні можуть зайняти місця 3! різними способами, не виходячи з неї. Аналогічно, в чотиримісній кімнаті чотири учні можуть зайняти місця 4! різними способами, не виходячи з неї. Тому загальна кількість способів розселення учнів по кімнатам дорівнює Р₈(1,3,4) = = 280.

Задача 31. Скількома способами можна розподілити 10 спеціалістів по чотирьом цехам №1, №2, №3, №4 так, щоб в них попали відповідно 1, 2, 3, 4 спеціаліста ? Відповідь: Р₁₀(1,2,3,4) = = 12600.

Задача 32. Скільки слів можна скласти з 5-ти букв А і не більше, ніж трьох букв Б ?

Задача 33. Скільки існує 10-значних чисел, у яких сума цифр дорівнює 3 ?

Розв’язання: Зафіксуємо на першому місці цифру 1, потім 2, потім 3. Можливі випадки:

1 11⏟ ⏟0000000 – Р₉(2,7) перестановок

1 ⏟2 ⏟00000000 – Р₉(1,8) перестановок

2 ⏟1 ⏟00000000 – Р₉(1,8) перестановок

3000000000 – одне число.

6. КОМБІНАЦІЇ З ПОВТОРЕННЯМ З n ЕЛЕМЕНТІВ ПО k

Нехай маємо n-елементну множину М. Розглянемо невпорядковану підмножину (послідовність) з k елементів, які можуть повторюватися. До k-елементної послідовності (наприклад, до b,c,b з М = ) припишемо всі n елементів множини М і отримані n+k елементів запишемо по порядку, ставлячи однакові елементи поряд (a,b,b,b,c,c,d,e). Потім підмножини однакових елементів розділимо n-1 рисочками (a|bbb|cc|d|e). Нарешті, замінимо всі елементи між рисочками на точки (∙|∙∙∙|∙∙|∙|∙). Таким чином ми ставимо у відповідність k-елементній послідовності розстановку n-1 рисочок в n+k-1 проміжках. І навпаки, по кожній такій розстановці однозначно відновлюється відповідна їй kпослідовність. Наприклад,

Всього існує 𝐶_𝑛 𝑛 ₊ − _𝑘 1 ₋₁ = 𝐶_𝑛 𝑘 _+𝑘−1 способів розстановки n-1 рисочок на n+k-1 місцях. Отже, і k-послідовностей з повтореннями з множини М існує стільки ж. Число комбінацій з повтореннями позначатимемо 𝑪 𝒌 _(𝒏) . Отже,

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

Розв’язання: При киданні двох гральних кубиків може випасти невпорядкована пара (i,j) чисел, 1≤i,j≤6. Маємо число

комбінацій з повторенням С

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

Розв’язання: Кожному способу розміщення відповідає 5елементна послідовність з множини М, яка має три типи елементів.

(Передбачається, що місткість урн необмежена). Тому будемо мати число комбінацій з повтореннями: С 5 ₍₃₎ = С 5 ₇ = 21 різних способів.

Задача 36. Скількома способами можна розмістити n однакових кульок в m різних урнах за наступними умовами:

Розв’язання: 1). Покладемо в кожну з урн по кульці. Інші

Задача 37. Скількома способами можна роз-містити 5 білих, 6 чорних і 7 синіх кульок в 4 різні урни ?

Розв’язання: Білі кульки ми можемо розмістити в урни С 5 ₍₄₎ способами, чорні – С 6 ₍₄₎ способами і сині – С 7 ₍₄₎ способами. Але оскільки розміщення кульок різного кольору не залежать одне від одного, то, за комбінаторним правилом множення, загальна

кількість способів дорівнює С

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

Розв’язання: Для того, щоб характеризувати число, що задовольняє умові задачі, достатньо сказати, скільки в цьому числі зустрічається одиниць, двійок, … , дев’яток. Інтерпретувати цю задачу можна так: маємо множину М = і nпослідовність з повторен-нями. Скільки існує способів вибору ?

Задача 39. В гості запрошені 4 різні пари близнюків. Скількома способами можна вибрати двох з восьми гостей ?

Розв’язання: кожному способу вибору відповідає двохелементна послідовність з множини М, яка має 4 типи елементів.

Задача 40. Довести, що кількість різних розв’язків рівняння х₁+х₂+…+х_m = n в натуральних числах дорівнює 𝐶_𝑛 𝑚 ₋ − ₁ 1 .

Доведення: Розіб’ємо число n на суму n одиниць. Нехай одиниці – кульки, а числа х_і – урни. З умови задачі жодна урна не може бути порожньою. Тому будемо мати результат задачі 36(1).