Enigme tres difficile

[mquidech]

SALAM



Demain Marie soufflera, pour son anniversaire, autant de bougies qu'elle recevra de baisers. L'ensemble de ses 12 invités pourra l'embrasser de 78 façons différentes et personne ne saurait oublier de l'embrasser.
Quel âge a Marie?

[CarpDiem]

ça dépend d'ou ils viennent par exemple à Montpellier ils font 3, Lyon 4 bises, Marseille 2 ... Paris ils serrent la main

[Scootie]

Bah, elle doit avoir entre 12 et 934 ans ........... zaama au cas où tous les invités seraient arabes et la bisoutent donc de toutes les façons

[absent]

Elle a 12 ans.

[mquidech]

SALAM


14 ans



Soit xi le nombre de baisers donnés par l'invité i (xi >= 1 et 1 =< i =< 12).

Soit a l'âge de Marie.

Nous avons donc x1 + ... + x12 = a (et donc a >= 12).

Posons yi = xi - 1 et b = a - 12 (yi >= 0 et b >= 0).

L'équation précédente est équivalente à y1 + ... + y12 = b.



Le nombre de "façons différentes" laisse planer un doute : tient-on compte de l'ordre ou non ?



* l'ordre compte



Le nombre de compositions de b en au plus 12 sommants (un sommant est strictement positif) vaut donc C(b+12-1; 12-1) = C(a-1; 11) = 78 où C(n; k) est le nombre de combinaisons de k objets pris parmi n.

Un manière visuelle de le voir est de procéder comme l'exemple suivant (une composition de 9 en 5 sommants) : 2+3+2+0+2 s'écrit ..|...|..||..

Ainsi cela revient à placer 11 | dans un ensemble de b+11.



D'où l'équation (a-1)*(a-2)*...*(a-11)/11! = 78.

Le membre de gauche est une fonction strictement croissante. L'existence de a garantit son unicité.

L'essai des premières valeurs montre que a = 14 est solution.



* l'ordre ne compte pas



Notons P(n; m) le nombre de partitions de n en exactement m sommants et p(n; m) le nombre de partitions de n en au plus m sommants.

Quelques propriétés triviales...

P(n; m) = 0 si m > n

p(n; m) = p(n; n) si m >= n

p(n; m) = P(n; 1) + ... + P(n; m)

P(n; n) = P(n; 1) = 1



Une propriété moins triviale...

P(n; m) = p(n-m; m)

Pour l'obtenir il suffit de procéder comme nous avons fait plus haut pour passer de x1 + ... + x12 = a à y1 + ... + y12 = b et réciproquement.



D'où P(n; m) = P(n-m; 1) + ... + P(n-m; m)

Cette relation de récurrence permet de calculer les P(n; m) de proche en proche et de s'assurer que P(n; m) est une fonction croissante de n pour m fixé.

En particulier, nous avons P(24; 12) = 77 et P(25; 12) = 100.

Et donc il n'existe pas de a tel que P(a; 12) = 78.
__________________