Зарядка для мозга во время самоизоляции: шесть задач от школы анализа данных «Яндекса»
Привет, я куратор школы анализа данных «Яндекса». Самоизоляция — отличный повод немного прокачаться, поэтому я подобрал для вас задачи, которые помогут отвлечься от тревожных новостей с пользой для мозга.
Кстати, похожие задачи будут в этом году на вступительном экзамене в ШАД(школа анализа данных), где для людей с опытом в ИТ мы придумали новый трек, который поможет им улучшить свои знания математики.
В ряд выложены пять красных, пять синих и пять зеленых шаров. С какой вероятностью никакие два синих шара не лежат рядом?
В подобных задачах обычно не нужны глубокие познания — достаточно хорошо понимать, что такое размещения, перестановки и сочетания. Но все же требуется большая аккуратность при работе с элементарными событиями, то есть базовыми равновероятными исходами, из которых мы и будем конструировать события в задаче. В противном случае легко впасть в заблуждения в духе «вероятность 50%: либо произойдет, либо нет».
В этой задаче можно сэкономить время и нервы, если решать её «конструктивно»: представив, что составляете расстановку шаров, удовлетворяющую условиям.
Например, так: сначала расположим красные и зелёные шары (надо выбрать из десяти пять мест, в которых будут красные), после чего пять синих шаров надо положить не более, чем по одному, в одиннадцать промежутков между красными и зелёными шарами, а также слева и справа (то есть выбрать пять мест из одиннадцати).
Электрическая цепь представляет собой связанный неориентированный граф без кратных ребер, в котором ребра (числом N) — это провода, а вершины — это либо лампочки, либо единственный источник тока. На каждом ребре размещено реле. Лампочка горит, если существует путь, соединяющий ее с источником тока, вдоль которого все реле находятся в положении «включено». Известно, что ровно одно из реле бракованное и никогда не пропускает ток. Вы можете включать и отключать реле и видеть, горят ли лампочки. Изначально все выключатели находятся в положении «включено». Опишите способ нахождения неисправного реле за О(N) операций включения-выключения.
Задачи по алгоритмам очень хороши тем, что они проверяют не только умение понятно описать некую процедуру, но и объяснить, почему она работает.
Если граф — дерево, то бракованное реле находится перед первой (от источника тока) не горящей лампочкой. Если есть циклы, то можно выключить все рёбра и запустить аналог поиска в глубину.
Докажите, что среди шести человек обязательно найдутся трое попарно знакомых или трое попарно незнакомых.
Задачи на графы, особенно если количество вершин небольшое, чаще всего стараются свести к разбору случаев. Важно, чтобы вы смогли внимательно разобрать их и при этом не запутаться.
Впрочем, эту классическую задачу можно решить и очень коротким элегантным способом (достаточно рассмотреть одного человека и троих его знакомых, а если таких меньше трёх, то «инвертируем» граф знакомств, заменив все рёбра их отсутствиями и наоборот — задача от этого не поменяется). Если его найдете, сэкономите много времени!
На столе лежат четыре карточки, на которых сверху написано «А», «Б», «4», «5». Про то, что написано на обратных сторонах, ничего не известно. Какое наименьшее количество карточек надо перевернуть, чтобы проверить истинность утверждения «Если на одной стороне карточки написано четное число, то на другой — гласная буква»?
Еще одна задачка на тонкости логической связки «если — то». Тут важно разобраться, что под условие подходят карточки вида:
- четное число, гласная буква;
- нечетное число, что угодно.
И не подходят карточки вида:
- четное число, согласная буква.
Теперь становится ясно: что бы ни было написано на обороте карточек «А» и «5», это не влияет на ситуацию; а чтобы проверить условие, нам достаточно перевернуть карточки «Б» и «4» и проверить, нет ли на обороте четного числа и согласной буквы соответственно.
Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками.
Задачка на геометрическую интуицию: надо понять, что ни один из меньших треугольников не может покрыть сразу две вершины. После этого становится ясно: чтобы покрыть все три вершины, нужно хотя бы три треугольника. А вообще тут зарыто непростое утверждение о диаметре треугольника, но его можно не доказывать.