7 человек в лесу

[waxtep]

(без доказательства) видимо, все разнообразие общего случая исчерпывается вариантами $7$ или $8$ грибников (они существенно различны). В любом варианте, достаточно рассматривать наборы, в которых минимальное из количеств набранных грибов является максимально возможным для данного $n$. Далее, для варианта "$7$ грибников" решение дается способом DeBill (одна дырка единичного размера между левыми и правыми грибниками), а для варианта $8$ грибников - способом Geen (одна дырка единичного размера перед самым правым из левых грибников).
Добивая до ответа, пусть общее число грибников - $Q$, и мы желаем иметь всегда не менее половины у $R$ из них. Далее, введем $L=Q-R,n_0=\frac {Q(Q+1)} 2,S^2=LR+\frac{R(R+1)}2-\frac{L(L-1)}2$, тогда искомое $n$ будет:

$$n=n_0-L+\max \left \{Q\left \lfloor{\frac{S^2-1}{L-R}}\right \rfloor+1,Q\left \lfloor{\frac{S^2}{L-R}}\right \rfloor\right \}$$

[daogiauvang]

provincialka Да еще нужно. Спасибо большое.

[provincialka]

Пишу решение для daogiauvang

Пусть грибники набрали $a_1<a_2<a_3<a_4<b_1<b_2<b_3$ грибов, максимальное число грибов, набранное троими грибниками, равно $B=b_1+b_2+b_3$, остальные четверо набрали $A=a_1+a_2+a_3+a_4$, причем $A+B = n$.
Условие задачи нарушится, если слагаемые можно подобрать так, что $A$ составляет больше половины от $n$, при этом $A>B$. Попробуем построить такое разбиение на слагаемые.

Идея. Значения $a_i$ надо сделать как можно больше, а $b_j$ -- как можно меньше, но при этом $a_4<b_1$.

Строгое рассуждение.

Рассмотрим случай $n = 2k$. Тогда $A\geqslant k+1, B\leqslant k-1$. Но $a_3\leqslant a_4-1, a_2\leqslant a_4-2,a_1\leqslant a_4-3$, так что $A\leqslant 4a_4-6$. Аналогично $B\geqslant b_1+(b_1+1)+(b_2+2)=3b_1+3$.

Итак, $4a_4-6\geqslant k+1, 3b_1+3\leqslant k-1$. Значит, $a_4\geqslant \frac{k+7}4$, причем оно целое. Аналогично $b_1\leqslant \frac{k-4}{3}$, и тоже целое. "Плохое" распределение грибов получится, если можно подобрать $a_4,b_1$ так, что $a_4<b_1$.

Число $n=2k$ удовлетворяет условию задачи, если каждое целое $a_4$ такое, что $a_4\geqslant \frac{k+7}4$ не меньше каждого целого $b_4$ такого, что $b_1\leqslant \frac{k-4}{3}$.

Самое маленькое $a_4$ есть $a_4 = \left\lceil {\frac{k+7}4}\right\rceil$. Эти скобки обозначают "потолок", целое число, которое не меньше $\frac{k+7}4$

Самое большое $b_1$ есть $b_1=\left\lfloor\frac{k-4}{3}\right\rfloor$, скобки -- целая часть,"пол".

Число $n=2k$ нельзя будет разложить в "неправильную" сумму, если

$$ \left\lfloor\frac{k-4}{3}\right\rfloor\leqslant\left\lceil \frac{k+7}{4}\right\rceil \eqno(1)$$

Дальше можно рассуждать по-разному. Более простое рассуждение: оценить число $k$ сверху и проверить, выполняется ли (1). Заметим, что $ \left\lfloor x\right\rfloor > x-1,\left\lceil x\right\rceil <x+1 $. Значит, $\frac{k-4}{3}-1<\frac{k+7}{4}+1$, откуда $k<61$, т.е. $k\leqslant 60$.

Будем проверять их одно за другим.
$k=60, \left\lceil \frac{k+7}{4}\right\rceil =\left\lceil \frac{60+7}{4}\right\rceil = 17, \left\lfloor\frac{k-4}{3}\right\rfloor=\left\lfloor\frac{60-4}{3}\right\rfloor=18$. Условие (1) не выполняется.

Так можно проверить и другие $k$, подойдет только $k=54$ или меньше. Значит, наибольшее четное $n$ равно $108$.

Для нечетных $n$ исследование дает значения ещё меньше, так как разница между $A$ и $B$ ещё меньше, может быть равна 1.

Можно произвести оценку более аккуратно, и сразу получить $k\leqslant 54$. Но вы пока разберитесь в этом решении.