Индукция в комбинаторике

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

База индукции: при перебором убеждаемся, что .

Переход: Пусть неравенство верно для карточек каждого цвета. Докажем, что оно верно, если количество карточек каждого цвета равно . Рассмотрим, как может увеличиться сумма , если добавить по одной карточке каждого цвета.. Без ограничения общности можно считать, что белая карточка добавлена на самый верх стопки, а добавленные чёрная и красная карточки - самые верхние среди карточек своего цвета. Пусть выше первой сверху красной карточки расположено ранее лежащих чёрных, а выше первой сверху чёрной — ранее лежащих белых. Тогда белая карточка добавляет в сумму (учитывая все чёрные, лежащие под ней), чёрная карточка добавляет (учитывая все красные, лежащие под ней) и w, за счёт того, что она лежит под w старыми белыми карточками, а красная карточка добавляет не более, чем за счёт белых, лежащих под ней, и за счёт того, что она лежит под старыми чёрными карточками. Итого, . Учитывая, что , получим: .

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