Processing math: 78%
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 enntier

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,093E+3

partitions d'un entoer

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

artitions 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

Partitions d'unn 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:
uk le nombre de '1' dans les partitions de k (u pour 'un'),
pk le nombre de partitions de k,
dk le nombre de chiffres distincts comptés dans les partitions de k (d pour 'distinct').

Comme l'a souligné @gwen27, uk+1=uk+pk. En effet, on ajoute un 1 à chaque partition de k, ce qui nous donne les partitions de k+1 ayant un 1. Le nombre total de 1 est donc celui de k, ajouté au nombre de partitions.

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

Pour cela, nous associons à chaque chiffre l apparaissant dans une partition de k+1 la partition de kl obtenue en retirant l 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 k+1, on associe une partition d'un entier plus petit, et on a donc l'égalité souhaitée.

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

Plus formellement, si on note Pk l'ensemble des partitions de k, et Pk les partitions pointées de k i.e
Pk={(i,a1,a2,,ak)|kj=1jaj=k,ai0},
alors nous construisons la bijection suivante:
Pk+1l.

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

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

partitiobs 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

partitions d'yn entier

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

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

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

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

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

Partitions d'un enter

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 (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

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