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

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

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

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 какая-то ошибка

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

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

Ответить
1
Развернуть ветку
Иванка Сегодина

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

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

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

Ответить
0
Развернуть ветку
Иванка Сегодина

Ясно, спасибо.

Ответить
0
Развернуть ветку
Еврейский кот

Комментарий удален по просьбе пользователя

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

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

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

Готово :)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответить
0
Развернуть ветку
Читать все 16 комментариев
Для чего «Знаем лично» запускает отдельные аккаунты Instagram в разных городах

В конце ноября такой журнал появился в Казани и стал четвертым аккаунтом проекта вслед за Москвой, Санкт-Петербургом и Краснодаром. В чем ценность аккаунтов для локального бизнеса, рассказали контент-продюсер, SMM-менеджер и продакт проекта МТС Знаем лично.

«Кинопоиск» стал лидером по количеству подписчиков среди онлайн-кинотеатров в 2021 году — GfK Статьи редакции

Пользователи больше всего слышали про «Кинопоиск», ivi и Okko.

Как бесплатно пиарить бренд за счет чужих новостей. Простое руководство по ньюсджекингу

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

Как украли мою покупку в Сбермегамаркете
Бренд и лояльность клиентов ценнее финансов: история любимой покупки Баффета — кондитерской See’s Candys Статьи редакции

В 1972 году инвестор сделал нехарактерное для себя вложение — купил небольшое производство шоколадных конфет. Баффет не стал расширять компанию, а сохранил её небольшой, сделав ставку на качество. Благодаря этому она хоть и медленно, но стабильно росла, а на заработанные деньги Баффет в 1980 годах купил акции Coca-Cola.

Магазин See’s Candies
Digital Horizon повторно инвестировал в чекаут-платформу Bolt в новом раунде на $355 млн

За три месяца, прошедших с раунда D, оценка компании удвоилась.

Райан Бреслоу, CEO Bolt
Как чат-боты помогают МФО: скоринг, оформление займов и проверка документов в боте

Идея с оформлением микрозаймов через чат-бота в мессенджере упрощает взаимодействие заемщика и МФО и позволяет эффективнее оценивать кредитоспособность клиентов. Стоит ли интегрировать чат-ботов в свои внутренние процессы? Насколько они полезны для владельцев бизнеса? Какие обязанности можно и нужно делегировать чат-ботам для выдачи кредитов? В…

Обзор трёх месяцев суда над Элизабет Холмс: что нового рассказали инвесторы, партнёры и работники о ней самой и Theranos Статьи редакции

Экс-сотрудники говорили о преследованиях и давлении, совет директоров не разбирался в деталях, а Холмс рассказывала про тяжёлое прошлое и влияние бывшего партнёра на неё.

В Великобритании отменят сбор с владельцев телевизоров в пользу BBC — это около 75% выручки компании Статьи редакции

Сбор действует в стране с 1946 года.

Цифровые продукты — создано людьми. Какие ИТ-специалисты нужны ДОМ.РФ и стройотрасли сегодня

Эксперты ДОМ.РФ рассказали о цифровых разработках в компании и о том, какие ИТ-специалисты нужны Институту развития прямо сейчас.

null