Расположи 9 элементов в трёх множествах ...

[SpiderHulk]

Я начал строить дерево вариантов с нахождения трёх принципиально разных ситуаций:
1) в зоне пересечения трёх множеств 0 элементов, в зонах пересечения двух множеств 5 элементов, в зонах без пересечений 4 элемента
2) в зоне пересечения трёх множеств 1 элемент, в зонах пересечения двух множеств 3 элемента, в зонах без пересечений 5 элементов
3) в зоне пересечения трёх множеств 2 элемента, в зонах пересечения двух множеств 1 элемент, в зонах без пересечений 6 элементов

Однако с дальнейшим построением дерева вариантов испытываю затруднения

(Оффтоп)

А ещё я слегка озадачен сложностью данной задачи из учебника третьего класса

[Geen]

У нас есть два замечательных множества - 2 и 7 - одно из них достаточно мало, а в сумме дают 9...
И вроде бы всё в уме легко считается (хотя для 3-го класса...)...

[SpiderHulk]

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

[arseniiv]

Кажется, это дело для производящих функций! (Героическая музыка, под которую в кадр влетают производящие функции во всей красе.)

$$F_N = (x + y + z + xy + yz + zx + xyz)^N = \sum\limits_{\ell,m,n} a(\ell,m,n) x^\ell y^m z^n,$$

где $a(\ell,m,n)$ — количество способов разложить $N$ различимых* элементов по множествам $A,B,C$ так, чтобы в $A$ было $\ell$, в $B$ было $m$, в $C$ — $n$. Чтобы получить искомое число, надо найти $a(2,5,7)$ для $F_9$, но при этом у нас посчитаются лишние способы, когда в одном из множеств слишком много. Их можно выкинуть, вычтя $\binom N3x^3F_{N-3} + \binom N6y^6F_{N-6} + \binom N8z^8F_{N-8}$, но тут мы вычли чересчур, так что надо ещё прибавить $\binom N{3;6}x^3y^6F_{N-3-6} + \binom N{6;8}y^6z^8F_{N-6-8} + \binom N{8;3}z^8x^3F_{N-9-3}$, а теперь прибавили многовато, и надо вычесть $\binom N{3;6;8}x^3y^6z^8F_{N-3-6-8}$. К счастью, на самом деле $F_{N<0} = 0$, и $N = 9$, так что на деле имеем $F_{:)} = F_9 - \binom93x^3F_6 - \binom96y^6F_3 - \binom98z^8F_1 + \binom9{3;6}x^3y^6F_0$, где и надо найти нужный коэффициент. Далее может помочь то, что $F_1 = (1+x)(1+y)(1+z) - 1 \equiv G - 1$, так что $F_N = \sum_i \binom ni G^i (-1)^{n-i}$. Вполне посильно ученикам 3 класса, если только не вспомнить, что

* у нас неразличимые элементы, упс.

SpiderHulk в сообщении #1231781 писал(а):

а в нахождении всех возможных решений

Можно понять и так, что надо найти хотя бы одно решение и их общее число.

[SpiderHulk]

Я насчитал 36 вариантов, но нет полной уверенности что это все возможные

UPD >36

[Geen]

Полагаю, что элементы и множества неразличимы...
И всего 10 решений.

[SpiderHulk]

Geen в сообщении #1231842 писал(а):

Полагаю, что элементы и множества неразличимы...

А если считать множества различимыми? 60?

[Geen]

SpiderHulk в сообщении #1231856 писал(а):

Geen в сообщении #1231842 писал(а):

Полагаю, что элементы и множества неразличимы...

А если считать множества различимыми? 60?

Да, но вряд ли это требуется в задаче если она для "младших классов" (не думаю, что в третьем классе смог бы решить - я и слово "множество" тогда вряд ли знал)

[SpiderHulk]

А как всё вами было вычислено вычислено число решений? Из каких соображений?

[SpiderHulk]

решено

(Оффтоп)

мне трудно поверить в то, что множество третьеклассников, способных самостоятельно такую задачу решить, не пустое

[TOTAL]

SpiderHulk в сообщении #1231771 писал(а):

1) в зоне пересечения трёх множеств ....

А почему вообще должны волновать зоны пересечения?

Каким-то двум элементам дадим по красной конфетке.
Каким-то пяти элементам дадим по желтой конфетке.
Каким-то семи элементам дадим по зеленой конфетке.

Сколькими способами можно надавать?

[iifat]

Не забывая следить, чтоб каждому таки чего-то досталось.

[Geen]

И что дети без конфет неразличимы

[SpiderHulk]

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

А почему вообще должны волновать зоны пересечения?

Каким-то двум элементам дадим по красной конфетке.
Каким-то пяти элементам дадим по желтой конфетке.
Каким-то семи элементам дадим по зеленой конфетке.

Сколькими способами можно надавать?

Задача мною уже решена, но из иных соображений

(Оффтоп)

Каждое множество содержит 4 зоны. Пусть в А 2 элемента, в В 5 элементов, а в С 7 элементов. Тогда 2 элемента множества А можно расставить по 4 зонам 10 разными способами. (В четырёх из них в одной из зон два элемента, а в остальных нет элементов. В остальных шести в двух из четырёх зон содержится по одному элементу) Каждому из этих 10 способов соответствует лишь один способ расстановки элементов по зонам остальных множеств удовлетворяющий условию задачи. Но далее надо учесть что 2; 5 и 7 элементов можно присвоить множествам A, B, C шестью разными способами. В таком случае получится 60 возможных вариантов

Ваша же подсказка меня к иному способу решения не подтолкнула. Попробую:

Так?

1) Двум из девяти элементов по красной конфетке можно дать $9\cdot8=72$ способами
2) Пяти из девяти элементам можно дать по жёлтой конфетке $9\cdot8\cdot7\cdot6\cdot5=15120$ способами
3) Семи из девяти элементам можно дать по зелёной конфетке $9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3=181440$ способами

Или так?

1) $\frac{9\cdot8}{2\cdot1}=36$

2) $\frac{9\cdot8\cdot7\cdot6\cdot5}{5\cdot4\cdot3\cdot2\cdot1}=126$

3) $\frac{9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}=36$

[gris]

Сейчас младшеклассники умеют такие задачи решать. Хотя бы расставляя циферки в семи зонах на картинке. Эти диаграммы им знакомы. Конечно, строго найти число всех вариантов им не под силу, но это и не требуется. Задачка хороша тем, что находить варианты довольно просто и их много, так что подогревается интерес и вносится элемент соревновательности. Дополнительно можно порассуждать о том, какие варианты считать одинаковыми.