Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 50

énigme solitaire



  1. #1
    matthias

    énigme solitaire


    ------

    Vous connaissez tous le jeu du solitaire (pas celui avec les cartes, celui-là).
    On garde les mêmes règles mais on prend comme plateau le plan entier (disons ZxZ) et comme situation initiale toute situation telle qu'un demi-plan (disons y > 0) soit vide. Dans l'autre demi-plan (y <=0) on dispose d'autant de pions que l'on veut (même une infinité, le choix est libre, le placement des pions aussi, on peut remplir le demi-plan si on veut).
    La question est : jusqu'où peut-on amener un pion (ordonnée maximale atteignable, si elle existe) ?

    Illustration d'une situation initiale :

    -----
    Images attachées Images attachées  

  2. Publicité
  3. #2
    homotopie

    Re : énigme solitaire

    Salut,
    au bout d'un nombre dénombrable de coups (c'est long surtout vers la fin) le plan est rempli.

  4. #3
    martini_bird

    Re : énigme solitaire

    Salut,

    au premier ordinal transfini ? Tu fais comment?

  5. #4
    invite986312212
    Invité

    Re : énigme solitaire

    Citation Envoyé par homotopie
    Salut,
    au bout d'un nombre dénombrable de coups (c'est long surtout vers la fin) le plan est rempli.
    donc c'est encore plus fort que l'hôtel infini de Hilbert?
    puisqu'au solitaire à chaque fois qu'on saute on enlève un pion. Donc si je te suis bien, on part d'un demi-plan rempli, on enlève une infinité de pions et on finit avec tout le plan rempli... pas mal.

  6. A voir en vidéo sur Futura
  7. #5
    matthias

    Re : énigme solitaire

    Avant d'essayer de remplir le plan, il faudrait déjà pouvoir amener un pion aussi loin que l'on veut. Or contrairement à ce que pourrait suggérer l'intuition, ce n'est pas évident. Pas évident du tout même

  8. #6
    invite986312212
    Invité

    Re : énigme solitaire

    Citation Envoyé par matthias
    Avant d'essayer de remplir le plan, il faudrait déjà pouvoir amener un pion aussi loin que l'on veut
    intuitivement, pour amener un pion aussi loin qu'on veut, il faut faire progresser une sorte de triangle et si ce triangle n'a pas de trous, ce qui reste à prouver, il va bien "finir" par remplir le plan.

  9. Publicité
  10. #7
    matthias

    Re : énigme solitaire

    Vous êtes bien ambitieux.
    Je vous propose de commencer de manière plus modeste. Auriez-vous une solution explicite pour pouvoir amener un pion en y=1, 2, 3, 4, 5 ?
    Vous allez voir que ça se complique vite.

  11. #8
    Evil.Saien

    Re : énigme solitaire

    Salut,

    Intuitivement, je dirais 5 cases maximum.
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  12. #9
    matthias

    Re : énigme solitaire

    Citation Envoyé par Evil.Saien
    Intuitivement, je dirais 5 cases maximum.
    Ton intuition vient-elle d'essais que tu as faits, de ma proposition de tester pour y allant de 1 à 5, ou juste comme ça ?
    En tout cas ce n'est pas ça, mais ce n'est vraiment pas loin

  13. #10
    yat

    Re : énigme solitaire

    Citation Envoyé par matthias
    Ton intuition vient-elle d'essais que tu as faits, de ma proposition de tester pour y allant de 1 à 5, ou juste comme ça ?
    En tout cas ce n'est pas ça, mais ce n'est vraiment pas loin
    On peut aller plus loin que 5 ?
    Moi je n'arrive pas à dépasser le 4 ...

    J'espère qu'il y aura une petite démo à la clé

  14. #11
    matthias

    Re : énigme solitaire

    Citation Envoyé par yat
    On peut aller plus loin que 5 ?
    Non.

    Citation Envoyé par yat
    Moi je n'arrive pas à dépasser le 4 ...
    Normal, ce n'est pas possible
    Le max est bien 4.

    Citation Envoyé par yat
    J'espère qu'il y aura une petite démo à la clé
    Oui, n'aies pas peur. Il y a une très jolie démonstration de ce résultat.

  15. #12
    yat

    Re : énigme solitaire

    Citation Envoyé par matthias
    Normal, ce n'est pas possible
    Le max est bien 4.
    Ah... je pensais qu'Evil.Saien supposait que le max était 5 parce que c'était le maximum qu'il arrivait à atteindre...
    Citation Envoyé par matthias
    Oui, n'aies pas peur. Il y a une très jolie démonstration de ce résultat.
    Alors la.... J'ai pas l'ombre d'un début de raisonnement qui pourrait démontrer un truc pareil. Je suis curieux de voir la solution

  16. Publicité
  17. #13
    martini_bird

    Re : énigme solitaire

    Salut,

    m'est avis qu'il y un invariant bien choisi derrière tout ça, mais lequel?

    Mais bon, je fais peut-être fausse route...

    Cordialement.

  18. #14
    homotopie

    Re : énigme solitaire

    Il n'y a pas de génération spontanée de pions?
    J'oubliais que le pion qui vient de sauter laissait un vide à son ancienne place. D'où guère de difficultés pour "remplir" le plan.

  19. #15
    martini_bird

    Re : énigme solitaire

    Citation Envoyé par homotopie
    J'oubliais que le pion qui vient de sauter laissait un vide à son ancienne place.
    Si ça peut te rassurer, j'ai commis la même erreur au début : ah quand on ne lit pas les énoncés...

  20. #16
    invite986312212
    Invité

    Re : énigme solitaire

    Citation Envoyé par martini_bird
    m'est avis qu'il y un invariant bien choisi derrière tout ça, mais lequel?
    il suffit de trouver une équation algébrique de degré la position extrême du pion et qui doit être résolue "par radicaux", mais je ne vois pas

  21. #17
    Evil.Saien

    Re : énigme solitaire

    Citation Envoyé par Evil.Saien
    Salut,

    Intuitivement, je dirais 5 cases maximum.
    Argh... En fait je suis alle jusqu'a 4, et j'ai eu la flemme de tenter le 5 parce que je me suis dit qu'il fallait trop de manip, j'ai suppose que ca passait !
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  22. #18
    matthias

    Re : énigme solitaire

    Bon, en fait la solution consiste à créer une fonction qui associe une valeur à chaque situation et qui décroisse à chaque coup joué. Si on dispose d'une telle fonction, il est clair qu'à partir d'une situation de valeur A, on ne pourra jamais aboutir à une situation de valeur B > A.

    Jusque là, c'est très théorique.

    Commençons par associer une valeur à chaque emplacement, et on prendra comme fonction la somme des valeurs des emplacements non vides.

    Posons (solution de x²+x=1).

    On associe à l'emplacement (x;y) la valeur , et on a donc notre fonction d'évaluation d'une situation.

    Il ne reste plus qu'à démontrer que la fonction que l'on a créée décroit à chaque coup joué, puis que l'on ne peut pas passer de la situation demi-plan inférieur rempli à une situation où l'on aurait un pion en (0;5).

    Oui je sais, c'est pas super intuitif mais bon, ça passe un peu mieux avec un dessin (que je n'ai pas fait)

  23. Publicité
  24. #19
    Evil.Saien

    Re : énigme solitaire

    Suis-je le seul a n'avoir rien compris ???
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  25. #20
    yat

    Re : énigme solitaire

    Citation Envoyé par Evil.Saien
    Suis-je le seul a n'avoir rien compris ???
    Non, rassure-toi

  26. #21
    matthias

    Re : énigme solitaire

    C'est plus facile à expliquer avec les mains

    Bon, vous avez compris comment on évalue une situation ?
    Imaginons que je n'ai que deux pions, un en (1;2) et un en (0;5), la fonction d'évaluation vaut :



    Ce qu'il faut commencer par montrer, c'est que la fonction d'évaluation ne peut que décroître à chaque coup joué. Ce n'est pas difficile, chaque coup ne modifiant que trois cases contigues.

  27. #22
    matthias

    Re : énigme solitaire

    Bon j'ai fait un petit effort pour que les valeurs affectées à chaque emplacement soient un peu plus claires :



    La valeur 1 est sur l'emplacement (0;5).
    Les valeurs pour y > 5 n'ont pas d'importance car on n'a pas besoin d'évaluer de situation où un pion serait au delà de la 5ème ligne.

    Toutes les séries de trois cases consécutives (en horizontal ou vertical) étant de la forme ou , il est facile de démontrer que la fonction d'évaluation ne peut pas augmenter quand on joue un coup, puisque :







    (car )

    C'est plus clair ?

  28. #23
    Evil.Saien

    Re : énigme solitaire

    Superbe schema explicatif matthias !

    T'as eu bien du courage de le faire !

    Mais a part ca, j'ai toujours du mal a comprendre, sans doute a cause de mes capacites limites, t'en fait pas !
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  29. #24
    matthias

    Re : énigme solitaire

    Citation Envoyé par Evil.Saien
    Mais a part ca, j'ai toujours du mal a comprendre
    Dis moi où tu coinces, ça m'obligera à être plus clair.
    Tu as compris comment on calcule l'évaluation d'une situation ?
    On fait simplement la somme des valeurs associées aux "cases" sur lesquelles il y a un pion.

    Si tu as compris ça, as-tu compris pourquoi la valeur diminue, ou reste stable, à chaque fois que l'on joue un coup ?

  30. Publicité
  31. #25
    yat

    Re : énigme solitaire

    Bon, en ce qui me concerne, maintenant j'ai compris pourquoi on prend la solution de x²+x=1... ( )
    Ce qui me perturbe un peu, c'est que la solution est déjà dans la fonction de départ... En gros, il faut déjà savoir que la hauteur maximale est 5 pour choisir la fonction de sorte que la somme des valeurs des cases sous la ligne soit strictement inférieure à 1...

    Ca n'aurait pas marché en virant ce 5 ? La décroissance reste valable, et il suffit ensuite de calculer la somme des cases sous la ligne et de regarder quelle est la case la plus haute qui ait une valeur inférieure ou égale à cette somme, non ?

  32. #26
    rvz

    Re : énigme solitaire

    Citation Envoyé par matthias
    Il ne reste plus qu'à démontrer que la fonction que l'on a créée décroit à chaque coup joué, puis que l'on ne peut pas passer de la situation demi-plan inférieur rempli à une situation où l'on aurait un pion en (0;5).
    Bonjour,

    Je comprends pas pourquoi ça empêche la configuration x=0, y >=5.
    Y a quelque chose que j'ai du rater
    En tout cas, c'est un très joli problème, et plutot contre-intuitif.

    __
    rvz, qui adore ces petits problèmes apparemment tout simples

  33. #27
    matthias

    Re : énigme solitaire

    Citation Envoyé par yat
    Ce qui me perturbe un peu, c'est que la solution est déjà dans la fonction de départ... En gros, il faut déjà savoir que la hauteur maximale est 5 pour choisir la fonction de sorte que la somme des valeurs des cases sous la ligne soit strictement inférieure à 1...
    Oui, c'est un peu parachuté (doux euphémisme)

    Citation Envoyé par yat
    Ca n'aurait pas marché en virant ce 5 ? La décroissance reste valable, et il suffit ensuite de calculer la somme des cases sous la ligne et de regarder quelle est la case la plus haute qui ait une valeur inférieure ou égale à cette somme, non ?
    Pourquoi pas en effet.

  34. #28
    yat

    Re : énigme solitaire

    Citation Envoyé par rvz
    Je comprends pas pourquoi ça empêche la configuration x=0, y >=5.
    -On a une fonction qui associe une valeur réelle à une situation donnée.
    -On montre facilement que la valeur de cette fonction décroit à chaque fois que l'on joue un coup
    -On constate que la valeur de la fonction est plus grande quand on a juste une bille en (0;5) que quand on a des billes sur toutes les cases d'ordonnée négative ou nulle.

    Donc quand on ne commence la partie avec que des billes sous la ligne, la valeur de la fonction est déjà inférieure à celle qu'elle aurait si on avait une bille sur la cinquième ligne. Or, il est impossible de jouer un coup qui fasse augmenter cette valeur, donc on ne peut pas placer une bille sur la cinquième ligne.

  35. #29
    rvz

    Re : énigme solitaire

    Ah oui !
    Tout s'éclaire. C'est vraiment très très beau.
    Même si je trouve ça beau parce que je n'aurai jamais pu trouver cela seul. Y a quand même des gens qui ont de ces intuitions...

    __
    rvz

  36. #30
    matthias

    Re : énigme solitaire

    Citation Envoyé par rvz
    Bonjour,

    Je comprends pas pourquoi ça empêche la configuration x=0, y >=5.
    Y a quelque chose que j'ai du rater
    En tout cas, c'est un très joli problème, et plutot contre-intuitif.
    En faisant le calcul, tu vois que si ta situation initiale est le demi-plan inférieur rempli, la fonction d'évaluation vaut 1 (moins si le demi-plan n'est pas rempli).
    Si tu as un pion en (0;5) la fonction d'évaluation vaut au moins 1.
    On pourrait dire que ce n'est pas décisif puisque la fonction n'est pas strictement décroissante, mais si on peut atteindre la cinquième ligne, on peut le faire en un nombre fini de coups, donc si on est parti avec le demi-plan rempli, il reste des pions dedans, et donc la valeur finale est strictement supérieure à 1 (ou autre manière de voir, si on peut atteindre la cinquième ligne en un nombre fini de coups, on peut le faire avec une situation initiale où le demi-plan n'est pas rempli).

    [EDIT: désolé, j'ai été un peu lent ]

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Vers solitaire???
    Par jojo86 dans le forum Santé et médecine générale
    Réponses: 8
    Dernier message: 24/11/2012, 14h45
  2. Le taenia ( le ver solitaire )
    Par placebo974 dans le forum Santé et médecine générale
    Réponses: 76
    Dernier message: 03/01/2010, 01h14
  3. [identification]guêpe et abeille solitaire
    Par bonzai dans le forum Identification des espèces animales ou végétales
    Réponses: 3
    Dernier message: 04/07/2007, 00h32
  4. Un Quasar solitaire
    Par Dydo dans le forum Actualités
    Réponses: 2
    Dernier message: 05/01/2006, 10h55
  5. solitaire
    Par sliders_alpha dans le forum [ARCHIVE] Psychologie / Sociologie
    Réponses: 10
    Dernier message: 21/10/2004, 15h16