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

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

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

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

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

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

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

Решение

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

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

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

Для двух пар

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

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

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

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

Ещё по теме