2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: 7 человек в лесу
Сообщение05.10.2016, 05:50 
Аватара пользователя


07/01/16
881
Аязьма
(без доказательства) видимо, все разнообразие общего случая исчерпывается вариантами $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 \}$$

 Профиль  
                  
 
 Re: 7 человек в лесу
Сообщение05.10.2016, 09:15 
Аватара пользователя


21/06/08
476
Томск
provincialka Да еще нужно. Спасибо большое.

 Профиль  
                  
 
 Re: 7 человек в лесу
Сообщение05.10.2016, 14:51 
Заслуженный участник
Аватара пользователя


18/01/13
11840
Казань
Пишу решение для 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$. Но вы пока разберитесь в этом решении.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group