Механічна коробка: пристрій, види, особливості. Шанси на розклад з довгим ланцюжком

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

Чим будемо займатись? У вузькому значенні комбінаторика - це підрахунок різних комбінацій, які можна скласти з деякої множини дискретнихоб'єктів. Під об'єктами розуміються якісь відокремлені предмети чи живі істоти – люди, звірі, гриби, рослини, комахи тощо. При цьому комбінаторику зовсім не хвилює, що безліч складається з тарілки манної каші, паяльника та болотяної жаби. Принципово важливо, що ці об'єкти піддаються перерахуванню – їх три (Дискретність)і суттєво те, що серед них немає однакових.

З безліччю розібралися, тепер про комбінації. Найпоширенішими видами комбінацій є перестановки об'єктів, їх вибірка з множини (поєднання) і розподіл (розміщення). Давайте прямо зараз подивимося, як це відбувається:

Перестановки, поєднання та розміщення без повторень

Не лякайтеся малозрозумілих термінів, тим більше деякі з них дійсно не дуже вдалі. Почнемо з хвоста заголовка – що означає « без повторень»? Це означає, що в даному параграфі будуть розглядатися множини, які складаються з різнихоб'єктів. Наприклад, … ні, кашу з паяльником і жабою пропонувати не буду, краще щось смачніше =) Уявіть, що перед вами на столі матеріалізувалося яблуко, груша і банан (за наявності таких ситуацію можна змоделювати і реально). Викладаємо фрукти зліва направо у такому порядку:

яблуко / груша / банан

Питання перше: Скільки способами їх можна переставити?

Одна комбінація вже записана вище та з іншими проблемами не виникає:

яблуко / банан / груша
груша / яблуко / банан
груша / банан / яблуко
банан / яблуко / груша
банан / груша / яблуко

Разом: 6 комбінацій або 6 перестановок.

Добре, тут не склало особливих труднощів перерахувати всі можливі випадки, але як бути, якщо предметів більше? Вже із чотирма різними фруктами кількість комбінацій значно зросте!

Будь ласка, відкрийте довідковий матеріал (методичку зручно роздрукувати)та у пункті № 2 знайдіть формулу кількості перестановок.

Жодних мук – 3 об'єкти можна переставити способами.

Питання друге: Скільки способами можна вибрати а) один фрукт, б) два фрукти, в) три фрукти, г) хоча б один фрукт?

Навіщо обирати? Так нагуляли апетит у попередньому пункті – для того, щоб з'їсти! =)

а) Один фрукт можна вибрати, очевидно, трьома способами - взяти або яблуко, грушу або банан. Формальний підрахунок проводиться за формулі кількості поєднань:

Запис у разі слід розуміти так: «скількими способами можна вибрати 1 фрукт з трьох?»

б) Перерахуємо всі можливі поєднання двох фруктів:

яблуко та груша;
яблуко та банан;
груші та банан.

Кількість комбінацій легко перевірити за тією самою формулою:

Запис розуміється аналогічно: «скільки можна вибрати 2 фрукти з трьох?».

в) І, нарешті, три фрукти можна вибрати єдиним способом:

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

г) Скільки способами можна взяти хоча б одинфрукт? Умова «хоча б один» передбачає, що нас влаштовує 1 фрукт (будь-який) або 2 будь-яких фрукти або всі 3 фрукти:
способами можна вибрати хоча б один фрукт.

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

Для відповіді на наступне запитання мені потрібні два добровольці… …Ну що ж, якщо ніхто не хоче, тоді викликатиму до дошки =)

Питання третє: Скільки способами можна роздати по одному фрукту Даші та Наташі?

Для того, щоб роздати два фрукти, спочатку потрібно їх вибрати. Відповідно до пункту «бе» попереднього питання, зробити це можна засобами, перепишу їх заново:

яблуко та груша;
яблуко та банан;
груші та банан.

Але комбінацій зараз буде вдвічі більше. Розглянемо, наприклад, першу пару фруктів:
яблуком можна пригостити Дашу, а грушею – Наташу;
або навпаки – груша дістанеться Даші, а яблуко – Наталці.

І така перестановка можлива кожної пари фруктів.

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

Способами можна вибрати 1 юнака;
способами можна вибрати 1 дівчину.

Таким чином, одного юнака іодну дівчину можна вибрати: методами.

Коли з кожної множини вибирається по 1 об'єкту, то справедливий наступний принцип підрахунку комбінацій: « коженоб'єкт з однієї множини може скласти пару з кожнимоб'єктом іншої множини».

Тобто Олег може запросити на танець будь-яку з 13 дівчат, Євген – теж будь-яку з тринадцяти, і аналогічний вибір має решта молодих людей. Разом: можливі пари.

Слід зазначити, що у цьому прикладі немає значення «історія» утворення пари; однак якщо взяти до уваги ініціативу, то кількість комбінацій треба подвоїти, оскільки кожна з 13 дівчат також може запросити на танець будь-якого юнака. Все залежить від умови того чи іншого завдання!

Схожий принцип справедливий і для складніших комбінацій, наприклад: скількома способами можна вибрати двох юнаків ідвох дівчат для участі у сценці КВК?

Союз Інедвозначно натякає, що комбінації необхідно перемножити:

Можливі групи артистів.

Іншими словами, кожнапара юнаків (45 унікальних пар) може виступати з будь-якийпарою дівчат (78 унікальних пар). А якщо розглянути розподіл ролей між учасниками, то комбінацій буде ще більше. …Дуже хочеться, але все-таки утримаюсь від продовження, щоб не прищепити вам огиду до студентського життя =).

Правило множення комбінацій поширюється і на більшу кількість множників:

Завдання 8

Скільки існує трицифрових чисел, які діляться на 5?

Рішення: для наочності позначимо це число трьома зірочками: ***

У розряд сотеньможна записати будь-яку з цифр (1, 2, 3, 4, 5, 6, 7, 8 чи 9). Нуль не годиться, тому що в цьому випадку число перестає бути тризначним.

А ось у розряд десятків(«посередині») можна вибрати будь-яку з 10 цифр: .

За умовою, число має ділитися на 5. Число ділиться на 5, якщо воно закінчується на 5 або на 0. Таким чином, у молодшому розряді нас влаштовують 2 цифри.

Отже, існує: трицифрових чисел, які діляться на 5.

При цьому твір розшифровується так: «9 способами можна вибрати цифру в розряд сотень і 10 способами вибрати цифру в розряд десятків і 2 способами в розряд одиниць»

Або ще простіше: « кожназ 9 цифр у розряді сотенькомбінується з кожноюз 10 цифр розряду десятків і з кожноюз двох цифр у розряд одиниць».

Відповідь: 180

А зараз…

Так, мало не забув про обіцяний коментар до завдання № 5, в якому Борі, Дімі та Володі можна здати за однією картою способами. Множення тут має той самий сенс: способами можна витягти 3 карти з колоди І в кожнійвибірці переставити їх засобами.

А тепер завдання для самостійного вирішення… зараз придумаю щось цікавіше, …нехай буде про ту ж російську версію блекджека:

Завдання 9

Скільки існує виграшних комбінацій з 2 карток при грі в «очко»?

Для тих, хто не знає: виграє комбінація 10 + ТУЗ (11 очок) = 21 очко і, давайте вважатимемо виграшною комбінацію з двох тузів.

(Порядок карт у будь-якій парі не має значення)

Коротке рішення та відповідь наприкінці уроку.

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

Настав час закріпити пройдений матеріал парою солідних завдань:

Завдання 10

У Васі вдома живуть 4 коти.

а) скільки можна розсадити котів по кутах кімнати?
б) скільки можна відпустити гуляти котів?
в) Скільки способами Вася може взяти на руки двох котів (одного на ліву, іншого - на праву)?

Вирішуємо: по-перше, знову слід звернути увагу на те, що в задачі йдеться про різнихоб'єктах (навіть якщо коти – однояйцеві близнюки). Це дуже важлива умова!

а) Мовчання котів. Цю кару зазнають відразу всі коти
+ важливе їх розташування, тому тут мають місце перестановки:
способами можна розсадити котів по кутах кімнати.

Повторюся, що з перестановках має значення лише кількість різних об'єктів та його взаємне розташування. Залежно від настрою Вася може розсаджувати тварин півколом на дивані, ряд на підвіконні і т.д. – перестановок у всіх випадках буде 24. Бажаючі можуть для зручності уявити, що коти різнокольорові (наприклад, білий, чорний, рудий та смугастий) та перерахувати всі можливі комбінації.

б) Скільки можна відпустити гуляти котів?

Передбачається, що коти ходять гуляти тільки через двері, при цьому питання має на увазі байдужість щодо кількості тварин – на прогулянку можуть вийти 1, 2, 3 або всі 4 коти.

Вважаємо всі можливі комбінації:

Способами можна відпустити гуляти одного кота (будь-якого з чотирьох);
способами можна відпустити гуляти двох котів (варіанти перерахуйте самостійно);
способами можна відпустити гуляти трьох котів (якийсь один із чотирьох сидить удома);
способом можна випустити всіх котів.

Напевно, ви здогадалися, що отримані значення слід підсумувати:
способами можна відпустити гуляти котів.

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

в) Скільки способами Вася може взяти на руки двох котів?

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

Другий варіант вирішення: способами можна вибрати двох котів іспособами посадити кожнупару на руки:

Відповідь: а) 24, б) 15, в) 12

Ну і для очищення совісті щось конкретніше на збільшення комбінацій. Нехай у Васі додатково живе 5 котів =) Скільки способами можна відпустити гуляти 2 котів і 1 кішку?

Тобто, з кожноюпарою котів можна випустити кожнукішку.

Ще один баян для самостійного вирішення:

Завдання 11

У ліфт 12-поверхового будинку сіли 3 пасажири. Кожен, незалежно від інших, з однаковою ймовірністю може вийти на будь-якому (починаючи з 2-го) поверсі. Скількими способами:

1) пасажири можуть вийти на тому самому поверсі (Порядок виходу не має значення);
2) дві людини можуть вийти на одному поверсі, а третя – на іншому;
3) люди можуть вийти різних поверхах;
4) пасажири можуть вийти із ліфта?

І тут часто перепитують, уточнюю: якщо 2 чи 3 особи виходять на одному поверсі, то черговість виходу не має значення. ДУМАЙТЕ, використовуйте формули та правила додавання/множення комбінацій. У разі труднощів пасажирам корисно дати імена та поміркувати, у яких комбінаціях вони можуть вийти з ліфта. Не треба засмучуватися, якщо щось не вийде, наприклад, пункт № 2 досить підступний.

Повне рішення із докладними коментарями наприкінці уроку.

Заключний параграф присвячений комбінаціям, які теж зустрічаються досить часто – за моєю суб'єктивною оцінкою, приблизно 20-30% комбінаторних завдань:

Перестановки, поєднання та розміщення з повтореннями

Перелічені види комбінацій законспектовані у пункті № 5 довідкового матеріалу Основні формули комбінаторикиПроте деякі з них за першим прочитанням можуть бути не дуже зрозумілими. І тут спочатку доцільно ознайомитися з практичними прикладами, і лише потім осмислювати загальне формулювання. Поїхали:

Перестановки із повтореннями

У перестановках із повтореннями, як і в «звичайних» перестановках, бере участь відразу все безліч об'єктів, але є одне але: в даному множині один або більша кількість елементів (об'єктів) повторюються. Зустрічайте черговий стандарт:

Завдання 12

Скільки різних буквосполучень можна отримати перестановкою карток із наступними літерами: К, О, Л, О, К, О, Л, Ь, Ч, І, К?

Рішення: у тому випадку, якби всі літери були різні, то слід було б застосувати тривіальну формулу , проте цілком зрозуміло, що для запропонованого набору карток деякі маніпуляції спрацьовуватимуть «вхолосту», наприклад, якщо поміняти місцями будь-які дві картки з літерами «К » у будь-якому слові, то вийде те саме слово. Причому фізично картки можуть сильно відрізнятися: одна бути круглою з надрукованою літерою «К», інша – квадратною з намальованою літерою «К». Але за змістом завдання навіть такі картки вважаються однаковими, оскільки в умові питається про буквосполучення.

Все дуже просто – всього: 11 карток, серед яких літера:

К - повторюється 3 рази;
Про - повторюється 3 рази;
Л – повторюється двічі;
Ь - повторюється 1 раз;
Ч – повторюється 1 раз;
І – повторюється один раз.

Перевірка: 3 + 3 + 2 + 1 + 1 + 1 = 11, що потрібно перевірити.

За формулою кількості перестановок із повтореннями:
різних буквосполучень можна отримати. Більше півмільйона!

Для швидкого розрахунку великого факторіального значення зручно використовувати стандартну функцію Екселю: забиваємо в будь-яку комірку =ФАКТР(11)і тиснемо Enter.

На практиці цілком допустимо не записувати загальну формулу і, крім того, опускати поодинокі факторіали:

Але попередні коментарі про літери, що повторюються, обов'язкові!

Відповідь: 554400

Інший типовий приклад перестановок з повтореннями зустрічається в задачі про розміщення шахових фігур, яку можна знайти на складі готових рішеньу відповідній pdf-ці. А для самостійного рішення я вигадав менш шаблонне завдання:

Завдання 13

Олексій займається спортом, причому 4 дні на тиждень – легкою атлетикою, 2 дні – силовими вправами та 1 день відпочиває. Скільки способами він може скласти собі розклад занять на тиждень?

Формула тут не годиться, оскільки враховує збігаються перестановки (наприклад, коли міняються місцями силові вправи у середу із силовими вправами у четвер). І знову - за фактом ті ж 2 силові тренування можуть сильно відрізнятися один від одного, але за контекстом завдання (з точки зору розкладу) вони вважаються однаковими елементами.

Дворядкове рішення та відповідь наприкінці уроку.

Поєднання з повтореннями

Характерна риса цього виду комбінацій у тому, що вибірка проводиться із кількох груп, кожна у тому числі складається з однакових об'єктів.

Сьогодні всі добре попрацювали, тому настав час підкріпитись:

Завдання 14

У студентській їдальні продають сосиски в тесті, ватрушки та пончики. Скільки можна придбати п'ять пиріжків?

Рішення: відразу зверніть увагу на типовий критерій поєднань із повтореннями – за умовою на вибір запропоновано не безліч об'єктів як таке, а різні видиоб'єктів; при цьому передбачається, що у продажу є не менше п'яти хот-догів, 5 ватрушок та 5 пончиків. Тістечка в кожній групі, зрозуміло, відрізняються - бо абсолютно ідентичні пончики можна змоделювати хіба що на комп'ютері =) Проте фізичні характеристики пиріжків за змістом завдання не суттєві, і хот-доги/ватрушки/пончики у своїх групах вважаються однаковими.

Що може бути у вибірці? Насамперед, слід зазначити, що у вибірці обов'язково будуть однакові пиріжки (обираємо 5 штук, а на вибір запропоновано 3 види). Варіанти тут на будь-який смак: 5 хот-догів, 5 ватрушок, 5 пончиків, 3 хот-доги + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончики і т.д.

Як і при «звичайних» поєднаннях, порядок вибору та розміщення пиріжків у вибірці не має значення – просто вибрали 5 штук та все.

Використовуємо формулу кількості поєднань із повтореннями:
способом можна придбати 5 пиріжків.

Смачного!

Відповідь: 21

Який висновок можна зробити із багатьох комбінаторних завдань?

Іноді найважче – це розібратися в умові.

Аналогічний приклад для самостійного вирішення:

Завдання 15

У гаманці знаходиться досить велика кількість 1-, 2-, 5- та 10-рублевих монет. Скільки способами можна витягти три монети з гаманця?

З метою самоконтролю дайте відповідь на кілька простих питань:

1) Чи можуть у вибірці всі монети бути різними?
2) Назвіть найдешевшу і найдорожчу комбінацію монет.

Рішення та відповіді наприкінці уроку.

З мого особистого досвіду, можу сказати, що поєднання з повтореннями – найрідкісніший гість на практиці, чого не скажеш про такий вид комбінацій:

Розміщення з повтореннями

З множини, що складається з елементів, вибирається елементів, при цьому важливий порядок елементів у кожній вибірці. І все було б нічого, але досить несподіваний прикол полягає в тому, що будь-який об'єкт вихідної множини ми можемо вибирати скільки завгодно разів. Образно кажучи, від «багато не убуде».

Коли таке буває? Типовим прикладом є кодовий замок з кількома дисками, але через розвиток технологій актуальніше розглянути його цифрового нащадка:

Завдання 16

Скільки існує чотиризначних пін-кодів?

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

А тепер за допомогою формули. За умовою нам запропоновано набір із цифр, з якого вибираються цифри та розташовуються у визначеному порядку, при цьому цифри у вибірці можуть повторюватися (тобто будь-якою цифрою вихідного набору можна користуватися довільну кількість разів). За формулою кількості розміщень із повтореннями:

Відповідь: 10000

Що тут спадає на думку… …якщо банкомат «з'їдає» картку після третьої невдалої спроби введення пін-коду, то шанси підібрати його навмання дуже примарні.

І хто сказав, що у комбінаториці немає жодного практичного сенсу? Пізнавальне завдання для всіх читачів сайт:

Завдання 17

Згідно з державним стандартом, автомобільний номерний знак складається з 3 цифр та 3 літер. При цьому неприпустимий номер із трьома нулями, а літери вибираються з набору А, В, Е, К, М, Н, О, Р, С, Т, У, Х (використовуються лише ті літери кирилиці, написання яких збігається з латинськими літерами).

Скільки номерних знаків можна скласти для регіону?

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

Рішення та відповідь наприкінці уроку. Не забуваємо використовувати правила комбінаторики;-) …Хотів похвалитися ексклюзивом, та виявилося не ексклюзивом =) Заглянув у Вікіпедію – там є розрахунки, щоправда, без коментарів. Хоча у навчальних цілях, напевно, мало хто вирішував.

Наше захоплююче заняття добігло кінця, і насамкінець я хочу сказати, що ви не дарма витратили час – з тієї причини, що формули комбінаторики знаходять ще одне насущне практичне застосування: вони зустрічаються в різних завданнях теорії ймовірностей,
і в завдання на класичне визначення ймовірності- Особливо часто =)

Дякую всім за активну участь і до швидких зустрічей!

Рішення та відповіді:

Завдання 2: Рішення: знайдемо кількість всіх можливих перестановок 4 карток:

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

Примітка : т.к. карток небагато, то тут нескладно перерахувати всі такі варіанти:
0579
0597
0759
0795
0957
0975

Таким чином, із запропонованого набору можна скласти:
24 - 6 = 18 чотиризначних чисел
Відповідь : 18

Завдання 4: Рішення: способами можна вибрати 3 карти з 36
Відповідь : 7140

Завдання 6: Рішення: методами.
Інший варіант вирішення : способами можна вибрати двох осіб з групи та
2) «Найдешевший» набір містить 3 рублеві монети, а «найдорожчий» – 3 десятирублеві.

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

Правило додавання використовується в тому випадку, якщо у нас є дві або більше множин, які попарно не перетинаються, тобто не мають спільних елементів. І нам потрібно знайти скільки елементів міститься в поєднанні цих множин. У цьому випадку ми складаємо кількість елементів у кожній множині. Найпростіший приклад: якщо у нас є два кошики з фруктами: в одному 5 яблук, а в іншому 7 груш. Якщо ми ці фрукти пересипаємо в один кошик (об'єднуємо безліч), тоді в новому кошику виявиться 5+7=12 фруктів.

Правило множення

Правило множення використовується в тому випадку, якщо ми маємо дві множини, і ми складаємо всілякі пари з елементів цих множин. Наприклад, якщо взяти безліч, що складається з 5-ти яблук і безліч, що складається з 7 груш і скласти всілякі пари з цих фруктів, то ми отримаємо всіляких пар.

Справді. Візьмемо перше яблуко. Ми можемо покласти до нього будь-яку із семи груш, тобто отримуємо 7 пар. Візьмемо друге яблуко, і до нього ми також можемо покласти будь-яку з 7 груш, отримуємо ще 7 пар. І так далі. Усього виходить пара.

Правило множення легко зрозуміти, якщо спробувати відповісти, наприклад, на таке запитання: скільки існує двоцифрових чисел?"

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

Нехай і у нас є 10 варіантів цифр, які можуть стояти на другому місці. Тоді ми маємо 10 двоцифрових чисел, що містять 1 десяток.

Потім ми беремо і так само отримуємо 10 двоцифрових чисел, у яких тепер уже 2 десятки.

Так як цифра може набувати 9 різних значень, то отримуємо двоцифрових чисел.

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

У загальному випадку правило множеннязвучить так:

Якщо елемент A можна вибрати n способами, і за будь-якому виборі A елемент B можна вибрати m способами, то пару (A, B) можна вибрати n·m способами. Це правило поширюється на будь-яке число незалежно обраних елементів.

Якщо ми хочемо відповісти на запитання, скільки існує трицифрових чисел, ми зауважимо, що в тризначному числі перша цифра може набувати 9 значень, друга - 10, і третя - 10 значень. І ми отримуємо трицифрових чисел.

Формула включень-виключень

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

Нехай безліч А містить n елементів, безліч містить m елементів, і перетин цих множин містить k елементів. Тобто k елементів містяться і в множині А, і в множині В. Тоді об'єднання множин містить m+n-k елементів.

Дійсно, при об'єднанні двох множин ми k елементів порахували двічі, і тепер один раз ми повинні їх відняти.

Число елементів у множині позначається загальноприйнятим значком #. Тоді формула для підрахунку числа елементів в поєднанні трьох множин має вигляд:

## # # # # # #

Розглянемо приклади завдань.

1. Скільки трицифрових чисел містить хоча б одну цифру 3?

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

Знайдемо, скільки трицифрових чисел НЕ містить цифру 3. У цьому випадку на першому, другому та третьому місці в записі числа може стояти будь-яка цифра крім 3. Тобто перша цифра може набувати 8 значень, друга - 9, і третя - 9 значень. Тоді ми отримуємо трицифрових чисел, які не містять цифри 3. Отже, решта числа містить хоча б одну цифру 3.

2. Скільки чотирицифрових чисел, кратних 5.

Ми знаємо, що число ділиться на 5, якщо воно закінчується на 0 або 5. Отже, у чотиризначному числі остання цифра може набувати лише двох значень: 0 і 5.
Перша цифра може набувати 9 значень, друга - 10, і третя - 10 значень, четверта - 2 значення.

Тоді ми отримуємо чотиризначні числа, які діляться на 5.

Перестановки

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

Людину, яка стоїть першою в шерензі можна вибрати сімома способами, другу можна вибрати з шести осіб, тобто шістьма способами. Третього відповідно п'ятьма. І так далі. Останнього можна вибрати єдиним способом. Усього отримуємо способів побудувати 7 осіб у шеренгу.

У випадку, якщо ми маємо об'єктів, які хочемо розташувати у порядку (пронумерувати їх), ми отримаємо

способів розташування цих об'єктів.

Факторіаломнатурального числа називається добуток усіх натуральних чисел від 1 до :

За визначенням 0!=1; 1!=1.

Перестановкоюз предметів називається будь-який спосіб нумерації цих предметів (спосіб розташування їх у ряд).

Число перестановокпредметів одно.

3. Є 10 комп'ютерних дисків та 10 коробок від них. Знайдіть ймовірність того, що випадково поклавши диски в коробки, ми виявимо, що

1. Кожен диск лежить у своїй коробці.

2. Хоча один диск лежить не у своїй коробці.

3. Два певні диски переплутані місцями, а решта у своїх коробках.

4. Рівно один лежить не у своїй коробці, а решта – у своїх коробках.

1. Пронумеруємо диски та коробки. Розташуємо коробки у певній послідовності. Нам потрібно, щоб при випадковому розташуванні дисків у ряд, їх номери теж були розташовані в тій же послідовності.

Розташувати 10 чисел у певній послідовності можна єдиним способом, тобто ми маємо 1 сприятливий результат.

Розмістити 10 чисел у довільному порядку можна 10! методами.

Отже, ймовірність того, що кожен диск опиниться у своїй коробці, дорівнює

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

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

4. Подія " рівно один лежить не у своїй коробці, а решта - у своїх коробкахнеможливо, тому що якщо один диск лежить не своїй коробці, то обов'язково повинен знайтися ще один, який так само лежить не в своїй коробці. Тому ймовірність цієї події дорівнює нулю.

4. Слово "МАТЕМАТИКА" написали на смужці картону та розрізали смужку на літери. Знайдіть ймовірність того, що склавши всі ці букви випадково в ряд, ми знову отримаємо слово "МАТЕМАТИКА".

МАТЕМАТИКА"?

Імовірність того, що на першому місці стоятиме буква М, дорівнює 2/10 - у нас дві літери М, і всього 10 букв.

Імовірність того, що на другому місці стоятиме літера А, дорівнює 3/9 - у нас залишилося 9 літер, з яких 3 літери А.

Імовірність того, що на другому місці стоятиме літера Т, дорівнює 2/8 - у нас залишилося 8 літер, з яких 2 літери Т.

Пронумеруємо всі літери у слові "МАТЕМАТИКА". Знайдемо, скільки способів ми можемо їх розташувати у порядку. У слові 10 букв, і ми можемо їх розташувати 10! = 3628800 у різний спосіб.

Оскільки в слові є однакові букви, то при перестановці цих букв ми отримаємо те саме слово:

у слові "МАТЕМАТИКА" 2 літери "М"; 3 літери "А"; 2 букви "Т", отже за правилом твору це дає нам способів перестановки цих букв із збереженням слова "МАТЕМАТИКА".

Таким чином, можливість знову отримати слово "МАТЕМАТИКА" дорівнює:

Скільки буквосполучень можна скласти з букв слова " МАТЕМАТИКА"?

З 10 букв слова " МАТЕМАТИКА"можна скласти 10! буквосполучень. Але деякі з них будуть однаковими, тому що при перестановці однакових літер, ми отримуватимемо ті ж самі буквосполучення. Тобто в результаті ми отримаємо

буквосполучень.

Розміщення

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

5. Скільки існує різних варіантів вибору 4-х кандидатур з 9-ти фахівців для поїздки до 4 різних країн?

Скористаємося правилом множення.

У першу країну ми вибираємо з 9 спеціалістів, тобто ми маємо 9 варіантів вибору. Після того, як фахівця для поїздки до першої країни обрано, у нас залишилося 8 спеціалістів, і для поїздки до другої країни ми маємо 8 варіантів вибору. І так далі... у четверту країну ми можемо обрати кандидата із 6 фахівців.

Таким чином, ми отримуємо варіантів вибору 4-х кандидатур з 9-ти фахівців для поїздки до 4 різних країн.

Узагальним це завдання у разі вибору k кандидатур з n фахівців для поїздки до різних країн.

Розмірковуючи аналогічним чином, ми отримуємо

варіантів.

Якщо помножити і розділити цей вираз на , то отримаємо таку формулу:

У цьому вся задачі з безлічі, що з елементів ми вибрали упорядкованіпідмножини (Для нас був важливий порядок розташування елементів у підмножині), що складаються з елементів. Завдання зводилося до знаходження числа таких підмножин.

Такі впорядковані підмножини називаються розміщеннями з елементів n до k.

Розміщенням(з n по k) називається упорядковане підмножиназ різних елементів з деякої множини, що складається з різних елементів.

Кількість розміщень з елементів по позначається та знаходиться за формулою:

Розміщення з повтореннями

6. Гральну кістку кидають тричі. Скільки різних комбінацій очок, що випали, при цьому вийде?

При киданні кістки вперше ми отримаємо 6 різних варіантів: 1 очко, 2, 3 ... або 6. Аналогічно при киданні кістки вдруге і втретє ми отримаємо також по 6 різних варіантів. За правилом множення отримаємо кількість різних комбінацій трьох чисел, що приймають значення від 1 до 6:

У загальному випадку:

Нехай у нас є безліч, що складається з елементів.

Будь-який упорядкований набір елементів множини, що складається з елементів називається розміщенням з повторенням з елементів по . Число різних розміщень з повтореннями дорівнює

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

Оскільки кулі кожного разу повертаються, кожен раз, виймаючи кулю з коробки, в якій куль, ми можемо отримати різні числа. За правилом множення маємо

Поєднання

Розглянемо задачу, аналогічну до завдання 5, але з істотною відмінністю.

7. Скільки існує різних варіантів вибору 4-х кандидатур із 9-ти фахівців?

У цьому завданні нам потрібно вибрати 4 кандидатури, але при цьому не важливо, в якому порядку ми їх обираємо, нас цікавить лише склад обраних елементів, але з порядок їх розташування.

Якби нас цікавив порядок розташування елементів, як у задачі 5, то ми могли б застосувати формулу для знаходження числа розміщень з 9 по 4:

4 різних елементів можна розташувати в певному порядку 4! у різний спосіб. Оскільки нас нецікавить порядок розташування елементів, кількість способів, якими ми можемо вибрати 4 елементи, не маючи їх у певному порядку, зменшується в 4! рази в порівнянні з попереднім завданням (оскільки для даного завдання різне розташування даних елементів вважається одним способом), і ми отримуємо

методів.

У цьому вся задачі з'являється поняття поєднання.

Поєднаннями з n елементів по k елементів називаються підмножини, що складаються з елементів множини (множини, що складається з n елементів).

Увага!Одне поєднання від іншого відрізняється лише складом вибраних елементів (але не порядком їхнього розташування, як у розміщень).

Число поєднаньз nелементів по kелементів позначається

і знаходиться за формулою:

Число поєднань з nпо kпоказує, скільки способів ми можемо вибрати kелементів з nелементів, або скільки способів ми можемо розташувати kоб'єктів по nмісцям .

Легко помітити, що

8. У коробці лежать 8 червоних олівців та 4 сині. З коробки навмання виймають 4 олівці. Яка ймовірність того, що серед них виявиться 2 червоні та 2 сині?

Загалом у коробці 12 олівців. Знайдемо, скільки способів можна витягти з коробки 4 олівця. Так як нас не цікавить порядок, в якому олівці витягуються з коробки, а тільки склад олівців, це число дорівнює кількості поєднань з 12 по 4:

З 8 червоних олівців можна витягти два олівці методами.

З 4 синіх олівців можна витягти два олівці методами.

За правилом твору отримуємо, що витягти 2 сині та 2 червоні олівці можна способами.

Таким чином, шукана ймовірність дорівнює:

Метод куль та перегородок

9. Скільки способами можна розкласти 10 куль у 4 коробки? Передбачається, що деякі коробки можуть бути порожніми.

Розглянемо 10 куль:

"Розкладатимемо кулі по коробках", ставлячи перегородки.

Наприклад, так:

У цьому прикладі у першій коробці 3 кулі, у другій - 2, у третій - 4, і в четвертій - 2. Переставляючи кулі та перегородки, ми отримуємо різні комбінації куль у коробках. Наприклад, переставивши останню кулю в першій коробці та першу внутрішню перегородку, ми отримаємо таку комбінацію:

Таким чином, ми отримуємо різну кількість куль у коробках, комбінуючи позиції 10 куль і 3 внутрішніх перегородок. Щоб визначити, скільки різних комбінацій ми можемо отримати, нам потрібно знайти число поєднань з 13 по 3. (Або, що те саме, що число поєднань з 13 по 10.) Стільки способів вибрати 3 місця для перегородок з 13 можливих позицій. Або, що те саме, 10 місць для куль.

10. Скільки рішень має рівняння у цілих невід'ємних числах?

Так як змінні можуть набувати тільки цілі невід'ємні значення, отже, у нас є 10 змінних, і вони можуть набувати значення 0, 1, 2, 3 і 4. Уявімо, що у нас є 10 коробок (це змінні), і ми повинні розкласти по цих коробках 4 кулі. Скільки куль потрапить у коробку, таке значення відповідної змінної. Якщо у нас 10 коробок, отже, 10-1=9 внутрішніх перегородок. І 4 кулі. Усього 13 місць. Нам треба розташувати на цих 13 місцях 4 кулі. Число таких можливостей:

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

У цьому завдання ми мали справу з поєднаннями із повтореннями.

Поєднання з повтореннями

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

Що таке поєднання з елементів щодо елементів з повтореннями можна зрозуміти за допомогою такого уявного експерименту. Представимо ящик із пронумерованими кулями. Ми виймаємо кулю, записуємо її номер і повертаємо назад, і так разів. На відміну від розміщень із повтореннями нас не цікавить порядок записаних чисел, а лише їхній склад. Наприклад, групи чисел (1,1,2,1,3,1,2) та (1,1,1,1,2,2,3) вважаються однаковими. Скільки таких груп з номери ми можемо отримати?

Зрештою нас цікавить скільки елементів кожного типу (всього nтипів елементів) міститься в кожній групі (з kелементів ) і скільки таких різних варіантів може бути. Тобто ми знаходимо, скільки в цілих невід'ємних рішень має рівняння рівняння - задача аналогічна задачі розкладання nкуль у kкоробки.

Число поєднань із повтореннями знаходиться за такою формулою:

Таким чином, число поєднань з повтореннями - це кількість способів уявити число k у вигляді суми n доданків.

Яка я знайшов на сайті компанії DataGenetics. Усі помилки за цією статтею надсилайте, будь ласка, в особисті повідомлення.

У цьому в'язниці сидять 100 ув'язнених, кожен з яких пронумерований числами від 1 до 100. Тюремник вирішує дати шанс ув'язненим на звільнення, він розповідає їм умови випробування, і якщо всі ув'язнені пройдуть тест, тоді вони будуть звільнені. Якщо хоча б один із них провалить тест, то всі ув'язнені помруть.

Завдання

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

Змагання починається, тюремник відводить кожного ув'язненого по одному в кімнату з коробками і каже ув'язненим, що вони повинні знайти коробку, в якій буде табличка з номером ув'язненого. Ув'язнені намагаються знайти табличку зі своїм номером, відкриваючи коробки. Кожному дозволяється відкрити до 50 коробок; якщо кожен із ув'язнених знайде свій номер, то ув'язнених відпустять, якщо хоча б один із них не знайде свій номер за 50 спроб, то всі ув'язнені помруть.

Для того, щоб ув'язнених було звільнено, ВСІ ув'язнені мають пройти випробування успішно.

То який же шанс, що в'язнів помилують?

• Після відкриття коробки ув'язненим та перевірки ним таблички вона поміщається назад у коробку і кришка знову закривається;
• Місцями таблички міняти не можна;
• В'язні не можуть залишати один одному підказки або взаємодіяти один з одним після початку випробування;
• Ув'язненим дозволяється обговорити стратегію на початок випробування.

Яка оптимальна стратегія для ув'язнених?

Додаткове питання:

Якщо товариш ув'язнених (не учасник випробування) матиме можливість проникнути в секретну кімнату до початку випробування, вивчити всі таблички у всіх коробках і (за бажанням, але не обов'язково) поміняти місцями дві таблички з двох коробок (при цьому у товариша не буде можливості як повідомити ув'язненим про результат своїх дій), то яку стратегію він має зробити, щоб збільшити шанси ув'язнених на порятунок?

Рішення малоймовірне?

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

Шанси одного в'язня – 50:50. Всього 100 коробок і він може відкрити до 50 коробок у пошуках своєї таблички. Якщо він відкриватиме коробки навмання і відкриє половину всіх коробок, то знайде свою табличку у відкритій половині коробок, або її табличка залишиться в закритих 50 коробках. Його шанси на успіх – ½.

Візьмемо двох ув'язнених. Якщо обидва вибирають коробки навмання, для кожного шанси будуть ½, а для двох ½x½=¼.
(Для двох ув'язнених успіх буде в одному випадку з чотирьох).

Для трьох ув'язнених шанси будуть ½ × ½ × ½ = ⅛.

Для 100 ув'язнених шанси наступні: ½ × ½ × … ½ × ½ (перемноження 100 разів).

Це дорівнює

Pr ≈ 0.000000000000000000000000000008

Тобто, це дуже маленький шанс. За такого розкладу, швидше за все, всі ув'язнені будуть мертві.

Неймовірна відповідь

Якщо кожен ув'язнений відкриватиме ящики навмання, то навряд чи вони пройдуть випробування. Існує стратегія, за якої ув'язнені можуть розраховувати на успіх більш ніж у 30% випадків. Це надзвичайно неймовірний результат (якщо ви не чули про це математичне завдання раніше).

Більше 30% для всіх 100 ув'язнених! Та це навіть більше, ніж шанси для двох ув'язнених, за умови, що ті відкриватимуть ящики навмання. Але як це можливо?

Зрозуміло, що по одному у кожного ув'язненого шанси не можуть бути вищими за 50% (адже немає способу спілкування між ув'язненими). Але не варто забувати, що інформація зберігається в розташуванні табличок усередині коробок. Ніхто не перемішує таблички між відвідуваннями кімнати окремими ув'язненими, тому ми можемо використовувати цю інформацію.

Рішення

Спочатку розповім рішення, потім роз'ясню, чому воно працює.

Стратегія вкрай легка. Перший із ув'язнених відкриває коробку з номером, який написаний на його одязі. Наприклад, ув'язнений номер 78 відкриває коробку з номером 78. Якщо він знаходить свій номер на табличці всередині коробки, то це чудово! Якщо ні, то він дивиться номер на табличці у своїй коробці і потім відкриває наступну коробку з цим номером. Відкривши другу коробку, він дивиться номер таблички всередині цієї коробки та відкриває третю коробку з цим номером. Далі просто переносимо цю стратегію на ящики, що залишилися. Для наочності дивимося картинку:

Зрештою, ув'язнений або знайде свій номер, або дійде до 50 коробок. На перший погляд, це виглядає безглуздо, в порівнянні з простим вибором коробки навмання (і для одного окремого ув'язненого це так), але так як всі 100 ув'язнених будуть використовувати той же набір коробок, це має сенс.

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

То чому ж стратегія працює?

У кожній коробці по одній табличці – і ця табличка унікальна. Це означає, що табличка знаходиться в коробці з тим самим номером, або вона вказує на іншу коробку. Так як всі таблички унікальні, то для кожної коробки є тільки одна табличка, що вказує на неї (і всього один шлях, як дістатися цієї коробки).

Якщо подумати над цим, то коробки утворюють замкнутий круглий ланцюжок. Одна коробка може бути частиною лише одного ланцюжка, тому що всередині коробки лише один покажчик на наступну і, відповідно, у попередній коробці лише один покажчик на дану коробку (програмісти можуть побачити аналогію зі зв'язаними списками).

Якщо коробка не вказує на себе (номер коробки дорівнює номеру таблички в ній), то вона буде в ланцюжку. Деякі ланцюжки можуть складатися з двох коробок, деякі довші.

Оскільки всі ув'язнені починають із коробки з тим самим номером, що й на їхньому одязі, вони, за визначенням, потрапляють на ланцюжок, який містить їхню табличку (є лише одна табличка, яка вказує на цю коробку).

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

Єдине питання залишається у тому, чи знайдуть вони свою табличку за 50 ходів.

Довжина ланцюжків

Для того, щоб усі ув'язнені пройшли випробування, максимальна довжина ланцюжка повинна бути меншою, ніж 50 коробок. Якщо ланцюжок довше, ніж 50 коробок, ув'язнені, що мають номери з цих ланцюжків, провалять випробування - і всі ув'язнені будуть мертві.

Якщо максимальна довжина найдовшого ланцюжка менша, ніж 50 коробок, тоді всі ув'язнені пройдуть випробування!

Подумайте про це на секунду. Виходить, що може бути тільки один ланцюжок, який довший за 50 коробок при будь-якому розкладі табличок (у нас всього 100 коробок, так що якщо один ланцюжок довший за 50, то решта буде коротшою, ніж 50 в результаті).

Шанси на розклад з довгим ланцюжком

Після того, як ви переконали себе, що для досягнення успіху максимальна довжина ланцюга повинна бути меншою або дорівнює 50, і може бути лише один довгий ланцюжок у будь-якому наборі, ми можемо обчислити ймовірність успіху проходження випробування:

Ще трохи математики

Отже, що нам потрібно, щоб з'ясувати ймовірність існування довгого ланцюжка?

Для ланцюжка з довжиною l, ймовірність того, що коробки будуть поза цим ланцюжком одно:

У цій колекції чисел існує (l-1)! способів розташувати таблички.

Таблички, що залишилися, можуть бути розташовані (100-l)! методами (не забуваємо, що довжина ланцюжка вбирається у 50).

З огляду на це число перестановок, які містять ланцюжок точної довжини l: (>50)

Виходить, є 100(!) способів розкладок табличок, тому ймовірність існування ланцюжка довжиною l дорівнює 1/l. До речі, цей результат залежить від кількості коробок.

Як ми вже знаємо, може бути тільки один варіант, при якому існує ланцюжок довжиною > 50, так що ймовірність успіху розраховується за цією формулою:

Результат

31.18% - ймовірність того, що розмір найдовшого ланцюжка буде меншим за 50 і кожен із ув'язнених зможе знайти свою табличку, враховуючи ліміт у 50 спроб.

Імовірність того, що всі ув'язнені знайдуть свої таблички та пройдуть випробування 31.18%

Нижче наведено графік, що показує ймовірності (осі ординат) для всіх ланцюгів довжини l (на осі абсцис). Червоний колір означає всі "невдачі" (дана крива тут - це просто графік 1/l). Зелений колір означає «успіх» (розрахунок трохи складніший для цієї частини графіка, оскільки існує кілька способів визначення максимальної довжини<50). Общая вероятность складывается из зеленых столбцов в 31.18% шанс на спасение.

Гармонійне число (ця частина статті для гіків)

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

Порахуємо ліміт, якщо замість 100а коробок ми маємо довільну велику кількість коробок (давайте вважати, що у нас є 2n коробок у результаті).

Постійна Ейлера-Маскероні - константа, що визначається як межа різниці між частковою сумою гармонійного ряду та натуральним логарифмом числа.

Оскільки кількість ув'язнених збільшується, то за умови, якщо наглядач дозволяє ув'язненим відкривати половину всіх коробок, то шанс на порятунок прагне 30.685%.

(Якщо ви ухвалили рішення, при якому ув'язнені випадково вгадують коробки, то зі збільшенням кількості ув'язнених ймовірність порятунку прагне нуля!)

Додаткове питання

Хтось ще пам'ятає про додаткове запитання? Що може зробити наш корисний товариш, щоби збільшити шанси на виживання?

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

В результаті цієї стратегії не буде довгих ланцюжків і всі ув'язнені гарантовано знайдуть свою табличку та порятунок. Отже, помінявши місцями дві таблички, ми зводимо можливість порятунку до 100%!

Пропоную читачам "Хабрахабра" переклад публікації "100 Prisoners Escape Puzzle", яку я знайшов на сайті компанії DataGenetics. Усі помилки за цією статтею надсилайте, будь ласка, в особисті повідомлення.

За умовою завдання у в'язниці перебуває 100 ув'язнених, кожен із яких має особистий номер від 1 до 100. Тюремник вирішує дати ув'язненим шанс на звільнення та пропонує пройти вигадане випробування. Якщо всі ув'язнені впораються, то вони вільні, якщо хоча б один провалиться – усі помруть.

Завдання

Змагання починається, тюремник відводить кожного ув'язненого по одному в кімнату з коробками і каже ув'язненим, що вони повинні знайти коробку, в якій буде табличка з номером ув'язненого. Ув'язнені намагаються знайти табличку зі своїм номером, відкриваючи коробки. Кожному дозволяється відкрити до 50 коробок; якщо кожен із ув'язнених знайде свій номер, то ув'язнених відпустять, якщо хоча б один із них не знайде свій номер за 50 спроб, то всі ув'язнені помруть.

Для того, щоб ув'язнених було звільнено, ВСІ ув'язнені мають пройти випробування успішно.

То який же шанс, що в'язнів помилують?

• Після відкриття коробки ув'язненим та перевірки ним таблички вона поміщається назад у коробку і кришка знову закривається;
• Місцями таблички міняти не можна;
• В'язні не можуть залишати один одному підказки або взаємодіяти один з одним після початку випробування;
• Ув'язненим дозволяється обговорити стратегію на початок випробування.

Яка оптимальна стратегія для ув'язнених?

Додаткове питання:

Якщо товариш ув'язнених (не учасник випробування) матиме можливість проникнути в секретну кімнату до початку випробування, вивчити всі таблички у всіх коробках і (за бажанням, але не обов'язково) поміняти місцями дві таблички з двох коробок (при цьому у товариша не буде можливості як повідомити ув'язненим про результат своїх дій), то яку стратегію він має зробити, щоб збільшити шанси ув'язнених на порятунок?

Рішення малоймовірне?

Шанси одного в'язня – 50:50. Всього 100 коробок і він може відкрити до 50 коробок у пошуках своєї таблички. Якщо він відкриватиме коробки навмання і відкриє половину всіх коробок, то знайде свою табличку у відкритій половині коробок, або її табличка залишиться в закритих 50 коробках. Його шанси на успіх – ½.

Візьмемо двох ув'язнених. Якщо обидва вибирають коробки навмання, для кожного шанси будуть ½, а для двох ½x½=¼.
(Для двох ув'язнених успіх буде в одному випадку з чотирьох).

Для трьох ув'язнених шанси будуть ½ × ½ × ½ = ⅛.

Для 100 ув'язнених шанси наступні: ½ × ½ × … ½ × ½ (перемноження 100 разів).

Це дорівнює

Pr ≈ 0.0000000000000000000000000000008

Тобто, це дуже маленький шанс. За такого розкладу, швидше за все, всі ув'язнені будуть мертві.

Неймовірна відповідь

Більше 30% для всіх 100 ув'язнених! Та це навіть більше, ніж шанси для двох ув'язнених, за умови, що ті відкриватимуть ящики навмання. Але як це можливо?

Зрозуміло, що по одному у кожного ув'язненого шанси не можуть бути вищими за 50% (адже немає способу спілкування між ув'язненими). Але не варто забувати, що інформація зберігається в розташуванні табличок усередині коробок. Ніхто не перемішує таблички між відвідуваннями кімнати окремими ув'язненими, тому ми можемо використовувати цю інформацію.

Рішення

Стратегія вкрай легка. Перший із ув'язнених відкриває коробку з номером, який написаний на його одязі. Наприклад, ув'язнений номер 78 відкриває коробку з номером 78. Якщо він знаходить свій номер на табличці всередині коробки, то це чудово! Якщо ні, то він дивиться номер на табличці у своїй коробці і потім відкриває наступну коробку з цим номером. Відкривши другу коробку, він дивиться номер таблички всередині цієї коробки та відкриває третю коробку з цим номером. Далі просто переносимо цю стратегію на ящики, що залишилися. Для наочності дивимося картинку:

Зрештою, ув'язнений або знайде свій номер, або дійде до 50 коробок. На перший погляд, це виглядає безглуздо, в порівнянні з простим вибором коробки навмання (і для одного окремого ув'язненого це так), але так як всі 100 ув'язнених будуть використовувати той же набір коробок, це має сенс.

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

То чому ж стратегія працює?

Якщо подумати над цим, то коробки утворюють замкнутий круглий ланцюжок. Одна коробка може бути частиною лише одного ланцюжка, тому що всередині коробки лише один покажчик на наступну і, відповідно, у попередній коробці лише один покажчик на дану коробку (програмісти можуть побачити аналогію зі зв'язаними списками).

Якщо коробка не вказує на себе (номер коробки дорівнює номеру таблички в ній), то вона буде в ланцюжку. Деякі ланцюжки можуть складатися з двох коробок, деякі довші.

Оскільки всі ув'язнені починають із коробки з тим самим номером, що й на їхньому одязі, вони, за визначенням, потрапляють на ланцюжок, який містить їхню табличку (є лише одна табличка, яка вказує на цю коробку).

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

Єдине питання залишається у тому, чи знайдуть вони свою табличку за 50 ходів.

Довжина ланцюжків

Якщо максимальна довжина найдовшого ланцюжка менша, ніж 50 коробок, тоді всі ув'язнені пройдуть випробування!

Подумайте про це на секунду. Виходить, що може бути тільки один ланцюжок, який довший за 50 коробок при будь-якому розкладі табличок (у нас всього 100 коробок, так що якщо один ланцюжок довший за 50, то решта буде коротшою, ніж 50 в результаті).

Шанси на розклад з довгим ланцюжком

Ще трохи математики

Для ланцюжка з довжиною l, ймовірність того, що коробки будуть поза цим ланцюжком дорівнює:

У цій колекції чисел існує (l-1)! способів розташувати таблички.

Таблички, що залишилися, можуть бути розташовані (100-l)! методами (не забуваємо, що довжина ланцюжка вбирається у 50).

З огляду на це число перестановок, які містять ланцюжок точної довжини l: (>50)

Виходить, є 100(!) способів розкладок табличок, тому ймовірність існування ланцюжка довжиною l дорівнює 1/l. До речі, цей результат залежить від кількості коробок.

Як ми вже знаємо, може бути тільки один варіант, при якому існує ланцюжок довжиною > 50, так що ймовірність успіху розраховується за цією формулою:

Результат

Імовірність того, що всі ув'язнені знайдуть свої таблички та пройдуть випробування 31.18%

Нижче наведено графік, що показує ймовірності (осі ординат) для всіх ланцюгів довжини l (на осі абсцис). Червоний колір означає всі "невдачі" (дана крива тут - це просто графік 1/l). Зелений колір означає «успіх» (розрахунок трохи складніший для цієї частини графіка, оскільки існує кілька способів визначення максимальної довжини<50). Общая вероятность складывается из зеленых столбцов в 31.18% шанс на спасение.

Гармонійне число (ця частина статті для гіків)

Порахуємо межу, якщо замість 100а коробок ми маємо довільну велику кількість коробок (давайте вважати, що у нас є 2n коробок у результаті).

Постійна Ейлера-Маскероні - константа, що визначається як межа різниці між частковою сумою гармонійного ряду та натуральним логарифмом числа.

Оскільки кількість ув'язнених збільшується, то за умови, якщо наглядач дозволяє ув'язненим відкривати половину всіх коробок, то шанс на порятунок прагне 30.685%.

(Якщо ви ухвалили рішення, при якому ув'язнені випадково вгадують коробки, то зі збільшенням кількості ув'язнених ймовірність порятунку прагне нуля!)

Додаткове питання

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

В результаті цієї стратегії не буде довгих ланцюжків і всі ув'язнені гарантовано знайдуть свою табличку та порятунок. Отже, помінявши місцями дві таблички, ми зводимо можливість порятунку до 100%!

Визначення.

Це шестигранник, основами якого є два рівні квадрати, а бічні грані є рівними прямокутниками.

Бокове ребро- це спільна сторона двох суміжних бічних граней

Висота призми- це відрізок, перпендикулярний до основ призми

Діагональ призми- відрізок, що з'єднує дві вершини основ, що не належать до однієї грані

Діагональна площина- площина, яка проходить через діагональ призми та її бічні ребра

Діагональний переріз- межі перетину призми та діагональної площини. Діагональний переріз правильної чотирикутної призми є прямокутником.

Перпендикулярний переріз (ортогональний переріз)- це перетин призми та площини, проведеної перпендикулярно її бічним ребрам.

Елементи правильної чотирикутної призми

На малюнку зображено дві правильні чотирикутні призми, у яких позначені відповідними літерами:

• Підстави ABCD і A 1 B 1 C 1 D 1 рівні та паралельні один одному
• Бічні грані AA 1 D 1 D, AA 1 B 1 B, BB 1 C 1 C та CC 1 D 1 D, кожна з яких є прямокутником
• Бічна поверхня - сума площ усіх бічних граней призми
• Повна поверхня - сума площ усіх основ та бічних граней (сума площі бічної поверхні та основ)
• Бічні ребра AA 1 , BB 1 , CC 1 та DD 1 .
• Діагональ B 1 D
• Діагональ основи BD
• Діагональний переріз BB 1 D 1 D
• Перпендикулярний переріз A2B2C2D2.

Властивості правильної чотирикутної призми

• Підставами є два рівні квадрати
• Підстави паралельні одна одній
• Боковими гранями є прямокутники
• Бічні грані рівні між собою
• Бічні грані перпендикулярні основам
• Бічні ребра паралельні між собою та рівні
• Перпендикулярний перетин перпендикулярно всім бічним ребрам і паралельно основам
• Кути перпендикулярного перерізу – прямі
• Діагональний переріз правильної чотирикутної призми є прямокутником.
• Перпендикулярний (ортогональний переріз) паралельно основам

Формули для правильної чотирикутної призми

Вказівки до вирішення завдань

Правильна призма- призма в основі якої лежить правильний багатокутник, а бічні ребра перпендикулярні до площин основи. Тобто правильна чотирикутна призма містить у своїй основі квадрат. (Див. вище властивості правильної чотирикутної призми) Примітка. Це частина уроку із завданнями з геометрії (розділ стереометрія – призма). Тут розміщені завдання, які викликають труднощі під час вирішення. Якщо Вам необхідно вирішити задачу геометрії, якої тут немає - пишіть про це у форумі. Для позначення дії вилучення квадратного кореня у розв'язках задач використовується символ√ .

Завдання.

Діагональ правильної призми утворює з діагоналлю основи та висотою призми прямокутний трикутник. Відповідно, за теоремою Піфагора діагональ заданої правильної чотирикутної призми дорівнюватиме:
√((12√2) 2 + 14 2 ) = 22 см

Відповідь: 22 см

Завдання

Рішення.
Оскільки в основі правильної чотирикутної призми лежить квадрат, то бік основи (позначимо як a) знайдемо за теоремою Піфагора:

A 2 + a 2 = 5 2
2a 2 = 25
a = √12,5

Висота бічної грані (позначимо як h) тоді дорівнюватиме:

H 2 + 12,5 = 4 2
h 2 + 12,5 = 16
h 2 = 3,5
h = √3,5

Площа повної поверхні дорівнюватиме сумі площі бічної поверхні та подвоєної площі основи

S = 2a 2 + 4ah
S = 25 + 4√12,5 * √3,5
S = 25 + 4√43,75
S = 25 + 4√(175/4)
S = 25 + 4√(7*25/4)
S = 25 + 10√7 ≈ 51,46 см 2 .

Відповідь : 25 + 10√7 ≈ 51,46 см 2 .