Как решаются такие задачи?

[From_Odessa]

Вот задача из программы 9-го класса:

На товарищеском турнире школьников по шахматам каждый школьник сыграл с каждым другим не более одной партии, кроме того, каждый их них сыграл с приглашённым гроссмейстером не более одной партии. Всего было сыграно 18 партий. Какое наименьшее количество учеников могло участвовать в этом турнире?

Попросили помочь решить.

Найти ответ-то я могу. Но проделал я это простым подбором. Так как в случае, когда соперники играют друг с другом, порядок в паре не имеет значения (1 против 2 и 2 против 1 - это одна и та же партия), то мы имеем дело с сочетанием. Взял для пробы пять участников. Имеем: 5!/2!(5-2)! = 10. Соответственно, играя каждый против каждого не более одной партии, ученики смогут провести максимум 10 партий, и даже, если каждый сыграет по одной партии с гроссмейстером, максимальное количество партий составит 15. Следовательно, участников не могло быть пять и менее. Далее пробуем шесть: 6!/2!(6-2)! = 15. А вот этого уже достаточно. Если они все друг с другом сыграют, то достаточно будет, чтобы только трое из них сыграли с гроссмейстером, и уже наберется 18 партий. Или же они могут сыграть не все друг с другом, но все равно набрать 12 партий, а потом каждый сыграет с гроссмейстером - будет 18 и т.д. Следовательно, минимальное количество участников - шесть.

Но я не думаю, что подразумевается такое решение. И я даже не знаю/не помню, знакомились ли к 9-му классу/в 9-м классе с комбинаторикой. Наверняка есть какой-то общий алгоритм решения таких задач. Но я его не знаю или не помню. Не помню, чтобы у нас такие задачи были в школе. И впоследствии именно с такими особо не сталкивался.

[Andrey Lukyanov]

Гроссмейстера отдельно выделять нет смысла, можно считать его как ещё одного школьника.

Если всего n человек, то первый может сыграть максимум n−1 партий, второй дополнительно n−2 партий (поскольку партия с первым уже учтена), третий ещё n−3 и т. д.

То есть получается сумма арифметической прогрессии от 1 до n−1, которая равна n(n−1)/2.

Для 6 участников получается 15, для 7 — 21.

То есть было 7 участников, из которых 1 гроссмейстер и 6 школьников.

[From_Odessa]

Andrey Lukyanov, можно ли считать, что Ваше решение - это какой-то общий алгоритм для таких задач? Или оно такое же, как мое? Может быть, у меня чуть более громоздкое из-за того, что я выделял гроссмейстера. Но Вы в итоге получили прогрессию и подбирали числа по ней. Я использовал сочетания и тоже подбирал числа. В итоге мы оба получили одинаковой ответ (ответ шесть, потому что вопрос там стоит о том, какое минимальное количество учеников могло принимать участие, а не какое минимальное количество участников вообще. Минимальное вообще - семь, но это вместе с гроссмейстером, а учеников - шесть). Или Ваш вариант решения более удобный, потому что с ним будет легче работать, если будут достаточно большие величины, тогда как мой в этом смысле хуже, поскольку придется иметь дело с большими величинами в подсчетах сочетаний? Хотя вряд ли, ведь там все равно большая часть факториалов сократится.

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

Но раз такая задача дается в девятом классе, то, наверное, для нее есть какой-то общий алгоритм, который объясняют в школе? Или же, может, нет алгоритма, а это просто частный случай, чтобы школьник сам сообразил? Так-то данную задачу можно решить даже без комбинаторики или прогрессии, потому что величины небольшие. Просто начать считать число возможных пар. Но что-то я сомневаюсь, что от учеников ждут этого.

[Upliner]

Гроссмейстера отдельно выделять нет смысла, можно считать его как ещё одного школьника.

Неправильно, т.к. партии между учениками и гроссмейстером учитываются отдельно. Если имеем n учеников, то максимальное количество сыгранных партий будет n(n−1)/2+n.

[From_Odessa]

Если имеем n учеников, то максимальное количество сыгранных партий будет n(n−1)/2+n.

Ну да, это как раз из сочетания можно вывести: n!/2!(n-2)! + n = n(n-1)/2 + n.

[Andrey Lukyanov]

Неправильно, т.к. партии между учениками и гроссмейстером учитываются отдельно. Если имеем n учеников, то максимальное количество сыгранных партий будет n(n−1)/2+n.

У вас n — число учеников, а у меня n — число учеников вместе с гроссмейстером. С учётом этого формулы совпадают.

[From_Odessa]

Но мой вопрос остается открытым. Я использовал просто сочетания для решения, Андрей - прогрессию, Аплайнер подошел чуть иначе, при этом не знаю, выводил он формулу из сочетаний или нет. Вот только все это - наши изобретения решений, причем, возможно, с использованием и того, чего по программе до этой задачи в девятом классе еще не было. А какого решения ждут от ученика и есть ли какой-то представленный в школе алгоритм для решения таких задач, совпадает ли он с одним из использованных в этой теме вариантов, - непонятно.

[From_Odessa]

В Интернете нашел вот такое решение (только там в условии 20 партий), вообще через неравенство:

[From_Odessa]

И здесь тоже перебор, подбор.

[Ömer]

Факт 1. Количество суммарных партий выражается  формулой сочетаний.

Школьник может дойти до этой формулы разными способами. Он может её знать (как знал Одесса), вывести через сумму прогрессии (как Андрей)... Можно также рассуждать вот как: каждый играет с остальными, поэтому получается n*(n-1), но в этой формуле партия A с B и B с A учтётся два раза, поэтому делим на два.

Факт 2. Минимальное число выражается через неравенство.

Его проще всего решить подбором, но можно заморочиться и через дискриминант.

[kemerover]

Да в целом это всё один и тот же подход, в сущности всё сводится к частичной сумме натурального ряда.

Если бы было указано точное количество партий, то можно было бы решить как квадратное уравнение, а так есть смысл только подбором решать.

[kemerover]

В Интернете нашел вот такое решение (только там в условии 20 партий), вообще через неравенство:

Вы тоже через неравенство решали, просто вы не заморочились это формально выразить.

[From_Odessa]

Вы тоже через неравенство решали, просто вы не заморочились это формально выразить.

Ну, в принципе, да, Вы правы. Фактически я решил неравенство n!/2!(n-2)! + n >= 18.

[From_Odessa]

Ну, в принципе, да, Вы правы. Фактически я решил неравенство n!/2!(n-2)! + n >= 18.

Но если бы я именно решал его, как неравенство, то сначала прошел бы такой путь:

n!/2!(n-2)! + n >= 18
n(n-1)/2 + n >= 18
n^2 + n >= 36
n(n+1) >= 36

а потом перебором нашел бы ответ n>=6. Я же все-таки не решал неравенство даже в голове именно обычным способом его решения, я, по сути, проделывал другую операцию, которая тождественна, но не аналогична решению неравенства в обычном смысле.

[From_Odessa]

Сабжевый вопрос уже вот по такой задаче:

На празднование Дня именинника в параллели 5 классов было заказано несколько пицц. На всех мальчиков было заказано 10 пицц, при этом всем мальчикам досталось поровну. Каждой девочке тоже досталось поровну, но в два раза меньше, чем мальчику. Сколько пицц было заказано, если известно, что девочек в этой параллели 11, а мальчиков больше, чем девочек? Пиццы можно делить на части.

[Эслыш]

1. n -- колво мальчиков, n>11.
2. 10\n пиццы досталаcь каждому мальчику, 5\n пиццы каждой девочке.
3. N(колво пицц)=11·5\n+10. Первое слагаемое натуральное только при n=55. Итого 11 пицц.

[From_Odessa]

Эслыш, спасибо!