Умова:

Відома логічна задача, може бути корисною для програмістів-початківців. Я пообіцяв учасникам i7.juniors детально її пояснити. Давайте розбиратися.

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

1. Ти лицар?
2. Ти брехун?
3. Ти хитрун?
4. Ми в селі лицарів?
5. Ми в селі брехунів?
6. Ми в селі хитрунів?

Шість запитань. Інші запитання на кшталт «Чи є життя на Марсі» нам не підійдуть, тому що нам треба не просто побалакати, а розв’язати задачу за мінімальну кількість запитань.

Далі пропоную розділити задачу на дві проміжні.

Перша – допомогти мандрівнику дізнатися, з ким він розмовляє.

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

Першу задачу можна розв’язати, якщо задати аборигену запитання номер три двічі поспіль. Тобто запитати два рази: «Ти хитрун?»

Якщо абориген двічі відповість «ні» — перед нами лицар. Якщо абориген відповість двічі «так», то він брехун. Якщо ж він дасть різні відповіді, то це хитрун. В такому випадку нам треба запам’ятати послідовність його відповідей. Тобто, якщо хитрун на запитання «Ти хитрун?» спочатку сказав «так», а потім – «ні», це означає, що спочатку він сказав правду, а потім збрехав. Нам це важливо, тому що, згідно умови задачі, наступний раз хитрун скаже правду. І навпаки.

Далі, дізнавшись «характеристику» аборигена, мандрівнику треба дізнатися, в якому селі вони знаходяться.

Для цього йому потрібно задати запитання номери чотири і п’ять в будь-який послідовності, а саме:

— Ми в селі лицарів?

—  Ми в селі брехунів?

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

Нехай перед ним лицар. Тоді мандрівник гарантовано отримає інформацію про своє місцезнаходження за два питання. (якщо на перше питання лицар відповів «так», то вистачить і одного запитання.)

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

Третій варіант. Нехай перед ним хитрун. Запам'ятавши відповіді на попередні два запитання, мандрівник може зрозуміти, чи скаже хитрун в наступний раз правду або він збреше. Якщо прийшов час хитруну казати правду і у відповідь на запитання «Я в селі лицарів?», хитрун скаже «так», то мандрівник якраз в цьому селі. Якщо хитруну прийшов час брехати,  і на запитання «Чи ми в селі лицарів?" він скаже «ні», то мандрівник також в цьому селі. В інших випадках мандрівнику знадобиться ще одне запитання, четверте.

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

Нагадаємо які вони:

— Ти хитрун?

— Ти хитрун?

— Ми в селі лицарів?

—  Ми в селі брехунів?

Правильна відповідь: 4 запитання.

p.s. Маєте інші версії? Чудово! Пишіть в коменти або приходьте на i7.juniors!

Незважаючи, що кліп було опубліковано ще в 2013 році, пропоную згадати стильну реалізацію цікавої ідеї:

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

Успіхів!

Анатолій Анатолійович.

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

Давайте спростимо умову до загальноголюдського  розуміння. Якщо в певній групі людей, наприклад в шкільному класі буде 500 учнів, то яка вірогідність того, що два учні будуть мати однаковий день народження, тобто однакове число і один місяць? Звичайно,  100%. Ми зараз не говоримо про те, як буде виглядати нещасний класний керівник такого великого класу :) , ми про математику. А якщо в класі буде 366 дітей, а рік приймемо за 365 днів, то яка вірогідність? Так, знову 100%. У варіанті, коли дні народження перших 365 дітей розподіляться рівномірно на весь рік: 1 січня, 2 січня і т.д., то 366 по списку дитині вільних днів вже не залишиться, а це означає що його день народження співпаде з днем народження іншої дитини в класі. А тепер припущення:

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

На перший погляд – це неправда. Так, у моєї доньки в класі з 30 учнів є дві дівчини, що народилися в один день і місяць. В школі, де я працюю, так само співпадають дні народження двох вчителів інформатики. Але при порівняно невеликій групі з 23 осіб мати вірогідність більше ніж 50% - це, здається, математичною помилкою. Але – ні. В російськомовній Вікі дуже детально все розписано, саме її і раджу для системного аналізу.

А тепер задача з e-olymp.com на цю тему:

Дні народження

https://www.e-olymp.com/uk/problems/1317

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

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

Вхідні дані

Кожен рядок є окремим тестом і містить кількість людей n (1 < n < 400).

Вихідні дані

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

Ліміт часу: 1 секунда

Ліміт використання пам'яті: 64 MB

Джерело: Медведев М.Г. – «Зимняя школа в Харькове 2009»

Класифікація задачі: теорія ймовірностей

Давайте аналізувати.  Вікі права:

У групі з 23 людей ймовірність збігу днів народження у двох людей настільки висока, тому що розглядається ймовірність збігу днів народження у будь-яких двох людей в групі. Ця ймовірність визначається кількістю пар людей, які можна скласти з 23 чоловік. Так як порядок людей в парах не має значення, загальне число таких пар дорівнює числу сполучень з 23 по 2, тобто (23 × 22) / 2 = 253 пари.

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

Сподіваюсь, теорію на вікі вже прочитали. З математичної точки зору при рівномірному розподілі:

Наведене в червоному прямокутнику можна розписати математично:

Ну а на Python наведене в червоному прямокутнику реалізується просто і елегантно:

x = 1
for i in range(2, n+1):
     x *= 1 - (i-1)/365

Все інше – деталі. Робота з файлами описана, хто забув, у Пісочниці, в задачі «Робота з текстовими файлами в Python».

А для тих, хто забув про форматування виводу змінних в Python, існує довідник «input_print».

А в вашому класі скільки учнів? А в вашому класі є співпадіння днів народження?

Ps. Для учасників гуртка i7 здача задачі є обов’язковою, код мені в телеграм, будь ласка, PEP8, ага :)

Цікаві білети. Задача для програмістів, що цікавляться гарними дівчатами.

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

Умова:

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

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

- Цікаво! Чотири четвірки, - подумав Вася, -  може цей цікавий білет є передвісником  якоїсь особливої вдачі? Може це щось означає?

І замислився. А скільки таких білетів в рулоні кондуктора, з чотирма четвірками? А скільки білетів, в яких три трійки в будь-якій послідовності? А п’ять пятірок?  

І придумав Вася таке правило – якщо у білеті лише одна одиниця на будь-який позиції, або лише дві двійки на будь-яких позиціях, і так далі до випадку коли у білеті шість шісток, то цей білет можна вважати цікавим. І подумав Вася – а скільки таких цікавих білетів у рулоні кондуктора?

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

Отже, якщо Вася купить у кондуктора один рулон білетів з номерами від 000000 до 999999 і буде безкоштовно видавати білети всім пасажирам, то таким чином він видасть мільйон білетів.  Порахуйте, скільки в цей чудовий автобус зайде гарних дівчат?

Ви можете дуже просто перевірити свій розв’язок.  Ваше число гарних дівчат  додайте до посилання на адресу сайту «Плетиво» і перевірте. Наприклад, ви вважаєте, що правильна відповідь – 1572. Тоді перейдіть на сторінку

http://pletyvo.in.ua/1572/

Якщо ви розв’язали задачу вірно, ви отримаєте відповідну оцінку і побачите одну з таких дівчат.

Успіхів!

p.s. Підказка для дівчат. Якщо ваш знайомий програміст ніяк не може впоратися з задачею, то можете дати йому підказку для розв’язку: https://oeis.org/A038291

Єдина проблема в тому, що якщо він ту підказку зрозуміє, то він, скоріше за все, взагалі не людина.

 Автор задачі: Анатолій Анатолійович. Дата публікації: 13.09.2018, день програміста.

 --------------------------------------------------------------------------------------------------------------------

Интересные билеты. Задача для программистов, которые интересуется красивыми девушками.

(Инструкция для девушек: дайте эту задачу знакомым программистам. Если они ее не решат, то либо они не программисты, либо не интересуются девушками. В обоих случаях гоните их прочь!)

Условие:

Программист Вася зашел в городской автобус, заплатил за проезд и сел на свободное сиденье.

Так как в автобусе, к сожалению, не было красивых девушек, Вася начал от скуки рассматривать билет, который дал ему кондуктор. Все, наверное, знают, если сумма первых трех цифр равна сумме последних трех цифр, то билет считается счастливым. Если разница между этими суммами - единица, например 123232, то этот билет является предвестником какой-то классной встречи. А программист Вася получил вот такой билет:

- Интересно! Четыре четверки, - подумал Вася, - может этот интересный билет является предвестником какой-то особенной удачи? Может это что-то значит?

И задумался. А сколько таких билетов в рулоне кондуктора, с четырьмя четверками? А сколько билетов, в которых три тройки в любой последовательности? А пять пятерок?

И придумал Вася такое правило — если в билете всего одна единица на любой позиции, или всего две двойки на любых позициях, и так далее до случая когда в билете шесть шестерок, то этот билет можно считать интересным. И подумал Вася - а сколько таких интересных билетов в рулоне кондуктора?

На остановке в автобус зашла настолько красивая девушка, что Вася забыл и о билете и о задаче. Но теперь ему стала совершенно ясна вселенская автобусная логика: после выдачи кондуктором интересного билета в автобус заходит красивая девушка.

Итак, если Вася купит у кондуктора один рулон билетов с номерами от 000000 до 999999 и будет бесплатно выдавать билеты всем пассажирам, то таким образом он выдаст миллион билетов. Посчитайте, сколько тогда в этот замечательный автобус зайдет красивых  девушек?

Вы можете очень просто проверить свое решение. Ваше число красивых девушек добавьте к ссылке на адрес сайта «Плетиво» и проверьте. Например, вы считаете, что правильный ответ - 1572. Тогда перейдите на страницу

http://pletyvo.in.ua/1572/

Если вы решили задачу верно, вы получите соответствующую оценку и увидите одну из таких девушек.

Успехов!

p.s. Подсказка для девушек. Если ваш знакомый программист никак не может справиться с задачей, то можете дать ему подсказку для решения: https://oeis.org/A038291

Единственная проблема в том, что если он эту подсказку поймет, то он, скорее всего, вообще не человек.

Автор задачи: Анатолий Анатольевич. Дата публикации: 13.09.2018, день программиста.

Задача, на перший погляд, звичайна — необхідно знайти цілі додатні значення для яблука, банана і ананасу:

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

Наступне рівняння в своїй роботі 2014 року аналізували математики Ендрю Бреммер з університету Арізони і Аллан Макліод з Університету Західної Шотландії:

Вчені знайшли рішення для різних N від 4 до 200.

Мінімальні цілі позитивні a, b, с для N = 4 складаються з 79-81 цифр:

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

За допомогою Python, що має "з коробки" довгу математику, нескладно перевірити, чи дані числа дійсно підходять:

Все добре. В результаті чотири виходить.

До речі, при N=4 максимальне число розрядів чисел a,b,c дорівнює 81. При N=178 максимальне число розрядів буде 398605460.

Дякуємо за цікавинку шановній Медузі.

Відео і схема орігамі для створення діючого свистка.