Форум умных людей

У повара в подчинении десять поварят, некоторые из которых дружат между собой. Каждый рабочий день повар назначает одного или нескольких поварят на дежурство, а каждый из дежурных поварят уносит с работы по одному пирожному каждому своему недежурящему другу. В конце дня повар узнает количество пропавших пирожных. Как сможет он понять, кто из поварят дружит между собой, а кто нет?

присвоим поварятам номера от 1 до 10. В первый день повар назначает дежурными первые девять номеров. По количеству пропавших пирожных он узнает количество  друзей у №10. Затем назначает на дежурство первые 8 номеров. Если количество пропавших  пирожных уменьшилось, значит № 9 дружит с №10, если нет, то не дружит. И т.д., пока не выявятся все друзья №10.
Так же повторить с другими номерами за исключением выявленных "недругов".

А если увеличилось?
Более того, если кол-во пироженных не уменьшилось, это нам ничего не говорит.

Увеличиться не может. Сначала дежурят первые 9 номер, каждый "друг" уносит по ОДНОМУ пирожному.
И если с №10 дружат все номера с №1 по №9, то более 9 пирожных они не унесут.

Почему это не может?
Если все дружат со всеми.
То в впервый раз (1-9)они унесут 9 пироженных
Во второй раз (1-8) они унесут 16 пироженных

В принципе, дружбу всех со всеми легко выявить, оставляя по 9 дежурных. При это будет пропадать 9 пирожных каждый раз при замене недежурного номера.
А вот как быть с группой?

Сначала нужно выявить количество друзей у каждого номера. Для этого поочередно оставлять дежурить по 9 номеров.

Я лишь привёл контр пример к
И тоже ложное утверждение

Сначала выявляем количество друзей у каждого номера, оставляя по очереди дежурить каждый номер. Потом дежурят №3-№10. Если количество пропавших пирожных будет меньше суммарного количества друзей у №1 и №2, то они друзья. Затем недежурная пара №1 и №3. И т.д., пока не выявим всех друзей у №1. И так с каждым номером.

Сначала, как предложил, выявляем количество друзей у каждого номера, оставляя по очереди дежурить каждый номер. Потом дежурят 1 и 2. Если общая сумма их пирожных уменьшилась на 2 - значит они друзья. Осталась без изменения- не друзья.
Дальше проверяем 1 и 3...1 и 4... и т.п.

 :bye: это тоже самое, что и у меня, только с другой стороны.

А скока дней для этого понадобится?

ну..на вскидку:
максимум: 9+8+7...2 = 44

Интересно как! В авторском решении больше выходит. :-\

Та не..Это я психанул...
9+8+8...8= 81
???

А тогда в авторском поменьше будет.

9*(9+1)/2+10=55

И это не минимум.

Точно. Когда дойдем до №8, станет понятно по остатку друзей, кто с кем дружит.
Если 2,2,2-№8,№9и №10 дружат друг с другом.
Если 2,1,1 - №8 дружит и с №9,и с №10.
Если 1,2,1 - №9 дружит с №8 и с №10.
Если 1,1,2 - №10 дружит с №8 и с №9.
Т.е. 55-3=52дня.

46 ???

первые 10 дней идет проверка на вшивость каждого поваренка. потом плюсуются пары.

Понятно.
10 проверок +
1-й день - 9 - а (а- кол-во друзей первого повара. Ессно- чем меньше а, тем больше проверок, если а не равно 9). Итак макс. проверок в 1 день = 8.
2- й день. Предположим у 2 - го поварешки тоже только один друг. То есть проверок нужно, 9- 1- 1 уже проверенный...
Итого всего проверок получается: 46...

да нет же.
10+
арифметическая прогрессия от 9 до 1 за вычетом проверки №8, №9 и №10

у меня 45 получилось

Как?

ставим дежурить поодиночке 9 (9 дней), затем из этих 9 все возможные пары (36 дней) = 45 дней

Берем любых двоих, если сумма пропавших в день когда они дежурили поодиночке = сумме когда они дежурили вдвоем, то значит они не друзья

Теперь с 10 - берем любого из 9 и смотрим сколько пропало у него в день одиночного дежурства, сверяем с количеством друзей из 9. Совпало - 10 не друг, не совпало - 10 друг.

Зачот!!! :beer:

Я чего- то тупанул, что достаточно 9 проверок, а не 10 одноразовых.
в остальном все правильно вроде:
проверка 1- го поваренка (если друзей 9 - проверять нечего) - 8 проверок максимально может быть, невзирая на кол-во друзей от 1 до 8.
2- го поваренка на одну проверку меньше 7.
Итого: 45.