Главное меню

Какое наименьшее количество имён может быть суммарно во всех списках?

Автор ZadaSIK, Март 15, 2024, 01:02

« назад - далее »

ZadaSIK

За круглым столом 13 одноклассников с разными именами выбирали старосту класса. Каждый написал список с несколькими именами, кто, по его мнению, подходит на эту роль. Известно, что если взять любых двух сидящих рядом ребят, то каждый из остальных ребят написал имя хотя бы одного из этих двоих. Какое наименьшее количество имён может быть суммарно во всех списках?
Каждое имя учитывается столько раз, сколько раз оно написано.

Edayniu

И снова для наглядности нарисуем круглый стол и рассадим ребят по номерам. Извиняюсь за несимметричный рисунок, но сути это не меняет.
Рассмотрим такой пример:
Возьмем первых двух. Остальные это 13-2 = 11 человек. И каждый написал имя хотя бы одного. пусть они все написали имя 1-го. А второго не написал никто.
Сдвинемся на 1 человека и возьмем пару 2 и 3. За второго номера заменился голосующий вместо 3 голосует теперь 1-й. Но и он выбрал не второго :)
И так далее. Таким образом получается такой случай, что голосовали через одного в паре. Условия выполнены. Какую пару не возьмем, то каждый хотя бы одного написал из пары.
Вот только участников нечетное количество и последняя пара 13-й и 1-й получится по 11.
Посчитаем всего. получили 77 имен сумарно.
Но как видим это не оптимальный вариант. Надо постараться минимизировать.
Воообще, понятно, что для минимальности, если у одного х - голосов, то у второго будет (11-х) - голосов, у третьего снова 11-(11-х) = х голосов. И так будет чередоваться.
Но поскольку число ребят нечетное. То Пара 13-й и 1-й будут иметь количество х и х = 2х
И надо, чтоб 2х≥11. Минимально это 2х=12 и х = 6
Тогда 11-х = 5
То есть голоса будут чередоваться 5 и 6 и у последней пары будет 6 и 6
Итого будет 6 участников по 5 голосов = 30 и 7 участников по 6 голосов = 42
Суммарно 30+42 = 72
Ответ: 72 минимально.   
                                                                              

Brurarl

Каждый ученик написал половину имен тех, кто присутствовал, не считая только своего имени. Исходя из этого составляем пример: 1) 13-1:2=6, следующее действие 2) 6*13=78
Ответ: Наименьшее количество имен может быть 78.

Nder

Поскольку "Известно, что если взять любых двух сидящих рядом ребят, то каждый из остальных ребят написал имя хотя бы одного из этих двоих", то "каждых из остальных" - это 11 ребят и, как минимум, 11 имён суммарно в их списках.
Сдвигая на одного по кругу этих "двух сидящих рядом ребят", получим 13 сдвигов, каждый сдвиг давал, как минимум, 11 имен, итого:
13 * 11 = 143
Ответ: минимум 143 имени суммарно во всех списках.