Question

В некоторой компании у каждого сотрудника, кроме генерального директора, есть ровно один непосредственный начальник. Также известно, что начав с любого сотрудника компании, можно, переходя к его начальнику, начальнику его начальника и т д дойти до генерального директора. По правилам компании, ни у одного сотрудника не может быть более 3 непосредственных подчиненных. Известно, что компания построена так, что длина максимальной цепочки от подчиненного до генерального директора минимальна. Какова эта длина, если в компании 2584 сотрудников? Уточнение: длиной цепочки называется количество сотрудников в этой цепочке (считая генерального директора).

Answer 1

Длину цепочки можно вычислить с помощью программы:
var n,l,k,st:integer;
begin
n:=2584; l:=1; st:=1; k:=1;
while k<n do
 begin
 st:=st*3;
 k:=k+st;
 l:=l+1;
 writeln(k,' - ',l);
 end;
writeln('l=',l);
end.

Результат:
4 - 2
13 - 3
40 - 4
121 - 5
364 - 6
1093 - 7
3280 - 8
l=8
Т.е., дина цепочки = 8
Можно и без программы, просто складывать степени числа 3.

Answer 2

Для решения данной задачи, можно использовать понятие чисел Фибоначчи.

Числа Фибоначчи - это последовательность чисел, в которой каждое число является суммой двух предыдущих чисел. Первые два числа равны 1.

Для решения задачи, заметим следующие свойства:

1) Чтобы минимизировать длину цепочки, необходимо использовать числа Фибоначчи как количество непосредственных подчиненных каждого сотрудника (исключая генерального директора).

2) Поскольку число сотрудников в компании равно 2584, мы можем использовать числа Фибоначчи до 2584 и найти наибольшее число из них, которое будет меньше или равно 2584.

3) Длина цепочки будет равна позиции найденного числа Фибоначчи плюс один (так как мы считаем генерального директора в цепочке).

Используя эти свойства, найдем максимальное число Фибоначчи, которое меньше или равно 2584:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584

Наибольшее число меньше или равно 2584 - это 1597.

Итак, длина цепочки будет равна 1597 + 1 = 1598.