Зарядка для мозга во время самоизоляции: шесть задач от школы анализа данных «Яндекса»

Привет, я куратор школы анализа данных «Яндекса». Самоизоляция — отличный повод немного прокачаться, поэтому я подобрал для вас задачи, которые помогут отвлечься от тревожных новостей с пользой для мозга.

Кстати, похожие задачи будут в этом году на вступительном экзамене в ШАД, где для людей с опытом в ИТ мы придумали новый трек, который поможет им улучшить свои знания математики.

1. В ряд выложены пять красных, пять синих и пять зеленых шаров. С какой вероятностью никакие два синих шара не лежат рядом?

В подобных задачах обычно не нужны глубокие познания — достаточно хорошо понимать, что такое размещения, перестановки и сочетания. Но все же требуется большая аккуратность при работе с элементарными событиями, то есть базовыми равновероятными исходами, из которых мы и будем конструировать события в задаче. В противном случае легко впасть в заблуждения в духе «вероятность 50%: либо произойдет, либо нет».

В этой задаче можно сэкономить время и нервы, если решать её «конструктивно»: представив, что составляете расстановку шаров, удовлетворяющую условиям.

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

2. Электрическая цепь представляет собой связанный неориентированный граф без кратных ребер, в котором ребра (числом N) — это провода, а вершины — это либо лампочки, либо единственный источник тока. На каждом ребре размещено реле.

Лампочка горит, если существует путь, соединяющий ее с источником тока, вдоль которого все реле находятся в положении «включено». Известно, что ровно одно из реле бракованное и никогда не пропускает ток. Вы можете включать и отключать реле и видеть, горят ли лампочки. Изначально все выключатели находятся в положении «включено». Опишите способ нахождения неисправного реле за О(N) операций включения-выключения.

Задачи по алгоритмам очень хороши тем, что они проверяют не только умение понятно описать некую процедуру, но и объяснить, почему она работает.

Если граф — дерево, то бракованное реле находится перед первой (от источника тока) не горящей лампочкой. Если есть циклы, то можно выключить все рёбра и запустить аналог поиска в глубину.

3. Докажите, что среди шести человек обязательно найдутся трое попарно знакомых или трое попарно незнакомых.

Задачи на графы, особенно если количество вершин небольшое, чаще всего стараются свести к разбору случаев. Важно, чтобы вы смогли внимательно разобрать их и при этом не запутаться.

Впрочем, эту классическую задачу можно решить и очень коротким элегантным способом (достаточно рассмотреть одного человека и троих его знакомых, а если таких меньше трёх, то «инвертируем» граф знакомств, заменив все рёбра их отсутствиями и наоборот — задача от этого не поменяется). Если его найдете, сэкономите много времени!

4. На столе лежат четыре карточки, на которых сверху написано «А», «Б», «4», «5». Про то, что написано на обратных сторонах, ничего не известно. Какое наименьшее количество карточек надо перевернуть, чтобы проверить истинность утверждения «Если на одной стороне карточки написано четное число, то на другой — гласная буква»?

Еще одна задачка на тонкости логической связки «если — то». Тут важно разобраться, что под условие подходят карточки вида:

  • четное число, гласная буква;
  • нечетное число, что угодно.

И не подходят карточки вида:

  • четное число, согласная буква.

Теперь становится ясно: что бы ни было написано на обороте карточек «А» и «5», это не влияет на ситуацию; а чтобы проверить условие, нам достаточно перевернуть карточки «Б» и «4» и проверить, нет ли на обороте четного числа и согласной буквы соответственно.

5. Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками.

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

6. Квадратная матрица такова, что след tr(AX) = 0 для любой матрицы X того же размера, имеющей нулевой след (след матрицы — сумма элементов на главной диагонали).

Докажите, что матрица является скалярной (т. е. имеет вид λE для некоторого λ, где E — единичная матрица).

Несмотря на то что это как будто бы задача на линейную алгебру, на самом деле ее суть в том, чтобы правильно разобраться со словами: «…такова, что для любой… такой, что». И не слишком-то важно, что речь идет о матрицах и следах. Если что-то верно для любой матрицы, удовлетворяющей некоторому условию, это верно и для каждой конкретной матрицы.

Таким образом, встретив подобную задачу, стоит сначала взять какие-нибудь конкретные (и желательно очень простые) матрицы X с нулевым следом и попробовать понять, что же нам дает условие tr(AX) = 0. В качестве таких матриц удобно взять матричные единицы (и матрицы, у которых на диагонали все нули, кроме двух элементов, равных 1 и (-1).

Собственно говоря, на этом задача и закончится: из условий tr(AX) = 0, которые вы распишете для таких матриц, сразу будет следовать ответ.

0
16 комментариев
Написать комментарий...
Роман Тютюнов

В задаче 5 какая-то ошибка

Ответить
Развернуть ветку
Стас Федотов

Роман, спасибо! Конечно, тут "двумя" выпало. Вот пример того, как стилистические правки могут исказить суть.

Ответить
Развернуть ветку
Аккаунт удален

Комментарий недоступен

Ответить
Развернуть ветку
Стас Федотов

Всё корректно) В переводе с математического жаргона это как раз и значит "два синих шара никогда не лежат рядом"

Ответить
Развернуть ветку
Аккаунт удален

Комментарий недоступен

Ответить
Развернуть ветку
Аккаунт удален

Комментарий недоступен

Ответить
Развернуть ветку
Кирилл Казаков

А вы не могли бы перенести формулировки задач, например, во врезки? В заголовках они занимают слишком много места.

Ответить
Развернуть ветку
Стас Федотов
Автор

Готово :)

Ответить
Развернуть ветку
Кирилл Казаков

Здорово, спасибо большое!

Ответить
Развернуть ветку
Victoria Vasilenko

А что за новый трек в ШАДе?

Ответить
Развернуть ветку
Стас Федотов

Мы создали его в этом году для тех, кто уже имеет опыт в IT и хочет развиваться дальше, но не так хорошо владеет высшей математикой, чтобы пройти через наш стандартный процесс отбора. При отборе мы будем учитывать умение программировать и знакомство с основами анализа данных, участие в проектах и наличие научных статей; математика же будет проверяться на гораздо более базовом уровне; собственно говоря, решать придётся задачи, похожие на задачи в этом посте. Поступивших ждёт адаптационный курс по высшей математике, который мы разработали специально для этого трека и который поможет им потом без проблем влиться в ШАДовский учебный процесс. Вот тут вы можете почитать подробнее про процесс поступления в ШАД: http://yandexdataschool.ru/enroll

Ответить
Развернуть ветку
Victoria Vasilenko

Большое спасибо!

Ответить
Развернуть ветку
Эмилия Теплова

Ох и формулировки задач.
Математикам нравятся шарады, но подпускать их к программированию нельзя 😊

Ответить
Развернуть ветку
Sergey Serebryakov

Задача 4: на обороте карточки "5" вполне может быть чётное число, что нарушит истинность утверждения. Так что её тоже надо перевернуть!

Ответить
Развернуть ветку
Tim Finiq

Тоже обратил на это внимание, подождем комментарий от автора)

Ответить
Развернуть ветку
Igor Tarasov

В вашей ШАД много ошибок. Когда вы пишите: "В ряд выложены пять красных, пять синих и пять зеленых шаров.", то это означает что они выложены последовательно. Нужно либо добавлять в перемешку случайным образом. 

Ответить
Развернуть ветку
13 комментариев
Раскрывать всегда