Задачка на худшее число оцениваний

[pierrevanstulov]

Такая задачка: модель надевает на себя $n$ видов вещей. Каждый $i$-й вид вещи имеет $m_i$ фасонов. Кутюрье смотрит на модель и указывает, какие пары вещей не сочетаются. После чего модель переодевается так, чтобы в новом обличье не было тех пар, которые кутюрье "отбраковал" на предыдущих шагах, и все повторяется.

Вопрос: какое количество оценок придется сделать кутюрье в худшем случае?

Моя гипотеза: чтобы вычислить это количество упорядочим $m_i$ по убыванию, получив ряд $(m^{(1)}, m^{(2)}, m^{(3)},..., m^{(n)})$. Худшее количество оценок = $m^{(1)}m^{(2)}+(m^{(3)}-1)(m^{(4)})+...+(m^{(n-1)}-1)(m^{(n)})$, если $n$ - четно; и $m^{(1)}m^{(2)}+(m^{(3)}-1)(m^{(4)})+...+m^{(n)}-1$, если $n$ - нечетно.

Я ее вывел чисто эмпирически, попробовав построить самую длинную последовательность оценок в случае, если $m_1=4, m_2=3, m_3=2, m_4=2$. У меня получилась такая вот последовательность (пары фасонов, которые кутюрье отбраковал при оценке омечены "-"): $(1-,1-,1,1), (1-,2-,1,1), (1-,3-,1,1), (2-,1-,1,1), (2-,2-,1,1), (2-,3-,1,1), (3-,1-,1,1)$ $ (3-,2-,1,1), (3-,3-,1,1), (4-,1-,1,1), (4-,2-,1,1), (4,3-,1-,1), (4,3,2-,1-), (4,3,2,2) $.

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