Что это
Этот урок — про умение думать хитро, а не считать долго. Круги Эйлера помогают не посчитать дважды тех, кто ходит сразу в два кружка. Принцип Дирихле говорит: если кроликов больше, чем клеток, где-то сидят хотя бы двое. А чашечные весы, если ими пользоваться с умом, позволяют найти фальшивую монету за удивительно малое число взвешиваний.
Зачем это нужно
Пересечения множеств — основа баз данных: когда интернет-магазин ищет покупателей, которые купили и то и другое, он считает именно пересечение кругов. Принцип Дирихле объясняет, почему в хеш-таблицах и системах хранения неизбежны совпадения и как с ними жить, а идея делить на три части и отбрасывать лишнее — та же, что в быстрых алгоритмах поиска и в поиске неисправностей в больших системах. ИИ отлично перебирает варианты, но придумать, что надо рассмотреть худший случай, и доказать, что ответ верен наверняка, — работа человека с логическим мышлением. Такие люди нужны в программировании, анализе данных, кибербезопасности и инженерии.
Как это работает
Когда складывают участников двух групп, те, кто входит в обе, оказываются посчитаны дважды, поэтому их один раз вычитают. В задачах «сколько достать, чтобы наверняка» представляют самый неудачный случай: сначала попадается всё ненужное, а нужное — последним, значит, нужно всё ненужное плюс одно. Чашечные весы дают три исхода: левая легче, правая легче или поровну. Поэтому монеты делят на три равные кучки, две кладут на весы, одну в сторону, и после каждого взвешивания подозреваемых остаётся втрое меньше.
Немного истории
Леонард Эйлер, один из величайших математиков, в восемнадцатом веке написал больше двухсот писем немецкой принцессе, объясняя ей науку простым языком. В этих письмах он рисовал круги, чтобы показать, как связаны понятия: один внутри другого, пересекаются или не пересекаются вовсе. Письма издали книгой, и с тех пор такие рисунки называют кругами Эйлера.
Формула: круги Эйлера
Если сложить тех, кто ходит в первую группу, и тех, кто ходит во вторую, ученики из обеих групп посчитаются дважды, поэтому пересечение один раз вычитаем. А тех, кто не ходит никуда, нужно прибавить отдельно — они не попали ни в один круг. Получается: всего равно а плюс бэ минус а и бэ плюс ни туда, ни туда. Здесь а и бэ — число людей в каждой группе, а и бэ — те, кто в обеих, а последнее слагаемое — те, кто вне кругов; всё измеряется в людях. Если пересечение увеличить на одного, сумма частей уменьшится на одного.
N = A + B − (A и B) + (ни туда, ни туда)N — всего человек, чел.
A — в первой группе, чел.
B — во второй группе, чел.
A и B — в обеих группах сразу, чел.
ни туда, ни туда — вне обеих групп, чел.
Формула: худший случай
Чтобы получить нужный предмет наверняка, представь самый неудачный случай: сначала тебе попадается всё, что не нужно, и только потом то, что нужно. Значит, ответ равен всему ненужному плюс один: эн равно числу ненужных плюс один. Здесь эн — сколько предметов достать, а ненужные — все предметы, которые нам не подходят, оба в штуках. Если ненужных предметов станет больше, придётся доставать больше. Та же идея худшего случая работает и на весах: противник всегда отвечает так, чтобы подозреваемых осталось как можно больше.
n = (всё ненужное) + 1n — сколько достать наверняка, шт.
всё ненужное — все предметы, которые не подходят, шт.
Что будем делать на практике
А теперь давай попробуем выполнить практическое задание. На схеме три задачи, их переключают кнопки «Круги», «Ящик» и «Весы». В «Кругах» класс из тридцати учеников, футбол и шахматы, пятеро не ходят никуда: меняй кнопками «Оба −1» и «Оба +1» число учеников в пересечении, пока сумма всех частей внизу не совпадёт с тридцатью. В «Ящике» белые, синие и чёрные маркеры: кнопками «Достать −1» и «Достать +1» выбери, сколько доставать, и посмотри справа худший случай. На «Весах» девять монет, одна легче: нажимай на монету, чтобы положить её на левую или правую чашу, жми «Взвесить», уложись в два взвешивания, а потом нажми «Указать фальшивую» и выбери монету. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.