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