Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 22-06-2025 21:02:34

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3834

Partitions d'un etnier

Bonjour @ tous.

Les partitions de 5 par exemple sont :

1+1+1+1+1
1+1+1+2
1+2+2
1+1+3
2+3
1+4
5

Si l'on compte les 1 de toutes les partitions, on en trouve 12
Si l'on compte les chiffres distincts à chaque partition et que l'on cumule on en trouve 12 également. (1 chiffre pour la 1ère, 2 pour la 2ème, 2 pour la 3ème, 2 pour la 4ème, 2 pour la 5ème, 2 pour la 6ème et 1 pour la 7ème).

Est ce un coup de chance pour 5, ou pour d'autres, ou est ce général pour tout entier ?

  • |
  • Répondre

#0 Pub

 #2 - 24-06-2025 19:25:00

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,096E+3

Partitionns d'un entier

C'est la suite https://oeis.org/A000070 et même si je n'y trouve pas de démonstration, une récurrence devrait permettre de s'en sortir.

Genre :
on rajoute +1 dans chaque partition.
donc on rajoute autant de 1 que le nombre de partitions précédent + le nombre décomposé en unaire.

Pour les chiffres différents, c'est un peu plus compliqué...
Il faut raisonner sur les sets de nombres. Je ne trouve pas d'explication simple, et les explications compliquées laissent toujours un cas particulier.

 #3 - 25-06-2025 07:02:06

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3834

Partitios d'un entier

@ Gwen : je laisse encore un peu de temps, jusqu'à la fin du mois car la question vient de Diophante.

Le problème est de bien classer les cas, et c'est très clair ensuite !

 #4 - 26-06-2025 15:10:26

Spirou
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 500

Partiions d'un entier

Merci pour ce problème très intéressant, les partitions d'entiers ont des propriétés bien mystérieuses! big_smile

Notons:
[latex]u_k[/latex] le nombre de '1' dans les partitions de k (u pour 'un'),
[latex]p_k[/latex] le nombre de partitions de k,
[latex]d_k[/latex] le nombre de chiffres distincts comptés dans les partitions de k (d pour 'distinct').

Comme l'a souligné @gwen27, [latex]u_{k+1} = u_k + p_k[/latex]. En effet, on ajoute un 1 à chaque partition de [latex]k[/latex], ce qui nous donne les partitions de [latex]k+1[/latex] ayant un 1. Le nombre total de 1 est donc celui de [latex]k[/latex], ajouté au nombre de partitions.

Il suffit donc de montrer que [latex]d_{k+1} = p_0 + p_1 + p_2 + \cdots + p_k[/latex].

Pour cela, nous associons à chaque chiffre [latex]l[/latex] apparaissant dans une partition de [latex]k+1[/latex] la partition de [latex]k-l[/latex] obtenue en retirant [latex]l[/latex] de la partition. Par exemple, la partition 6=1+2+3 contient trois chiffres distincts. A chaque chiffre, on associe respectivement les partitions de 5, 4, et 3 suivantes:

5 = 2+3
4 = 1+3
3 = 1+2

En conclusion, pour chaque chiffre distinct d'une partition de [latex]k+1[/latex], on associe une partition d'un entier plus petit, et on a donc l'égalité souhaitée.

------------------

Plus formellement, si on note [latex]P_k[/latex] l'ensemble des partitions de [latex]k[/latex], et [latex]P'_k[/latex] les partitions pointées de [latex]k[/latex] i.e
[latex]P'_k = \{ (i, a_1, a_2, \cdots, a_k) \Big| \sum_{j = 1}^k ja_j = k, a_i \neq 0\}[/latex],
alors nous construisons la bijection suivante:
[latex]\begin{array}{ccc}
P'_{k+1} & \longrightarrow & \cup_{l \leqslant k} P_l \\
(i, a_1, \dots, a_{k+1}) & \mapsto & (a_1, \dots, a_i-1, \dots, a_{k+1})
\end{array}[/latex].

 #5 - 26-06-2025 18:16:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3834

Patritions d'un entier

@ Spirou: je n'ai pas fait comme toi, et en te lisant je bute à partir de :

....Il suffit donc de montrer que dk+1=p0+p1+p2+⋯+pk.

Peux tu détailler ?

 #6 - 26-06-2025 18:39:25

Spirou
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 500

Partitionss d'un entier

On a montré que [latex]u_{k+1} = u_k + p_k[/latex], et on sait que [latex]u_1 = 1 = p_0[/latex]. (Par convention 0 a une unique partition: la partition vide).

Donc on a immédiatement [latex]u_{k+1} = p_k + p_{k-1} + \cdots + p_1 + p_0[/latex].

Le but est donc de montrer qu'on a la même chose pour [latex]d_{k+1}[/latex].

 #7 - 27-06-2025 08:17:15

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3834

Partitions d''un entier

J'ai compris ! C'est joli.

Comme je le disais, j'ai fait différemment, par récurrence, passer de k à (k+1).

Si l'on ajoute un 1 aux partitions de k qui n'ont pas de 1, alors il y a égalité entre le nombre de 1 ajoutés et le nombre de chiffres ajoutés, puisque pour chacune de ces partitions, c'est + 1 pour le nombre de 1, mais aussi +1 pour le nombre de chiffres distincts, puisqu'on ajoute le chiffre 1 aux partitions qui n'en ont pas.

En revanche, pour les partitions de k qui ont déjà un ou plusieurs 1, là il y augmentation du nombre de 1 sans augmentation du nombre de chiffres distincts. Comment gérer cela ?

On forme les partitions de (k+1) sans aucun 1. Et à chacune de ces partitions, on peut former une ou plusieurs partitions avec des 1 en changeant uniquement un seul chiffre  et en le remplaçant par des "1". Si la partition comporte 3 chiffres distincts par exemple, il y aura 3 nombres comportant au moins 2 "1". Et tous ces nombres formés avec au moins 2 "1", à partir de cette transformation, sont tous les nombres qu'on trouve dans les partitions de (k+1) comportant au moins 2 "1".

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete