Андрей вырос и носит носки одного цвета. Также он докупил очень много носков, и теперь его гардероб состоит их 20 оранжевых, 30 красных, 40 желтых, 40 синих, 30 фиолетовых и 20 белых носков. Но гардероб всё еще не освещается. Какое минимальное количество носков ему нужно взять, чтобы получить 8 пар носков, если он не может в процессе взятия носка различить его цвет? Один носок не может учитываться в двух разных парах.

Задача сводится к минимизации числа образованных пар при выборе N носков из ограниченного набора цветов. Данные: - Цветов 6: оранжевые 20, красные 30, желтые 40, синие 40, фиолетовые 30, белые 20. - Пусть за выбранное N носков по каждому цвету получено c_i носков, 0 ≤ c_i ≤ M_i и sum c_i = N. - Число пар это P = sum floor(c_i/2). - Обозначим U = количество цветов, у которых c_i нечетное (т.е. c_i mod 2 = 1). Тогда P = (N - U)/2, поскольку sum (c_i) = 2P + U. Максимально Possible U для заданного N: - Есть 6 цветов, поэтому U ≤ 6. - Parity: N и U должны иметь одну и ту же четность (сумма всех c_i mod 2 равна N mod 2, а это равно количеству нечетных c_i mod 2). - Для N ≤ 6 можно сделать c_i = 1 у N цветов, значит U = N. - Для N > 6: - если N чётное, можно сделать U = 6 (дать по 1 носку каждому цвету и добавлять носки парами, не меняя чётность ни одного c_i); - если N нечётное, максимум U = 5 (при добавлении носка в любом цвете одна пара сойдётся на другую четность и одна цвет останется с чётностью 0, итого у = 5). Следовательно, минимальное P для данного N: - Если N ≤ 6: P_min = (N - N)/2 = 0. - Если N > 6 и N чётное: P_min = (N - 6)/2. - Если N > 6 и N нечётное: P_min = (N - 5)/2. Ищем N такое, чтобы P_min ≥ 8. - Для N чётного: (N - 6)/2 ≥ 8 → N ≥ 22. То есть минимальное подходящее чётное N — 22. - Для N нечётного: (N - 5)/2 ≥ 8 → N ≥ 21. То есть минимальное подходящее нечётное N — 21. Наименьшее возможное N, обеспечивающее не менее 8 пар в любом случае, равно 21. Проверка на практическую реализуемость: - Возьмём 21 носок: например, 5 цветов по 1 носку (1, 1, 1, 1, 1) и один цвет по 16 носков (16). Это feasible, так как каждый M_i ≥ 16. - В таком распределении пары образуются только из 16 носков одного цвета: floor(16/2) = 8 пар. Остальные 5 носков дают 0 пар. - Значит можно получить ровно 8 пар, и в худшем случае это минимально возможно для N = 21. Ответ: минимальное количество носков, чтобы гарантированно получить 8 пар, равно 21.