запутанная задачка по комбинаторике

[Claer]

На математической олимпиаде командам были предложены 9 задач. В итоге получилось, что каждая команда решила ровно 3 задачи, каждые две команды решили разные наборы задач и для любых трех команд можно найти задачу, которую не решила ни одна из них. Какое наибольшее количество команд могло участвовать в этой олимпиаде?

Я предположила, что одну из задач не решил никто, отбросила третье условие и выяснила сколькими разными способами можно выбрать 3 задачи из 8. 8!/(3!(8-3)!) = 56, т. о. 56 команд. Но мне кажется, что я чего то не допонимаю, помогите, пожалуйста, разобраться.

[svv]

1) сколько может быть команд максимум, если есть только первые два условия? (это совсем простой вопрос)
2) сколькими способами из этого максимального набора команд можно выбрать три команды, нарушающие третье условие? (это посложнее)
Ответьте, тогда продолжим.

[Claer]

1) сколько может быть команд максимум, если есть только первые два условия?
Ответ: 9!/3!(9-3)!=84 команды (вот только сомневаюсь, может это только, если есть только одно первое условие)

[svv]

Да, 84. Вот они:

123,124,125,126,127,128,129,134,135,136,137,138,
139,145,146,147,148,149,156,157,158,159,167,168,
169,178,179,189,234,235,236,237,238,239,245,246,
247,248,249,256,257,258,259,267,268,269,278,279,
289,345,346,347,348,349,356,357,358,359,367,368,
369,378,379,389,456,457,458,459,467,468,469,478,
479,489,567,568,569,578,579,589,678,679,689,789

Здесь каждая команда обозначена тройкой номеров задач, которые она решила. Например, числом 259 обозначена команда, решившая задачи 2,5,9.
По второму условию каждому выписанному числу соответствует только одна команда.
(Если бы было только первое условие, каждой тройке задач могло бы соответствовать сколько угодно команд.)

А теперь включаем третье условие: "Никакие три команды не охватывают всех задач."
Сразу видно, что для выписанного полного списка это условие нарушается, например, команды 135, 469 и 278 вместе решили все задачи.
Мой второй вопрос: сколькими способами из указанного списка можно выбрать три команды, нарушающие третье условие, т.е. решившие "втроем" все девять задач?

[Claer]

svv в сообщении #490815 писал(а):

для выписанного полного списка это условие нарушается, например, команды 135, 469 и 278 вместе решили все задачи.

Команды 123, 456, 789 также нарушают третье условие. Т. о. можно найти 84/3 = 28 троек команд, нарушающих третье условие. Это количество надо исключить из максимально возможного количества команд?
84 - 28 = 56.

[svv]

Идея правильная, но дело немного сложнее.

Сначала всё-таки подсчитаем, сколько таких "нарушающих" троек. Иначе говоря, это количество способов, которыми числа 1,2,3,4,5,6,7,8,9 (номера задач) можно разбить на три группы по три элемента.

Каждый такой способ можно получить следующим образом. Запишем какую-то перестановку чисел от 1 до 9, например, 135469278 (всего этих перестановок, как известно, 9!=362880). Разделим её на три группы по три цифры, как номер телефона: 135-469-278. И договариваемся понимать это так: одна команда решила задачи 1,3,5; другая решила задачи 4,6,9; третья решила задачи 2,7,8.

Может показаться: ну, значит, таких способов 362880. Но обратите внимание, что первые три цифры можно переставлять (например, 351-469-278), но от этого нового разбиения не получится. И вообще, цифры в пределах любой группы можно переставлять (например, 351-496-872), но от этого нового разбиения не получится. И, кроме того, сами группы можно переставлять (например, 278-469-135), но это тоже не дает нового разбиения. Это я намекаю на способ вычисления.

Так что, всё-таки, поменьше, чем 362880. Но и не 28. Вычислите?

[Claer]

Количество перестановок в одной тройке чисел (группе) 3!=6, учитывая количество групп 3х3!=18.
Количество перестановок самих групп 3!=6. Итого 18+6 = 24?

[VAL]

Claer в сообщении #490886 писал(а):

Количество перестановок в одной тройке чисел (группе) 3!=6, учитывая количество групп 3х3!=18.
Количество перестановок самих групп 3!=6. Итого 18+6 = 24?

Жуть!

[svv]

М-да...
Надо было умножать. Аналогия: если в городе номера телефонов шестизначные, то первые три цифры номера принимают $1000=10^3$ значений, последние три цифры -- столько же, а все шесть цифр -- уже $1000000$, но никак не $2000$.

ОК, $6 \cdot 6 \cdot 6 \cdot 6=6^4=1296$, но это мы только подсчитали количество перестановок (получаемых перестановками внутри групп и самих групп), которые следует считать за один вариант. Изначально всех перестановок $9!=362880$. Дальше?

[Claer]

Боюсь шокировать образованных людей И все же рискну поделиться.
1) Городские телефоны не начинаются с нуля. Не следовало бы в произведении из шести десяток, один множитель заменить на 9?
2)Если всех перестановок 362880, а за один способ считаем 1296 перестановок, то количество способов 362880/1296 = 280 вариантов. Все равно тупик какой то
А может все же одну задачу не решила ни одна команда?

[TOTAL]

Claer в сообщении #491545 писал(а):

280 вариантов. Все равно тупик какой то

Если выгнать команду, решившую определенную тройку задач, то какое максимальное число из этих 280 нежелательных вариантов можно устранить?

[svv]

280 -- да, правильно.
Claer, Вы на финишной прямой. Присоединяюсь к вопросу TOTALа.

[Claer]

TOTAL в сообщении #491555 писал(а):

Если выгнать команду, решившую определенную тройку задач, то какое максимальное число из этих 280 нежелательных вариантов можно устранить?

Извините, нельзя ли этот вопрос разбить на подвопросы? Что-то не получается ничего

[TOTAL]

Claer в сообщении #492021 писал(а):

TOTAL в сообщении #491555 писал(а):

Если выгнать команду, решившую определенную тройку задач, то какое максимальное число из этих 280 нежелательных вариантов можно устранить?

Извините, нельзя ли этот вопрос разбить на подвопросы? Что-то не получается ничего

Что такое нежелательный вариант, которых Вы насчитали 280 штук, объясните здесь.

[Claer]

TOTAL в сообщении #492031 писал(а):

Что такое нежелательный вариант, которых Вы насчитали 280 штук, объясните здесь.

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