2014 dxdy logo

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

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




 
 Формализовать наивное решение комбинаторной задачи
Сообщение16.02.2015, 09:07 
Здравствуйте.
Помогите поставить на строгие математические рельсы мои наивные рассуждения применительно к следующей задаче.
Спасибо.

Сама задача:
Цитата:
$16$ учеников решали контрольную, в которой было $8$ задач. Оказалось, что в итоге каждую
задачу решили ровно $5$ школьников. Сколько задач гарантированно решил самый умный из них?

Мое решение:
Поскольку необходимо найти гарантированное решение, значит необходимо найти наихудший вариант для самого умного — это вариант, когда наилучший ученик решил ненамного больше, чем основная масса учеников.
Эту ситуацию можно представить так:
Поскольку решенных задач получилось $40(=5 \cdot 8)$, можно перенумеровать решения от $1$ до $40$ (решение номер №1, №2, №3, ...) и соотнести каждому решению номер ученика (вторая строчка) таким образом:

$\begin{pmatrix}
\text{Номер решения: } & 1 & 2 & 3 & \ldots & 16 & 17 & 18 & 19 & \ldots \\
& \downarrow & \downarrow & \downarrow & \ldots & \downarrow & \downarrow & \downarrow & \downarrow & \ldots \\
\text{Номер решившего ученика: } & 1 & 2 & 3 & \ldots & 16 & 1 & 2 & 3 & \ldots 
\end{pmatrix}$

Интуитивно мне кажется, что таким образом можно построить худшую ситуацию для самого умного ученика. Если мои правдоподобные рассуждения верны, то получается, что самый лучший ученик решил 3 задачи гарантированно. Потому что:

$\begin{pmatrix}
1 & \ldots & 16 & 17 & \ldots & 32 & 33 & \ldots & 40\\
\downarrow & \ldots & \downarrow & \downarrow & \ldots & \downarrow & \downarrow & \ldots & \downarrow\\
1 & \ldots & 16 & 1 & \ldots & 16 & 1 & \ldots & 8
\end{pmatrix}$

Как можно было рассуждать более формально?

PS: Спасибо, что заинтересовались.

 
 
 
 Re: Формализовать наивное решение комбинаторной задачи
Сообщение16.02.2015, 09:54 
Выстройте учеников в цепочку,
musius в сообщении #979000 писал(а):
$\begin{pmatrix}1 & \ldots & 16 & 17 & \ldots & 32 & 33 & \ldots & 40\\ \downarrow & \ldots & \downarrow & \downarrow & \ldots & \downarrow & \downarrow & \ldots & \downarrow\\ 1 & \ldots & 16 & 1 & \ldots & 16 & 1 & \ldots & 8\end{pmatrix}$

Лучше так:

Код:
1  2  3  4  5  1  2 ...  5  1  2  3 ...  1  2  3  4 ... 4  5
1  2  3  4  5  6  7 ... 15 16  1  2 ... 15 16  1  2 ... 7  8

 
 
 
 Re: Формализовать наивное решение комбинаторной задачи
Сообщение16.02.2015, 11:26 
Аватара пользователя
Можно рассуждать от противного. Предположите, что лучший ученик решил меньше 3 задач. Тогда сколько решил он? Сколько остальные?

Но для завершения решения надо обязательно привести пример.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group