Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Points dissimulés

Posté par
Vassillia
13-10-21 à 12:26

Bonjour à tous,

On connait l'expression chercher une aiguille dans une botte de foin, essayons de la mettre en pratique.

n points sont dissimulés dans un disque donc invisibles pour nous. Le but est de les retrouver et pour cela on va avoir le droit à des indices
A chaque étape, on donne les coordonnées d'un point quelconque :
-si c'est un point dissimulé alors il est découvert (bravo)
-sinon, on apprendra la distance entre ce point quelconque et le point encore dissimulé le plus proche

En combien d'étapes au maximum va t'on retrouver tous les points pour n=1 ? n=2 ? n=3 ? Généralisons ensuite si possible

Voici un petit programme du Grenier de Tolokoban dont je félicite l'auteur pour tester vos stratégies avec n=3. Les points apparaissent bel et bien si vous cliquez au bon endroit et le compteur d'étapes s'incrémente.

Posté par
GBZM
re : Points dissimulés 13-10-21 à 15:22

Bonjour Vassilia,

Sans trop me fouler, pour n=1, je tombe pile sur le point au 3e essai.
Le petit programme est amusant et addicitf. Un truc un peu casse-pied : on peut mettre plusieurs essais à cliquer pile sur l'emplacement d'un point qu'on a pourtant parfaitement déterminé, à cause de l'imprécision de la souris.

Posté par
Vassillia
re : Points dissimulés 13-10-21 à 15:42

Adjugé pour n=1, je sais faire en 3 essais aussi. Je ne vois pas comment on pourrait faire mieux, ce n'est pas trop difficile à démontrer.

Tant mieux si le jeu t'amuse, c'est vrai que l'imprécision de la souris peut provoquer plusieurs essais, ça m'arrive aussi... mais c'est juste pour l'expérimentation.

Si tu me dis que tu as une stratégie en un certain nombre d'essais et que tu arrives à me convaincre qu'elle est valable pour toutes les configurations, peu importe que tu ne cliques pas exactement au bon endroit. Au final, tu auras trouvé quand même

Posté par
verdurin
re : Points dissimulés 13-10-21 à 18:57

Bonsoir,
je suis curieux de voir comment vous faites pour n=1.
Il me semble qu'après deux essais on a une configuration symétrique par rapport à la droite joignant les deux essais.
Et donc encore 2 possibilités pour le point à trouver.

Je ne vois pas la ruse.

Posté par
GBZM
re : Points dissimulés 13-10-21 à 19:08

ruse :

Points dissimulés

Posté par
verdurin
re : Points dissimulés 13-10-21 à 19:43

J'ai oublié qu'on était dans un disque.

Posté par
GBZM
re : Points dissimulés 13-10-21 à 21:17

Un élément de stratégie : toujours taper dans les coins du domaine blanc.

Posté par
Vassillia
re : Points dissimulés 13-10-21 à 23:13

Yes, c'est pour ça que le 2ème essai, je le fais à une intersection entre le cercle venant du premier essai et le périmètre du disque initial.
Pour n=2, déjà ça se complique comme on ne peut pas promettre que le 3ème essai donnera un point dissimulé. En prévoyant le pire des cas, sauf erreur, on peut en déduire un nombre d'essais maximum.

Pour la généralisation et même pour n=3, disons que je sais faire une majoration  faute de mieux car sinon je m'embrouille donc c'est sur qu'il est possible de faire mieux et je compte un peu sur vous (enfin au moins sur GBZM du coup )

Posté par
dpi
re : Points dissimulés 14-10-21 à 08:17

Bonjour,
Attention à l'addiction.....
On cherche le point vert  en 3 essais en tout cas en 4 en cliquant
sur les points d'intersection des deux premiers cercles.
Il faut une bonne souris

Posté par
GBZM
re : Points dissimulés 14-10-21 à 14:38

Pour deux points, 7 essais suffisent.

Posté par
Vassillia
re : Points dissimulés 14-10-21 à 14:48

Bonjour,

On est d'accord, c'est le cas où le 3ème essai et le 4ème essai indiquent le même point dissimulé donc on a "perdu" un coup.
Le truc que je n'arrive pas bien à faire, c'est limiter les risques de ce genre de situation donc pour la généralisation, je me dis qu'au pire, ça arrive à chaque fois... Pas top.

dpi, si tu regardes la ruse de GBZM, il force l'une des 2 intersections obtenues à partir des premiers cercles à être en dehors du disque donc 3 essais sont suffisants puisque le point dissimulé ne peut pas être en dehors du disque.

Posté par
dpi
re : Points dissimulés 15-10-21 à 08:30

Bonjour,
Je suis arrivé à 7 essais pour 2 points et à 11 pour 3.

Posté par
GBZM
re : Points dissimulés 15-10-21 à 09:53

Je n'ai pas vraiment trouvé de scénario nécessitant 11 essais pour 3 points.

Posté par
dpi
re : Points dissimulés 15-10-21 à 12:03

Pour 10 essais pour 3 points

Points dissimulés

Posté par
Vassillia
re : Points dissimulés 15-10-21 à 13:42

dpi, d'accord mais le but maintenant est de systématiser ta méthode pour avoir toujours 10 essais maximum

Je ne suis pas plus avancée, c'est à dire que chaque point dissimulé peut être trouvé en 3 ou 4 essais max car si on a 3 cercles concourants, il faut absolument choisir ce point au prochain essai pour qu'il arrête de parasiter la suite.
Dès qu'on a 2 points dissimulés, on peut en avoir 1 qui nécessite 4 essais et au moins le dernier point ne nécessite que 3 essais.
Donc si on note M(n) le nombre max d'essais nécessaires (à condition de s'organiser un peu quand même ), on a selon moi 3n + \left\lfloor\dfrac{n}{2}\right\rfloor \leq M(n) \leq 4n-1
Désolée GBZM, je sais que tu essayes de réhabiliter l'ensemble vide mais cet encadrement n'est valable que pour n>0.
Pour n=1 et n=2 tout va bien, pour n=3 ben je sais pas trop si c'est 10 ou 11 essais, je penche pour 10 comme je n'ai pas encore trouvé de configuration nécessitant 11 mais pas sure et au delà je ne visualise plus du tout.

Posté par
GBZM
re : Points dissimulés 15-10-21 à 14:14

Une situation où, avec pas de chance dans des choix, on a besoin de 11 essais.

Points dissimulés

Posté par
Vassillia
re : Points dissimulés 15-10-21 à 15:34

Merci GBZM, bien vu, du coup on va être sur M(n)=4n-1 si on continue à avoir la poisse à chaque choix avec une configuration qui fait tout pour nous embêter.
J'imagine aussi qu'on devrait pouvoir le démontrer par récurrence à partir de ton dessin mais je sens que ça va être casse-pied à écrire.
Juste par curiosité, mettons que la règle soit de choisir systématiquement l'intersection avec le cercle venant du plus ancien essai, elle ressemblerait à quoi la configuration problématique ?

Posté par
GBZM
re : Points dissimulés 15-10-21 à 15:56

Je vois plutôt, au fur et à mesure que l'"attaquant" choisit des points, des réponses du "défenseur" qui sont compatibles avec la règle et placent l'attaquant en position défavorable. Il me semble maintenant assez clair que le défenseur peut imposer que chaque point trouvé soit à l'intersection de 3 cercles, sauf le dernier à l'intersection de 2.

Posté par
Vassillia
re : Points dissimulés 15-10-21 à 16:16

Ah oui, c'est nettement plus facile à voir comme ça !
Effectivement si les points encore dissimulés bougent en fonction de notre choix pour se cacher là où ça ne nous arrange pas, c'est assez facile à provoquer en fait.

Posté par
ty59847
re : Points dissimulés 15-10-21 à 16:33

Sur le dessin proposé par GBZM à 14h14, la stratégie du joueur n'est pas optimale.
A, B, C : ok.
A ce moment on sait que sauf coup du hasard infiniment improbable, un des 2 points D ou E est solution.
On a 2 arcs de cercle partant de C, on sait qu'on a un point sur chacun de ces 2 arcs.
L'arc de cercle partant vers le bas du dessin étant le plus court, on a plutôt intérêt à parier sur le point E que sur le point D.

Continuons.
On a joué D. Puis E, forcé.
Ensuite, le choix de F ne semble pas judicieux.
Ce point est trop central, on va balayer une surface importante, et donc on a un risque fort que le point touché ne soit pas celui sur la portion de cercle de centre B.
On avait plutôt intérêt à choisir le point d'intersection tout en haut.

Mais ça ne change rien au résultat, même en choisissant bien les points pour minimiser les risques, on a un risque de ne pas aboutir en moins de 11 coups.
L'intérêt de choisir des mauvais coups, c'était ici que ça permettait de bâtir un dessin où on a besoin de 11 coups, sans avoir des points  trop près des bords ou trop près les uns des autres.

Je me posais d'autres questions de stratégie.
On a placé un premier point, sur le bord. On obtient un arc de cercle.
Si cet arc de cercle est très petit, ou s'il est très grand, a-t-on systématiquement intérêt à chercher tout de suite le point qui est sur cet arc de cercle... ou bien garder cet arc de cercle en attente, et chercher un autre point ailleurs...
Mais a priori, on a toujours intérêt à se focaliser sur un premier point, placer ce premier point pour qu'il disparaisse. Puis continuer  avec la même règle.

Posté par
GBZM
re : Points dissimulés 15-10-21 à 17:25

À mon avis, les considérations sur la longueur des arcs de cercle ne sont absolument pas pertinentes pour l'estimation du nombre d'essais nécessaires dans le cas le pire.

Posté par
Vassillia
re : Points dissimulés 15-10-21 à 19:16

Les arcs de cercle je ne suis pas convaincue mais quand même je me demande si dans le doute il ne faudrait pas faire le prochain essai en choisissant le plus proche possible du bord du disque. En espérant avoir d'autres intersections en dehors du disque car là on est en tranquille. Mais ce n'est qu'une intuition, en vrai je n'en sais rien du tout.

Posté par
ty59847
re : Points dissimulés 15-10-21 à 19:46

@GBZM
Tout à fait, et d'ailleurs je le disais dans mon message.

Posté par
GBZM
re : Points dissimulés 15-10-21 à 21:56

Vassilia, la seule partie utile du disque est celle qui reste en blanc. Donc je ne vois pas vraiment l'intérêt d'être près du bord du disque, du moment qu'on tape dans les coins de la partie en blanc.

Posté par
Vassillia
re : Points dissimulés 15-10-21 à 22:29

Euh oui, tu as raison, je n'ai rien dit, il n'y a aucune raison valable pour que ça nous arrange dans le cas général. C'est juste que sur ton exemple, on s'en sort mieux si au lieu de choisir F, on prend l'intersection du disque initial avec le cercle de centre B mais c'est une coïncidence.

A la limite, ce qu'il faudrait faire, c'est réfléchir à la distance que peut parcourir le prochain cercle dans la zone blanche restante et choisir le min sauf que la réponse va dépendre du rayon qui est inconnu. Donc on ne s'en sortira jamais pour augmenter nos chances de faire le "bon choix"

Je pense quand même que sur une configuration donnée, on a quand même une sacré poisse si on a besoin de 4n-1 essais. Pour n=3 par exemple, je ne l'ai pas trouvé, la plupart du temps j'avais 9 essais, parfois 10

Posté par
Vassillia
re : Points dissimulés 15-10-21 à 22:47

Qu'il n'y ait pas de malentendu, je suis d'accord sur le fait qu'il y aura toujours un pire cas qui va nécessiter le pire nombre d'essais mais un peu comme ty59847, j'essaye de négocier pour tomber le moins possible sur ce pire cas. Sans grande conviction puisque de toute façon sans connaitre la distribution de proba, on ne peut pas faire grand chose.

Posté par
ty59847
re : Points dissimulés 15-10-21 à 23:33

Quand on ne sait pas où cliquer, on cherche le point le plus loin possible du centre de gravité de la partie blanche, à la frontière de la partie blanche.

Posté par
dpi
re : Points dissimulés 16-10-21 à 08:36

Bonjour
On peut faire 3 si on gagne à l'euromillion .

La stratégie pour 3 essais pour 1 peut être renouvelée pour 2 points.
A ce stade il reste une partie blanche et on clique au centre de cette
zone en direction du centre du cercle initial et en deux essais on a le 3 ème point.  
Soit 9 essais  hors  chance...

Points dissimulés

Posté par
ty59847
re : Points dissimulés 16-10-21 à 11:00

Quand tu cliques loin du bord, et à nouveau loin du bord, tu te retrouves généralement avec 2 cercles complets, et 2 points d'intersection.
Et donc tu as une chance sur 2 de bien tomber, en cliquant au hasard sur une des 2 intersections.
La stratégie 'cliquer au centre' est très mauvaise, comme ça a déjà été dit.

En cliquant systématiquement sur le bord, tu te retrouves avec 2 portions de cercle, et un seul point d'intersection. Et donc la quasi-certitude de trouver un point en 3 clics.

Trouver les 3 points en 9 clics, c'est la norme, c'est le résultat obtenu presque systématiquement (90 fois sur 100 , voire plus) Quand on n'a pas de chance, il faut 10 essais.
Et si on est vraiment poissard, on peut avoir des cas où il faut 11 essais.

Posté par
dpi
re : Points dissimulés 16-10-21 à 11:11

J'ai plusieurs fois trouvé 2 en 5 .
Objectif  8

Posté par
ty59847
re : Points dissimulés 16-10-21 à 11:40

Trouver 2 points en 5 clics, ça tient du miracle.
On clique sur un point au hasard, sur un arc de cercle, et on tombe sur le bon point.
Pour 2 points, il faut en général 6 clics,  et si on est poissard 7 voire 8 clics.

Posté par
GBZM
re : Points dissimulés 16-10-21 à 11:40

Je prétends que tu ne peux pas faire moins de 11 essais pour 3 points dans le pire des cas.

Je te propose un petit jeu : tu places un point,  Je te réponds. Tu places un deuxième point, je te réponds etc.
Je parie que je te force à faire 11 essais pour trouver les 3 points.

D'accord ? Pas ce week-end, mais à partir de lundi.

Posté par
ty59847
re : Points dissimulés 16-10-21 à 11:58

GBZM
Le jeu que tu proposes est différent du jeu initial.
Dans le jeu initial, un arbitre A  place 3 points sur le disque, et ensuite, le joueur B cherche ces 3 points.
Dans le jeu que tu proposes, le joueur B cherche les points, et A place les points au fur et à mesure, en fonction des décisions du joueur B, pour compliquer la tâche du joueur B.
A n'est plus un arbitre, mais un adversaire.

Posté par
Vassillia
re : Points dissimulés 16-10-21 à 12:14

Bonjour,
Si on joue contre GBZM, il n'y a plus trop de suspens, il faudra faire systématiquement le nombre d'essais maximum et c'était bien la question initiale donc si c'est le jeu ! Bien sur, en général, on fera moins d'essais avec de la chance mais trouver le nombre d'essais minimum n'est pas trop difficile, c'est n même si en pratique ça n'arrivera pas.

Ceci dit, moi je promets quand même 7 essais pour n=2 donc pas tout à fait d'accord avec ty59847, je n'aurai jamais besoin de 8 essais.

Tu devrais essayer de relever le défi dpi pour voir la différence entre trouver car tu as eu de la chance (et tant mieux, profites-en) ou trouver car ta stratégie fonctionne systématiquement en au pire tant d'essais ce qui encore une fois était la question initiale.
En plus, comme ça on va avoir une jolie succession de figures Geogebra

Posté par
ty59847
re : Points dissimulés 16-10-21 à 12:19

7 et non 8 ... tu as probablement raison, j'ai répondu mécaniquement.

Posté par
GBZM
re : Points dissimulés 16-10-21 à 15:52

Je confirme que le défi que je propose est bien exactement le problème initial.
Il s'agit de démontrer "il existe une stratégie en tant d'essai max, telle que quelle que soit la position des points ... "
Le gentil qui veut démontrer l'affirmation fait sa proposition d'essais, et le méchant (moi) qui veut démontrer qu'elle est fausse choisit les positions de points en fonction des essais proposés par le gentil.
En dessous de 11, le méchant gagne.

Posté par
dpi
re : Points dissimulés 16-10-21 à 17:14

le miracle de 5 pour 2 points
Je fais 9 à 80 % mais 8 pas ce soir sinon addiction

Points dissimulés

Posté par
Vassillia
re : Points dissimulés 16-10-21 à 19:39

Tu sais dpi, si tu t'intéressais à ce qu'on raconte, tu saurai que si tu as réussi par chance à avoir 2 points en 5 essais, il est sur et certain que tu auras le dernier point en 3 essais donc le 8 essais, tu l'aurais déjà eu. Enfin bon, si tu t'amuses, c'est ce qui compte

Posté par
dpi
re : Points dissimulés 17-10-21 à 09:35

Bon dimanche,

Chaque fois que j'ai  réussi 2 points en 5 essais ,j'étais persuadé
d'arriver à  8 pour 3 ,mais la précision de la souris me donnait
un mini point rouge...
Mais cette fois je l'ai eu

Je propose de laisser le fil open pour 7....3

Points dissimulés

Posté par
GBZM
re : Points dissimulés 18-10-21 à 18:44

Je vois, dpi, que ça ne t'intéresse pas d'être forcé à faire 11 essais pour 3 points.

Posté par
dpi
re : Points dissimulés 19-10-21 à 06:20

Qui peut le moins peut le plus...
Je ne désespère pas d'arriver à 7..

Posté par
GBZM
re : Points dissimulés 19-10-21 à 10:38

Je pense que tu n'as pas bien compris le sens de l'énigme.

Posté par
Vassillia
re : Points dissimulés 19-10-21 à 13:32

Le problème dpi, c'est que de la manière dont tu t'y prends, je ne suis même pas sure que tu fasses systématiquement 11 essais max, tu risques même de faire plus contre GBZM.
C'est pour ça que je pense que tu devrais accepter son défi pour comprendre où il peut y avoir des problèmes. Pour le moment, tout ce que tu fais c'est compter sur la chance alors tu passeras peut-être 7 essais mais ça ne prouvera rien du tout.
Je le ferai bien moi même pour te montrer mais je sais ce qu'il va faire et il sait ce que je vais faire donc l'interet est limité.

Posté par
verdurin
re : Points dissimulés 19-10-21 à 18:38

En fait, si on a beaucoup de chance, on trouve les trois points en trois essais.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !