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 - 17-01-2016 19:12:00

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

l'oconoclaste, l'inspecteur et le prof.

Bonsoir à tous,
Une énigme pas forcément simple pour cette fois.

Ce jour là, on a inauguré une oeuvre d'art numérologique dans le jardin public de la ville. L'artiste y a gravé tous les entiers naturels de 0 à Y. La nuit suivante, un fou furieux a effacé à grands coups de burin beaucoup de nombres: quand il lisait un nombre n, il effaçait le nombre 2n+1. Il a travaillé dans l'ordre croissant. Le lendemain, un inspecteur a été dépêché sur place pour enquêter. Plutôt malin, il a su retrouver la méthode du déséquilibré en observant les nombres intacts: 0,2,3,4,6,8,10,..Consciencieux, il a même compté X nombres intacts jusqu'à 1000, et aussi qu'il restait exactement 1000 nombres intacts.
Un peu plus tard, il en a parlé à son ami le prof de math. Celui-ci, après réflexion, lui a indiqué qu'il aurait pu se passer du comptage exhaustif pour arriver au résultat.
Que valent les nombres X et Y et le prof a t'il raison ?

PS: un comptage informatique est considéré comme un comptage exhaustif....

Bonne recherche.



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

 #2 - 17-01-2016 19:54:47

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2710
Lieu: Luxembourg

L'iconoclaste, l'isnpecteur et le prof.

http://www.prise2tete.fr/upload/nobodydy-N40-p43.jpghttp://www.prise2tete.fr/upload/nobodydy-N40-p38.jpghttp://www.prise2tete.fr/upload/nobodydy-N40-p32.jpg

Une petite précision sur la méthode croissante du fou furieux, stp: il lit 0, donc il efface 1, puis il lit 2 et efface 5, puis lit-il 6 ou retourne t-il sur le 3 non encore lu ?

 #3 - 17-01-2016 20:09:31

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

L'iconoclaste, l''inspecteur et le prof.

Il lit les nombres non effacés dans l'ordre: 0, puis 2 (1 effacé) puis 3 puis 4 puis 6 (5 effacé), etc...

 #4 - 18-01-2016 01:57:22

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

L'iconoclaste, l'inspecteur e tle prof.

On écrit les nombres en binaire, en rajoutant un 0 au départ :

Les nombres qui se terminent par 0 sont intacts
donc ceux qui se terminent par 01 sont effacés
donc ceux qui se terminent par 011 sont intacts
donc ceux qui se terminent par 0111 sont effacés, etc...

Un nombre est donc intact si et seulement si le nombre de 1 terminaux dans l'écriture binaire est pair.

Les nombres intacts sont les nombres de la forme 2x, 8x+3, 32x+15, 128x+63, 512x+255...

De 0 à 1000, le nombre de nombres intacts est donc : 501 + 125 + 31 + 8 + 2
X = 667

De 0 à 1499, le nombre de nombres intacts est donc : 750 + 188 + 47 + 12 + 3 = 1000
Y = 1499

 #5 - 18-01-2016 08:05:53

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

L'iconoclaste, l'insspecteur et le prof.

Titooufred, c'est presque parfait. Il y a une erreur sur Y. Tu n'expliques pas vraiment comment tu obtiens ces nombres. Sinon, la démarche est la bonne. Et bravo pour la rapidité !

 #6 - 18-01-2016 12:29:20

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

l'iconoclaste, m'inspecteur et le prof.

Je me rends compte que j'ai oublié de compter 1023, qui est un nombre de la forme 2048x+1023, ce qui rajoute 1 à mon total pour 1499 et donc j'arrive à 1001 nombres intacts jusqu'à 1499. Il faut donc enlever le dernier intact de ma liste qui est 1499, la bonne réponse est Y = 1498.

Par exemple, pour trouver combien il y a de nombres de la forme 32x+15 entre 0 et 1498, je calcule :
E((1498-15)/32) = E(1483/32) = E(46,34375) = 46
x peut prendre les valeurs de 0 à 46 donc cela fait 47 nombres de la forme 32x+15.

Le nombre d'intacts de 0 à 1498 est : 750 + 187 + 47 + 12 + 3 + 1 = 1000

Remarque : pour trouver une approximation de Y, partant du fait que 1/2 + 1/8 + 1/32 + ... = 2/3, je me suis dit qu'avec 1500 nombres on ne serait pas très loin.

 #7 - 18-01-2016 13:19:21

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

l'iconoclaste, l'inspecteur et ke prof.

C'est correct maintenant Titoufred, bravo à toi. J'ai adopté une méthode légèrement différente, qui permet de voir immédiatement l'approximation.
Avec ta méthode, comment as tu trouvé 1000 ? Sans doute par tâtonnement, non ?
Par exemple si je te demande quel est le 2000 ème intact, comment t'y prends tu ?

Bon, c'est histoire de me rendre compte de l'efficacité de ta méthode.

 #8 - 18-01-2016 22:48:18

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 303

l'iconoclaste, l'inspecreur et le prof.

Les nombres rayés sont ceux dont l'écriture binaire se termine par un nombre impair de "1".

Sur [|0;(2^n)-1|], il y a ((2^n)±1)/3 nombres rayés. Cela se démontre en remarquant que les nombres rayés sur [|0;(2^n)-2|], sont en bijection avec les nombres rayés sur [|2^n;(2^(n+1))-2|] via f(x)=x+2^n, et que (2^n)-1 est rayé <=> (2^(n+1))-1 n'est pas rayé.

Ainsi, sur [|0;1023|],  il y a (1024-1)/3=341 nombres rayés donc 1024-341=683 nombres intacts. En comptant à rebours jusqu'à 1000, je dénombre encore 7 nombres rayés (1021, 1017, 1015, 1013, 1009, 1005, 1001), donc 683-23+7=667 nombres intacts, d'où X=667 (ou 666 si 1000 ne compte pas).

Ensuite, en ajoutant 1024 avec les nombres de [|0;511|], je trouve qu'il y a 683+341=1024 nombres non rayés dans [|0;1535|], et en comptant à nouveau à l'envers, j'arrive à Y=1498.

 #9 - 19-01-2016 08:58:27

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

L'iconnoclaste, l'inspecteur et le prof.

Ebichu, c'est parfait, bravo !
La manière dont je fais le décompte est un peu différente de la tienne (jamais de soustraction), elle est plus systématique, mais bon c'est affaire de goût.

 #10 - 19-01-2016 17:11:28

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

L'iconoclaste,, l'inspecteur et le prof.

Le fou furieux préserve tous les nombres sauf ceux de la forme 2x+1 sauf ceux de la forme 2(2x+1)+1 = 4x+3 ... sauf ceux de la forme [latex]2^n(x+1)-1[/latex]



La formule des nombres intacts jusqu'à N est donc
[TeX]intacts(N) = \sum_{n=0}^{\infty} \left\lfloor \frac{N+1}{(-2)^n}\right\rfloor[/TeX]
Mais on peut faire beaucoup plus jolie. Après tout cette somme ressemble beaucoup à 2/3 de N+1, on ne fait que retirer la moitier puis ajouter la moitier de la moitier etc...

si on écrit la somme en binaire par exemple :
+111001101011
-   11100110101
+    1110011010
-      111001101
+       11100110
-          1110011
...

On voit bien chaque puissance de [latex]2^n[/latex] dans l'écriture de N+1 contribue à la somme totale comme la somme d'une suite géométrique de raison -2,
plus précisément contribue pour [latex]\frac{2^{n+1}+(-1)^n}{3}[/latex]

Finalement :
[TeX]\boxed{intacts(N) = \frac{2(N+1)+difbin1(N+1)}{3}}[/TeX]
où [latex]difbin1(N+1)[/latex] est le nombre de "1" en position pair moins le nombre de "1" en position impaire dans l'écriture binaire de N+1

Une simple application numérique avec [latex]N=1000=\overline{1111101000}^2[/latex]permet de trouver X:
[TeX]\color{blue}{X = (2*1001 + 3 - 4)/3 = 667}[/TeX]
La résolution inverse pour Y est plus subtile :
[TeX]1667 = \frac{2(Y+1)+difbin1(Y+1)}{3}[/TeX]
Le résultat est autour de 3/2*1667 ~ 2500 avec une erreur max de 10 (en regardant l'écriture binaire de 2500)

Code:

def intacts(N):
  def difbin1(x,s):
    return difbin1(x>>1,-s) + s*(x & 1) if x else 0
  return (2*(N+1) + difbin1(N+1,1))//3

for N in range(2490,2510):
  print (N, intacts(N))

Je trouve une solution unique pour Y:
[TeX]\color{blue}{Y=2499}[/TeX]
Merci pour l'énigme smile

 #11 - 19-01-2016 17:13:47

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

L'iconoclaste, l'inspecteur et le proof.

Nodgim, voici un moyen pour trouver directement, sans tâtonnements, le nème nombre intact :

Un exemple pour n = 1000 :

Pour 1 gravé, il y a 1* intact
Pour 2 gravés, il y a 1 intact
Pour 8 gravés, il y a 1+2+1+1 = 5 intacts
Pour 32 gravés, il y a 5+6+5+5 = 21 intacts
Pour 128 gravés, il y a 21+22+21+21 = 85 intacts
Pour 512 gravés, il y a 85+86+85+85 = 341 intacts

Tu décomposes 1000 intacts en une somme avec les nombres d'intacts ci-dessus, mais lors de la 2ème utilisation d'un nombre d'intacts, tu le majores de 1 (*sauf éventuellement si besoin est, pour le dernier 1). Le dernier 1 sera forcément étoilé.

Nombres intacts : 1000 = 341+342+85+86+85+21+22+5+6+5+1+1*

Puis tu fais la somme des nombres gravés correspondants, ce qui te donne le nombre de nombres gravés au départ.

Nombres gravés : 512+512+128+128+128+32+32+8+8+8+2+1 = 1499

Avec 1499 nombres gravés, il y en aura 1000 intacts. Autrement dit, le 1000ème nombre intact est 1498.

Autre exemple avec n = 2000 :

Pour 2048 gravés, il y a 341+342+341+341 = 1365 intacts

Nombres intacts : 2000 = 1365+341+85+86+85+21+5+6+5+1*
Nombres gravés : 2048+512+128+128+128+32+8+8+8+1 = 3001

Pour 3001 nombres gravés, il y en a 2000 intacts. Autrement dit, le 2000ème nombre intact est 3000.

 #12 - 19-01-2016 18:03:39

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

L'iconoclaste, l'ispecteur et le prof.

Bonjour

Il me semble que le plus simple est de compter les non-rayés qui sont tous les entiers écrits pouvant se mettre sous la forme [latex](2n+1).4^p-1[/latex] . Un petit calcul simple nous donne les X qui sont inférieurs à 1000 ( je laisse ça aux as de la programmation ) . Un petit coup d’œil au dernier nombre restant de la liste nous donne une bonne estimation du nombre Y qui terminait liste initiale . On peut ajouter 3 à ce nombre pour être certain de ne rater personne et commencer à lister les valeurs non rayées inférieures à ce nombre .

J'ai sûrement raté quelque chose car je ne trouve pas ça très émoustillant smile

Vasimolo

 #13 - 19-01-2016 19:25:38

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

L'iconoclaste, l'inspecteur et le pro.

Titoufred, ton 2000ème intact est le bon, bravo.
Ta méthode est pas mal, sauf que tu ne dis pas comment tu as obtenu chacun des termes de la somme. L'idéal serait peut être de sortir une formule pour le cas général, et ce serait parfait.

Vasimolo, je ne sais pas trop quoi te dire. Tu penses que le prof a tort et qu'il faut faire la liste des rayés / non rayés, au besoin par voie informatique. Effectivement, vu sous cet angle, ce n'est pas émoustillant. Je croyais que tu me connaissais un peu mieux....

 #14 - 19-01-2016 20:33:12

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

L'icooclaste, l'inspecteur et le prof.

J'ai terminé ma résolution de fou furieux lol

 #15 - 19-01-2016 21:08:09

titoufred
Elite de Prise2Tete
Enigmes résolues : 20
Messages : 1746

L'iconoclaste, l'inspecteur et l eprof.

Chacun des termes de quelle somme nodgim ?

Pour trouver que 1000 = 341+342+85+86+85+21+22+5+6+5+1+1* ?

Tu commences par enlever le plus grand nombre possible dans la liste des intacts : 341.
Il te reste donc 1000 - 341 = 659.
Tu recommences le processus : Tu enlèves le plus grand nombre possible dans la liste des intacts : c'est 341, mais comme tu l'utilises pour la deuxième fois, tu dois enlever 342.
Il reste donc 659 - 342 = 317.
Tu enlèves le plus grand nombre possible dans la liste des intacts : c'est 85
Il reste donc 317 - 85 = 232.
etc...

 #16 - 19-01-2016 22:45:17

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

l'icoboclaste, l'inspecteur et le prof.

Je voulais simplement dire que l'ordre des nombres rayés ne dépend absolument pas du dernier nombre inscrit et que le Y cherché est un très proche voisin du dernier entier non rayé , le reste ...

J'avoue que j'ai du mal à m'intéresser à ce type de problèmes , chacun ses goûts smile

Je ne remets bien sûr pas en cause la qualité de tes interventions .

Vasimolo

 #17 - 20-01-2016 09:47:55

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

L'iconocllaste, l'inspecteur et le prof.

C'est OK Titoufred, tu sais trouver le énième nombre intact et combien d'intacts se trouvent entre 0 et un nombre quelconque. Tu verras d'autres solutions qui font plus "propres" mais l'essentiel est là.

@Vasimolo: je crois que tu rates quelque chose. Il y a une idée simple à trouver à partir de laquelle le problème se résout facilement. Il semblerait bien que tu sois passé à coté. C'est une énigme à la "Vasimolo" en quelque sorte.

 #18 - 20-01-2016 15:27:03

portugal
Professionnel de Prise2Tete
Enigmes résolues : 22
Messages : 374

l'iconoclaste, l'inspecteur et lr prof.

j'ai trouvé la "mécanique" mais le comptage exact semble un peu laborieux..Est ce la piste la plus simple ou y a il mieux ?

On a à partir de chaque nombre pair une chaine où 1 nombre sur 2 nombre est détruit :

Rang               1    2     3      4   
Détruit         N    O     N      O   
Valeur        2n  4n+1      8n+3      16n+7   

Les nombres se rangent donc ainsi :

Rang    Premier terme    intervalle    Détruit ?
1       0                        2               N
2       1                       4               O
n      2^n-1             2^(n+1)     suivant parité

 #19 - 20-01-2016 18:21:16

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

L'iconoclaste, l'inspecteur et e prof.

@Portugal: ce n'est pas la piste que j'ai suivie, mais pourquoi pas ? Y a tout de même un truc qui simplifie grandement la vie.

 #20 - 21-01-2016 08:25:23

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

l'iconoclasye, l'inspecteur et le prof.

@ Matthieu:
Pardon, je n'avais pas lu tes messages, je ne sais pas pourquoi je les ai ratés.
Sinon, c'est correct pour le X, mais faux pour Y. Curieusement, l'erreur vient de la méthode informatique (que je n'ai pas analysée).
Donc, ta formule générale est bonne, mais il faut peut être revoir la manière de s'en servir. Perso, j'ai mis aussi un peu de temps pour mettre au point une bonne méthode manuelle...
Tu n'es pas loin !

 #21 - 21-01-2016 22:41:03

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

l'iconoclaste, l'inspecteur et le orof.

Je suis étonné d'avoir fait une erreur. J'ai tout de même vérifié avec un deuxième programme force brute qui élimine les nombres d'une liste. Pour les de 0 à 10000 je n'ai pas trouvé de différence avec ma fonction.

En lisant tes autres message j'ai vu que Titoufred a calculé le 2000ème intact. Je n'avais pas compris pourquoi. Est ce que ce nombre est Y ?

il a même compté X nombres intacts jusqu'à 1000, et aussi qu'il restait exactement 1000 nombres intacts.

J'avais compris de cette phrase que Y correspondait plutôt au (1000+X)ème intact.

Sinon avec ma méthode je trouve pour 2000 intacts deux valeurs possible pour Y
3000 et 3001 (la seconde étant effacé par le fou furieux)

 #22 - 22-01-2016 08:31:16

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

l'iconoclaste, l'inspexteur et le prof.

Oui Matthieu, en relisant ta réponse, tu n'as pas cherché combien Y faisait si Y était le 1000 ème nombre intact. C'est pourtant bien ce qui était demandé dans l'énoncé, même si c'était indirect.
Sinon tu as bien compris le raisonnement, ce qui est l'essentiel.

 #23 - 22-01-2016 09:02:39

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

LL'iconoclaste, l'inspecteur et le prof.

Le problème a été résolu plusieurs fois, avec pour tous des variantes malgré une trame commune.
On ne pouvait pas résoudre facilement ce problème si on ne pensait pas en binaire. En effet, en binaire, multiplier un nombre par 2 et lui ajouter 1, c'est ajouter 1 au bout du nombre (à gauche si poids faible à gauche).
Exemple:
10111---->110111.

Pour savoir si un nombre est présent ou absent de la liste, il suffit de compter le nb de 1 à gauche: si pair, nombre présent. Si impair nombre absent.

Partant de là, on peut facilement calculer le nombre de survivants de 0 jusqu'à 2^k -1, soit pour un nombre binaire de k chiffres max. On a 2 résultats selon la parité de k:

Nb à 2k chiffres: (2^(2k+1)+1)/3
Nb à 2k+1 chiffres: (2^(2k+2)-1)/3

On peut alors faire une liste selon le nombre de chiffres binaires:
1: 1
2: 3
3: 5
4: 11
5: 21
6: 43
7: 85
8: 171
9: 341
10: 683
11: 1365

Maintenant on est outillé pour répondre aux questions:

1000 s'écrit 000 101 111 1 en binaire (poids faible à gauche)
de 000 000 000 à 111 111 111 , on compte 341 survivants
de 000 000 00 à 111 111 11 on en compte 171
de 000 000 0 à 111 111 1 on en compte 85
de 000 000 à 111 111  : 43
de 000 00 à 111 11 : 21
de 000 à 111 : 5
+ 000 101 111 1

Total: 667 = X

Pour trouver le 1000 ème survivant, il suffit de regarder dans le tableau la valeur immédiatement inférieure à 1000 puis les restes successifs.
On aboutit à Y= 010 110 111 01= 1498. 

Merci aux participants et bravo pour les solutions originales.

 

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 : Pim, Pam et ?

Sujets similaires

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