Question

Суть задачи такова:"На учредительном собрании партии “Верный путь” 141 участник из 29 регионов второй день пытаются рассесться за круглым столом так, чтобы среди любых 35 подряд сидящих участников были представители всех регионов. Удастся ли этим достойным людям исполнить задуманное?"

Answer 1

Представим, что такое возможно. 141:29=4 (ост.25) значит, в какой то делегации будет точно 4 человека. Теперь между этими четырьмя людьми надо рассадить оставшихся по одному члену от каждой делегации. 141-4=137 осталось рассадить. Но 137:4= 34 (ост. 1) , а если есть остаток, то в одном из промежутков между нашими выбранными делегатами сидит 35 человек, а наш делегат будет 36-ым. А это не соответствует условию задачи. Значит, ответ НЕТ

Answer 2

Для решения этой задачи, давайте определим, можно ли удовлетворить условию, что среди любых 35 подряд сидящих участников должны быть представители всех 29 регионов. Мы можем использовать принцип Дирихле (или Лемму о среднем), чтобы определить, удастся ли это или нет.

Принцип Дирихле (Лемма о среднем) гласит, что если есть N объектов, которые должны быть распределены по K ячейкам, и N > K * (M - 1), где M - минимальное количество объектов, которые должны быть в каждой ячейке, то как минимум одна из ячеек содержит больше M объектов.

В данной задаче у нас есть 141 участник, которых мы хотим разместить в 29 регионах так, чтобы в любых 35 подряд сидящих участниках были представители всех 29 регионов. Мы можем представить это как 29 "ячеек" и 141 "объект" для размещения.

Используем принцип Дирихле:

N = 141 (количество участников) K = 29 (количество регионов) M = 35 (минимальное количество подряд сидящих участников)

N > K * (M - 1) 141 > 29 * (35 - 1) 141 > 29 * 34 141 > 986

Условие не выполняется, так как 141 не больше 986. Из этого следует, что невозможно удовлетворить требованию, чтобы в любых 35 подряд сидящих участниках были представители всех 29 регионов.