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-02-2011 15:02:03

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Applique à Con(way), la suit

Je reprends l'idée de Vasimolo: soit f l'application de N dans N qui à X fait correspondre Y tel que Y est le comptage "Conway-trié" des chiffres de X.
Par exemple f(453154) = 11132425 (un 1, un 3, deux 4 et deux 5)

On a déjà trouvé le plus grand des points fixes de f
La question est la suivante: combien y en a-t'il ?


 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 22-02-2011 15:57:56

Memento
Professionnel de Prise2Tete
Enigmes résolues : 30
Messages : 176

Applique à Con(way), l suite

Il y en as 109 smile

Code:

22
10213223
10311233
10313314
10313315
10313316
10313317
10313318
10313319
21322314
21322315
21322316
21322317
21322318
21322319
31123314
31123315
31123316
31123317
31123318
31123319
31331415
31331416
31331417
31331418
31331419
31331516
31331517
31331518
31331519
31331617
31331618
31331619
31331718
31331719
31331819
1031223314
1031223315
1031223316
1031223317
1031223318
1031223319
3122331415
3122331416
3122331417
3122331418
3122331419
3122331516
3122331517
3122331518
3122331519
3122331617
3122331618
3122331618
3122331718
3122331719
3122331819
10413223241516
10413223241517
10413223241518
10413223241519
10413223241617
10413223241618
10413223241619
10413223241718
10413223241719
10413223241819
41322324151617
41322324151618
41322324151619
41322324151718
41322324151719
41322324151819
41322324161718
41322324161719
41322324161819
41322324171819
1051322314251617
1051322314251618
1051322314251619
1051322314251718
1051322314251719
1051322314251819
1051322325161718
1051322325161719
1051322325161819
1051322325171819
5132231425161718
5132231425161719
5132231425161818
5132231425171819
5132232516171819
106132231415261718
106132231415261719
106132231415261819
106132231426171819
106132231526171819
613223141526171819
1011112131415161718
1011112131415161719
1011112131415161819
1011112131415171819
1011112131416171819
1011112131516171819
1011112141516171819 
1011113141516171819
1111213141516171819
10713223141516271819
101112213141516171819

 #3 - 22-02-2011 16:37:27

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Applique à Con(way), la siute

Je crois que la page de l'OEIS donnant la suite des points fixes de cette fonction a été donnée par quelqu'un dans le topic du Vasimolo...


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #4 - 22-02-2011 17:01:48

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Appique à Con(way), la suite

@Memento : Ok, mais la démo ?

@Mathias: non, j'ai bien regardé et j'ai rien vu de tel (sur le post de Vasimolo, par contre oui c'est vrai ça existe bien). Mais bon, j'attends un résultat et aussi la démo qui va avec smile

 #5 - 23-02-2011 16:56:21

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

Applique à Con(wya), la suite

J'y vais par construction en regardant le nombre d'apparition du chiffre 1 dans le point fixe :

0 => 1 point fixe : 22

1 => impossible pour un point fixe

2 => 2 apparait donc forcément une deuxième fois quand on dit le nombre de 2. Son coefficient ne peut pas être deux car il y aurait alors au moins trois 2.
si le coeff de 2 est 3 : ...213223... Il faut que je rajoute a ce motif 1n où n est un des chiffres restants pour avoir mon deuxième 1 : 7 possibilités. Si le coeff de 2 est plus grand je n'arrive pas a trouver d'autres points fixes.
7 points fixes

3 => 3 apparait forcément une 2eme fois. Je trouve 2 motifs possibles :
  - ...1333... auquel je greffe  1a et 1b avec a et b 2 des 8 chiffres restants : C2_8 points fixes.
  - ...132233... auquel je greffe 1a et 1b avec a et b 2 des 7 chiffres restants : C2_7 points fixes.
C2_8+C2_7 = 49 points fixes

k= 4,5,6,7 => je trouve le motif ...k12332...2k... auquel je greffe k-1 fois 1a parmi les 6 chiffres restants.
C3_6+C4_6+C5_6+C6_6 = 42 points fixes

8,9,10 => je ne trouve rien

11 => j'obtiens 2 motifs :
   -  ...111... + 8 1a parmi les 9 chiffres restants : C8_9
   -  101112213141516171819
C8_9+1 = 10 points fixes

12+=> je ne trouve rien

136 109 en tout mais pas la bonne réponse T_T faut que je trouve ceux qui me manquent.

 #6 - 24-02-2011 01:15:51

L00ping007
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2010
Lieu: Paris

Applique à Con(way,) la suite

Voila ce que je trouve après un fastidieux dénombrement. k est le nombre de chiffres des points fixes :

k=2
22 : 1 solution

k=4
0 solution

k=6
0 solution

k=8
31331x1y x,y dans {0,2,4,5,6,7,8,9} : 28 solutions
2132231x x dans {0,4,5,6,7,8,9} : 7 solutions

k=10
3122331x1y x,y dans {0,4,5,6,7,8,9} : 21 solutions

k=12
0 solution

k=14
413223241x1y1z x,y,z dans {0,5,6,7,8,9} : 20 solutions

k=16
513223251x1y1z1t x,y,z,t dans {0,4,6,7,8,9} : 6 solutions 15 solutions, c'est mieux scarta !

k=18
613223261x1y1z1t1u x,y,z,t,u dans {0,4,5,7,8,9} : 6 solutions

k=19
1111x1y1z1t1u1v1w1s : 9 solutions

k=20
10713223141516271819 : 1 solution

k=21
101112213141516171819 : 1 solution

Ce qui me fait en tout 100 solutions.
Comme ca ne valide pas, j'ai du en oublier !

Ce qui me fait 109 solutions, validé !

 #7 - 24-02-2011 09:26:22

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

applique à con(way), la syite

@Nicouj: tu en as trop. En même temps, tu le crois vraiment quand tu dit 8 parmi 9 = 36 ???
@L00poing: toi c'est pas assez, mais c'est la même erreur (4 parmi 6 = 6 ???)

 #8 - 24-02-2011 10:33:23

Nicouj
Professionnel de Prise2Tete
Enigmes résolues : 27
Messages : 330

apploque à con(way), la suite

*tousse* la case marche mieux du coup big_smile

 #9 - 24-02-2011 14:03:46

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

apploque à con(way), la suite

Réponse cachée 109h, en attendant tu peux poster ta solution.

y a pas de hasard, je dirais 109 points fixes.

 #10 - 24-02-2011 15:24:11

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Applique à Con(wway), la suite

@Gasole: bien vu, c'est fait exprès smile
Ceci dit une démo et éventuellement la liste complète ne serait pas de refus.

 #11 - 24-02-2011 15:35:10

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Applique à Con(way), l suite

J'avoue avoir trouvé la réponse toute faite, je n'ai pas de démo, mais j'ai la liste, ici. S'y trouvent aussi plein de variantes.

 #12 - 27-02-2011 10:45:33

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Applique à Con(wway), la suite

Bon alors, la réponse était bien 109. La démo maintenant.
Soit X un point fixe de f de N chiffres comprenant D chiffres différents.
Notre nombre s'écrit alors [latex]a_0b_0a_1b_1...a_{D-1}b_{D-1}[/latex], où les bi sont les D chiffres différents dans l'ordre et les ai le nombre de fois où chacun d'eux apparaît. Première remarque : N >= 2D (vu qu'ilfaut au minimum un chiffre pour chaque bi et un autre pour chaque ai)

On a [latex]\sum_{i=0}^{D-1}{a_i}=N[/latex] car la somme des nombres de fois où chaque chiffre apparaît doit donner le nombre de chiffre total.
On a aussi [latex]\sum_{i=0}^{D-1}{g(a_i)} = N-D[/latex],où g est la fonction qui renvoie le nombre de chiffres d'un nombre. En effet, parmi nos N chiffres, D sont utilisés pour écrire les bi, tous les autres servent donc aux ai.
Parmi ces N-D chiffres, D sont des chiffres des unités et donc N-2D sont au minimum des chiffres de dizaines. De plus, au moins D-(N-2D) = 3D-N sont des chiffres d'unités qui ne sont pas suivi de dizaines et sont donc non nuls
Du coup, [latex]\sum_{i=0}^{D-1}{a_i} = N \geq 10N-20D + 3D-N\\
8N \leq 17D\\
N \leq 2D + \frac{D}{8}[/latex]

Donc [latex] 2D \leq N \leq 2D + \frac{D}{8}[/latex]

On va maintenant regarder ce qu'il se passe pour chaque valeur de D.
Petite remarque cependant: quand N = 2D, supposons que parmi les ai, x d'entre eux valent 1. Dans ce cas, le 1 apparaît x+1 fois et du coup le chiffre 'x+1' doit apparaître dans nos ai (il sera la valeur de ai correspondant à bi=1).
Du coup, parmi nos D nombres ai, on en a x+1, et leur somme fait 2x+1. Il en manque donc D-x-1, et leur somme vaut 2D-2x-1.
Tous sont supérieurs à 1 et valent au moins 2, donc leur somme vaut au moins 2D-2X-2. Il en résulte que la seule combinaison possible pour les ai restants est "un 3 et que des 2".

On commence avec D=1 => N=2 => le même chiffre apparaît 2 fois => 2 apparaît dans notre nombre => le seul point fixe est 22

D=2 => N=4
ai = {1 3} => Le 1 apparaît 2 fois, et aucun 2 dans nos ai
ai = {2 2} => Le 2 apparaît 3 fois, et aucun 3 dans nos ai
De manière plus générale, on peut exclure les solutions où tous les ai valent 2.

D=3 => N=6
ai={1 2 3} => Chaque chiffre apparaît 2 fois, et on n'a qu'un seul 2

D=4 => N=8
ai={1 1 3 3} => Les solutions de la forme 31331a1b sont des points fixes (soit 28 points fixes)
ai = {1 2 2 3} => Les solutions de la forme 2132231a sont des points fixes (soit 7 poins fixes)

D=5 => N=10
ai = {1 1 2 3 3} => 3122331a1b sont des points fixes (21)
ai = {1 2 2 2 3} => 4 fois 2, et pas de 4 dans nos ai

D=6 => N=12
ai = {1 1 1 2 3 4} => 2, 3 et 4 apparaissent 2 fois, mais on n'a qu'un seul 2 dans nos ai
ai = {1 1 2 2 3 3} => Chacun apparaît 3 fois, mais il n'y a que 2 fois le chiffre 3 dans nos ai
ai = {1 2 2 2 2 3} => 2 apparaît 5 fois mais 5 n'est pas dans nos ai

D=7 => N=14
ai = {1 1 1 1 2 3 5} => 2, 3 et 5 apparaissent 2 fois, mais on n'a qu'un seul 2 dans nos ai
ai = {1 1 1 2 2 3 4} => 413223241a1b1c sont des points fixes (20)
ai = {1 1 2 2 2 3 3} => 4 fois le chiffre 2 (et inutile d'aller plus loin pour ce cas-ci, le nombre de 2 ne fait qu'augmenter)

D=8 => N=16 / N=17
N=16
ai = {1 1 1 1 2 2 3 5} => 513223251a1b1c1d sont des points fixes (15)
ai = {1 1 1 2 2 2 3 4} => Le 2 apparaît 4 fois, inutile d'aller plus loin

N=17 => Il faut nécessairement un ai à 2 chiffres, or la seule combinaisons est
ai = {1 1 1 1 1 1 1 10}, mais 1 apparaît alors 8 fois et ce n'est pas un ai valide

D=9
N=18
ai= {1 1 1 1 1 2 2 3 6} => 613223261a1b1c1d1e => 6 points fixes
ai= {1 1 1 1 2 2 2 3 5} => Trop de 2, on peut arrêter là

N=19
ai = {1 1 1 1 1 1 1 1 11} => 1111a1b1c1d1e1f1g1h => 9 points fixes
ai = {1 1 1 1 1 1 1 2 10} => 9 fois 1, et pas de 9 dans les ai

D=10
N=20
ai = {1 1 1 1 1 1 2 2 3 7} => 10713223141516271819 est un point fixe
ai = {1 1 1 1 1 2 2 2 3 6} => 4 fois 2, on peut arrêter là

Et enfin dernier cas, N=21
ai = {1 1 1 1 1 1 1 1 2 11} => 101112213141516171819

Total : 1+1+9+6+15+20+21+7+28+1 = 109 points fixes.


Bravo à ceux qui ont trouvé (et cherché)

 #13 - 27-02-2011 11:49:12

gasole
Elite de Prise2Tete
Enigmes résolues : 40
Messages : 1117
Lieu: Toulouse

Applique àCon(way), la suite

Magistral Scarta ! Merci pour cette très jolie démo.

 

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 : Tim, Tam et ?

Sujets similaires

Mots clés des moteurs de recherche

Mot clé (occurences)

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