Как надевают носки настоящие программисты
easy

Как надевают носки настоящие программисты

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

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

Представьте, что вы затеяли переезд, сложили все вещи по ящикам и коробкам и отвезли их в новое место. Там беспорядок: коробки лежат друг на друге, что-то свалено в углу, и до некоторых ящиков сложно добраться. В одном из таких ящиков вперемешку лежат носки разного цвета: пять синих, шесть жёлтых, семь красных и восемь чёрных. Так уж получилось.

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

Вопрос: сколько максимально нужно достать носков из ящика, чтобы получить пару одинакового цвета? А что, если требуется взять с собой запасной комплект и он тоже должен быть одного цвета?

Для одной пары

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

А теперь какой бы носок мы ни вытащили следующим, его цвет в любом случае совпадёт с тем, что у нас уже есть в руках. Например, пятым оказался жёлтый — а он у нас уже есть. Всё, пара готова, мы направляемся к выходу, и для этого нам потребовалось вытащить максимально пять носков. Это было легко.

Для двух пар

Две пары могут быть разного цвета — давайте это учтём при решении.

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

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

По-научному такой перебор носков и поиск пары называется комбинаторика. Она изучает все возможные комбинации из любых объектов и количество таких сочетаний. В ней есть специальные формулы, которые позволяют легко находить ответ без долгих рассуждений или подсчётов в уме. Например, с помощью комбинаторики можно быстро определить количество выигрышных комбинаций в «Русском лото» или подобрать пары дежурных в классе таким образом, чтобы их состав не повторялся как можно дольше. Мы ещё вернёмся к комбинаторным задачам в будущем.
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Задача о двоичной мыши и тысяче пробирок

Самое лучшее объяснение двоичной системы счисления.

hard
Делаем собственный таймер для спорта
Делаем собственный таймер для спорта

Без рекламы и встроенных покупок.

hard
Как взорвать ракету одной переменной
Как взорвать ракету одной переменной

Краткий мастер-класс по правильному объявлению типов данных.

easy
Откуда взялась лишняя долька шоколада?
Откуда взялась лишняя долька шоколада?

Задача про то, как незаметно съесть кусочек шоколада

medium
9 простых задач на математику

Всё настолько просто, что половину можно решить в уме.

easy
Задача про тест на собеседовании
Задача про тест на собеседовании

Пришёл программист на собеседование, и началось.

medium
Зубодробительная задачка с очень простой математикой

Эта задача поставит в тупик половину интернета, но не вас.

medium
Задача про соседских тараканов
Задача про соседских тараканов

Простая математика, но непростая логика. Проверьте, получится ли у вас.

easy
Задача о деньгах

Пропало 300 рублей, но никто этого не заметил.

medium
easy