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 - 19-02-2011 00:30:56

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Applique à Con(wa)

Tout le monde connait la suite de Conway :

11
21
1211
111221 ...

Mais Conway mérite bien son applique à Con ( tion ? ) définie de [latex]\mathbb{N}[/latex] dans lui même . On notera C(n) cette fonction qui compte en mode Conway le nombre de chiffres de l'entier n .

C(3107117)=10311327 car 3107117 est "constitué" de 1 chiffre 0 ,  3 chiffres 1 , 1 chiffre 3 et 2 chiffres 7  .

Les chiffres sont annoncés en ordre croissant de leurs valeurs en "sautant" les chiffres n'apparaissant pas dans l'écriture décimale .

Par exemple C(331)=C(313)=C(133)=1123 ( 1 fois 1 et 2 fois 3 ) .

22 est un point fixe de C car C(22)=22 .

Mais  quel est le plus grand point fixe de C ( s'il existe ) ?

Bon courage smile

Vasimolo

PS : la case réponse valide la réponse lol
PPS : j'ai corrigé une petite coquille relevée par L00Ping007 et Franck yikes



Annonces sponsorisées :

 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 19-02-2011 01:40:19

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

Appliique à Con(way)

Je trouve celui-là : 1111213141516171819
(11-1 1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9)

Mais apparemment cela ne suffit pas !

Par ailleurs, petite coquille dans ton énoncé, c'est 313 er non 131.

J'en ai trouvé d'autres, mais plus petits :
2132231x avec x allant de 4 à 9
1011113141516171819 (1-0 11-1 1-3 ...)

 #3 - 19-02-2011 08:26:45

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

Appique à Con(way)

Hello... j'ai mis "cinq minutes" à me rendre compte qu'un tel point fixe est solution de la (fameuse) phrase auto-référente :

"Cette phrase contient exactement ? fois le chiffre 0, ? fois 1, ? fois 2, ? fois 3, ? fois 4, ? fois 5, ? fois 6, ? fois 7, ? fois 8 et ? fois 9."

Une solution faisant intervenir tous les chiffres forme nécessairement un nombre plus grand qu'une solution ne les faisant pas tous intervenir...

D'après le (lui aussi fameux) Dcode, l'unique solution à la phrase est : 10713223141516271819

qui devrait donc être le plus grand point fixe de C, mais ça ne valide pas... Dcode Dconne ou c'est moi ?

PS : ça serait l'unique solution dans laquelle les chiffres apparaissent au plus 9 fois, il y a mieux apparemment...

 #4 - 19-02-2011 09:15:14

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Applique à oCn(way)

Voila trois grands points fixes:

101111213145161718
1111213141516171819
101112213141516171819 qui a de bonnes chances d’être le plus grand car decrit les dix chiffres ! cool c'est validé.

J'ai noté une erreur mineure dans l’exemple de l'énoncé : C(331) not C(131).

Merci Vasimolo pour cette énigme sympa


The proof of the pudding is in the eating.

 #5 - 19-02-2011 09:21:21

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

applique à con(wau)

Bonne réponse de Franck smile

L'homme serait plus fort que le machine , faut pas Dconner smile

Vasimolo

 #6 - 19-02-2011 10:25:07

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 198

Appliqu à Con(way)

J'ai un nombre:
1111213141516171819
Il ne donne pas la bonne réponse donc ce n'est pas le plus grand.
Je veux juste savoir si ce nombre est correct selon ta définition. (parce que j'ai onze fois le nombre 1)

Finalement j'ai trouvé:
101112213141516171819
Mais faut-il montrer qu'il n'y en a pas au dessus?

 #7 - 19-02-2011 10:36:52

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

appliqye à con(way)

Je n'ai pas de preuve que la réponse proposée est la meilleure ( seulement une quasi-certitude ) mais si quelqu'un se sent d'attaque ...

Vasimolo

PS : Bonne réponse d'Irmo smile

 #8 - 19-02-2011 11:53:24

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

Applique à Con(wya)

Tant qu'a viser un point fixe, je pense a un nombre qui contienne chaque chiffre. Il donnerait donc son propre nombre de 0, de 1, etc. jusqu'a 9, ce qui lui donnerait vingt chiffres.

Et, hop, l'outil d'autoréférence de Dcode :

Cette phrase contient exactement ? fois le chiffre 0, ? fois 1, ? fois 2, ? fois 3, ? fois 4, ? fois 5, ? fois 6, ? fois 7, ? fois 8 et ? fois 9.

donne

1 fois 0
7 fois 1
3 fois 2
2 fois 3
1 fois 4
1 fois 5
1 fois 6
2 fois 7
1 fois 8
1 fois 9

donc 10713223141516171819 est un point fixe de la fonction, et très probablement le plus grand. Sauf que ma réponse n'est pas validée... Y aurait-il plus grand encore ? oO'

Je sais : on peut ajouter un chiffre !

101112213141516171819 marchera peut-être mieux ? Oui ! Yeah !


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

 #9 - 19-02-2011 12:16:33

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

aoplique à con(way)

Il y a une petite subtilité qui a échappé à ceux qui "coincent" , je donnerais un petit indice ...

... demain lol

Vasimolo

 #10 - 19-02-2011 12:51:13

franck9525
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1922
Lieu: UK

Aplique à Con(way)

Il aurait été subtil de dire 10manche wink


The proof of the pudding is in the eating.

 #11 - 19-02-2011 14:28:33

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

Appliqque à Con(way)

Ok, j'ai trouvé, ça valide mais j'avais mis hors jeu ce genre de réponse : 101112213141516171819 qui doit se lire "un 0, onze 1, etc", sans vouloir chipoter outre mesure, cette séquence peut aussi se lire "un 0, un 1, douze 2, etc"

Donc suivant la lecture,
101112213141516171819 égale :

- C(987654322111111111110) qui contient onze 1
mais aussi bien
- C(987654322222222222210) qui n'en contient qu'1

Donc si tu permets ceci, ta fonction C perd un de ses caractères importants : connaissant C(n) pouvoir reconstituer les chiffres qui composent n (modulo leur ordre).

Objection votre honneur !

 #12 - 19-02-2011 17:48:58

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

applisue à con(way)

Bonne réponse de Mathias et gasole smile

gasole a écrit:

Ok, j'ai trouvé, ça valide mais j'avais mis hors jeu ce genre de réponse ... blablabla ... Objection votre honneur !

Tu mets hors jeu qui tu veux et tu objectes tout ce que tu veux mais il n'y a pas d'ambiguité dans la question hmm

Vasimolo

 #13 - 19-02-2011 17:50:41

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

Applique à Con((way)

Ahaaaaaah il est bien feinté le Gasole lol


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

 #14 - 19-02-2011 18:45:17

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

applique à cob(way)

C'est vrai, l'énoncé ne précisait pas que C doive être injective (modulo l'ordre des chiffres)... Mea ultima culpa.

"Objection votre honneur!" était une formule destinée à provoquer un effet comique par l'évocation, saugrenue dans le contexte, du monde judiciaire où elle est couramment employée en qualité d'acte de langage de type obligatif-directif, mais qui ne saurait dans la situation présente prétendre au moindre effet perlocutoire, bien entendu.

J'adore jargonner big_smile

 #15 - 19-02-2011 20:43:11

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,464E+3

Applique à Con(ay)

Il ne peut pas commencer par 4 vu que ce serait 44 soit 4444 ,
or 44 et 44 font 84 big_smile en fait, pas de chiffre supérieur à 3 ...

33 ? donc 33 3?
33 33 non , c'est 43
33 32 : 333222 non car c'est 3352
33 31 : 333111... donc 333 111 1 non, c'est 3341
3330 : 333000... peut -être 33 30 00 22 33 30 22 3 30 22 ..... 

Avec 00 = rien on va super loin ! Mais "yenapas" ne valide pas non plus la case réponse .


PFfffffffff .......... , je viens de tilter : "annoncer les chiffres par ordre croissant"


La case réponse ne valide pas mais je propose :

61 32 23 14 15 26 17 18 19

Voire ( en rusant un peu avec le zéro ) :

10 71 32 23 14 15 16 27 18 19

Edit: Un MP me dit de creuser un peu plus, donc je dois être sur la bonne voie...
Pas moyen de trouver mieux avec 20 chiffres et là... tilt !


Et bien j'aurai eu du mal avec celle-là.
10 111 22 13 14 15 16 17 18 19

 #16 - 21-02-2011 09:46:52

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

Applique à Con(wway)

Bon ok, la réponse est 101112213141516171819
Quant à savoir si c'est la meilleure...
Oui ça l'est !!!

Démonstration

Supposons qu'il existe un point fixe de k chiffres, k >= 21. On a deux cas:
On appelle N la fonction qui a X associe le nombre de chiffres de X, autrement dit N = E(log(X))+1

- soit il contient tous les chiffres de 0 à 9 au moins une fois.
Dans ce cas, il est de la forme [latex]a_00a_11a_22a_33a_44a_55a_66a_77a_88a_99[/latex], avec les [latex]a_i[/latex] des nombres de 1 chiffre ou plus.
On sait que
1°) [latex]\sum_{i=0}^9a_i=k[/latex]
2°) [latex]\sum_{i=0}^9N(a_i)=k-10[/latex]
Le point 1 découle du fait qu'il doit y avoir k chiffres dans notre point fixe, donc en additionnant le nombre d’occurrences de chaque chiffres, on tombe sur k
Le point 2 découle aussi du fait qu'il doit y avoir k chiffres dans notre point fixe : si on ôte les 10 chiffres de 0 à 9 de notre écriture, il doit en rester k-10

Soit q le nombre de [latex]a_i[/latex] qui sont inférieurs à 10 et ne s'écrivent donc qu'avec un seul chiffre. On remarque que q <10, sinon [latex]N(a_i)=1[/latex] et k-10 = 20, ce qui est contraire à notre hypothèse.

Pour écrire les [latex]a_i[/latex] de plus d'un chiffre, il faut donc avoir recours à k-10-q chiffres. Parmi ceux là 10-q seront des chiffres d'unité (puisque ces [latex]a_i[/latex] particuliers sont au nombre de 10-q)
Les chiffres des dizaines (voire plus, centaines, milliers, ...) sont donc au nombres de k-10-q-10+q = k-20

Et donc, le moment le plus important :


... (suspense...)
[TeX]k = \sum_{i=0}^9a_i \geq (k-20)*10+q[/TeX]
(Explications: q nombres d'un chiffre non nuls et k-20 chiffres qui correspondent au moins à des dizaines. Leur somme est donc supérieure à 10*(k-20) + q)
Dans ce cas k <= 22.2222 -q/9
Si k=22, alors 22 <= 22.222-q/9 et donc q<=2, ce qui signifie que la somme k vaudrait donc au minimum 82 et non pas 22. Pour 21, on va voir plus bas que c'est ok; mais on va d'abord clore notre autre cas.

- soit il ne contient pas tous les chiffres de 0 à 9 au moins une fois.
Le même raisonnement reste valable (c'est même pire, 21 n'est plus une solution dans ce cas)


Revenons à notre fameux 21

Si k=21, alors 21 <= 22.2222 -q/9, donc q <=11. C'est super ok smile (ben oui, q ne peut pas dépasser 10 tel qu'on l'a défini)
D'ailleurs, pour k=21; on a une solution: 101112213141516171819

Est-ce la meilleure ?
On sait que l'un des [latex]a_i[/latex] fait au moins 2 chiffres, les autres 1 seul.
Si un [latex]a_i[/latex] vaut 10 ou plus, la somme des 9 autres vaut 11 ou moins. Si 3 d'entre eux était supérieurs à 2 ou égaux à 2, la somme des 6 autres serait de 5, ce qui est impossibles (6 entiers non nuls sommés font au moins six).
Donc au plus 2 [latex]a_i[/latex] parmi les 9 valent 2, les 7 autres valent donc 1.
Donc [latex]a_1 \geq 7[/latex]. De là, il s'ensuit que [latex]a_1[/latex] est nécessairement le [latex]a_i[/latex] de 2 chiffres.

Cas [latex]a_1 = 10[/latex]
Dans ce cas [latex]a_0[/latex] vaut au moins 2.
> [latex]a_0 = 2[/latex] ===> Dans ce cas, [latex]a_2[/latex] vaut au moins 2
> > [latex]a_2 = 2[/latex]. Dans ce cas, [latex]a_0+a_1+a_2 = 14[/latex], donc la somme des 7 autres fait 7, donc chacun des 7 autres fait 1, mais 201012213141516171819 n'est pas un point fixe

> > [latex]a_2 \geq 3[/latex] : c'est pire: car la somme de 7 entiers non nuls devrait faire 6...

> [latex]a_0 = 3[/latex], dans ce cas [latex]a_0 + a_1 = 13[/latex], la somme des 8 autres fait 8, donc chacun des 8 autres fait 1, mais 301011213141516171819 n'est pas un point fixe

> [latex]a_0 \geq 4[/latex], la somme de 8 entiers non nuls devrait faire 7...

Cas [latex]a_1 = 11[/latex]
> Tous les autres [latex]a_i[/latex] valent 1: la somme fait 20
====> un autre [latex]a_i[/latex] au moins fait 2 ou plus.
> Un autre [latex]a_i[/latex] fait plus de 2. Dans ce cas, la somme des 8 autres a_i devrait faire 7 ou moins, c'est pas bon
====> hormis [latex]a_1[/latex], aucun autre [latex]a_i[/latex] ne fait plus de 2

Dans ce cas, un autre [latex]a_i[/latex] vaut 2, et donc [latex]a_2[/latex] vaut au moins 2.
Il s'ensuit donc que [latex]a_2 = 2[/latex] et que le point fixe est
101112213141516171819

Enfin, juste pour finir la démo proprement
[TeX]a_1 = 12[/TeX]
Dans ce cas, tous les autres [latex]a_i[/latex] valent 1. On se contentera de remarquer que 101211213141516171819 n'est pas un point fixe
[TeX]a_1 \geq 13[/TeX]
Dans ce cas, la somme des [latex]a_i[/latex] vaut au moins 13+9 = 22


Conclusion : le plus grand point fixe est 101112213141516171819
C'est par ailleurs le seul point fixe de 21 chiffres.
CQFD

 #17 - 21-02-2011 17:43:17

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

applique à xon(way)

Elle me plait bien cette énigme. Malheureusement je ne peux pas y consacrer le temps que je voudrais.

A ce sujet, peut-on écrire 102 s'il y a 10 chiffres 2?

Je trouve: 10 71 32 23 14 15 16 27 18 19 mais ça ne suffit toujours pas...
Il me semble pourtant qu'on ne peut pas faire plus grand avec des nombres de chiffres à un seul chiffre. En effet il y a le nombre maximum de chiffres: 20 dans ce cas. Chaque chiffre étant représenté, son compte vaut au moins 1. Il n'y a donc qu'un 0 et le nombre commence donc pas 10. On ne peut pas écrire 91. En effet il y a au plus 11 1 (les 10 comptes et le 1). Le fait d'écrire 91 enlève 1 1 possible, on tombe à 10 max. Mais si on écrit 9 1, il y a au moins 2 9 donc un 1 de moins et au moins 2 2 (ou un compte >1 devant un autre chiffre) donc on tombe à 8 1 max. En fait on voit même qu'il peut y avoir au maximum 7 1 car 2 2 n'est pas possible dans ce cas (les 2 2 de 2 2 et 2 9 ça fait 3) donc il n'y a pas non plus de 1 devant le 3 d'où 7 au maximum. Le plus grand nombre commence donc par 1071.
Ensuite si on écrit 42: on a le 2 de x2, le 2 de 24 et le 2 de 27. Il en manque 1.Si on met un 2 devant 5,6,8 ou 9 restant, il faut rajouter un de ces chiffres et autant de chiffres de ce type. Impossible. 23 n'est pas possible pour la même raison: il faudrait mettre un 2eme 3 et autant de ces chiffres.
De proche en proche, on trouve le nombre ci-dessus.

Il me semble que la seule façon d'aller plus loin est d'autoriser les nombres de chiffres à plusieurs chiffres. Mais je n'ai pas le temps d'aller plus loin.

 #18 - 21-02-2011 20:45:48

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

Appique à Con(way)

Je propose 101112213141516171819

 #19 - 21-02-2011 22:09:52

dylasse
Professionnel de Prise2Tete
Enigmes résolues : 21
Messages : 374

Appliqu à Con(way)

101112213141516171819 enfin !!!!
(après avoir longtemps buté sur 10713223141516271819).

amusant !

 #20 - 22-02-2011 02:38:31

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

applique à von(way)

Quel idiot il me manquait que le 22 au milieu de mon nombre lol
Qui a le courage de se lancer dans la magistrale demo de sacra ? Impressionnant !

 #21 - 22-02-2011 08:43:33

rivas
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1105
Lieu: Jacou

Applique à Con(way

Belle énigme.
Je n'ai pas eu le temps de finir. Ca m'énerve smile
J'en étais à 101113223141516171819 sur mon brouillon, plus très loin.

Très belle démo de scarta que j'ai survolée. Je vais la relire en détail pour le plaisir.

 #22 - 22-02-2011 09:49:54

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

appmique à con(way)

La démo est pas très compliquée.
Dans les grandes lignes c'est
1) Montrer qu'aucun point fixe ne peut avoir 22 chiffres ou plus
2) Montrer que pour 21 chiffres, il n'en existe qu'un

 #23 - 22-02-2011 19:45:34

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Applique à Con(way

Bravo à tous smile

Il fallait accepter de sortir du modèle "un chiffre pour un chiffre" pour atteindre la solution . Je vais décortiquer la démonstration de scarta qui a osé ( le bougre mad )

Merci à tous big_smile

Vasimolo

 

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 : 

Dans une course, vous doublez le 19ème, en quelle position êtes-vous ?

Sujets similaires

Mots clés des moteurs de recherche

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