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

✨Задача о том, как надевают носки настоящие программисты✨

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

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

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

Решение

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

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

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

Для двух пар

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

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

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