par simple intuition je n'ai pas trouvé de méthode pour mathématiser le problème

Seb

Je répondrai , car je pense que pour N=6k+5 (k entier), il est insoluble, car équivalent à la première disposition ci-dessous:
X X X    - - -    - - -    - - -    X X X     X X X
- - -     - - -    - - -    X X X    X X X     X X X
X - -    X - -   - X X    - X X     - X X     X - -
Les autres dispositions sont celles équivalentes pour N=6k, 6k+1, 6k+2, 6k+3, et 6k+4, qui sont toutes solubles, tout au moins pour k>0

Je considère un solitaire de 3 lignes et N colonnes.
J'ai pris la notation suivante :
Un coup est codifié (x,y,D), avec (x,y) coordonnées du trou à combler et D, la direction du pion « remplissant », pouvant prendre les valeurs d(droite), g(gauche), h(haut) ou b(bas).

On remarque tout d'abord que on peut « supprimer » une tranche de 3 colonnes pour revenir à la position initiale. C'est-à-dire que si on réussit à résoudre le solitaire avec n colonnes, on arrivera le résoudre avec n+(3*p) (p ).

Cette méthode est, le trou initial étant en (1,1).
1-1-d
3-1-h
3-3-g
1-3-b
2-3-d
3-3-g
2-1-d
2-3-b
4-3-g.

Je n'ai pas trouvé de solution pour 2 colonnes, 3 colonnes et 5 colonnes.
Par contre, il y en a pour 6 colonnes, 7 colonnes et 8 colonnes, donc d'après ce qui précède , je peux toujours résoudre un solitaire strictement supérieur à 5 colonnes.

Une  solution pour 6 est :
11d - 21h - 22d - 32g - 31d - 41g - 23d - 33g- 31h - 42d - 21d - 31g - 43d - 41h - 51g - 41d.
Une solution pour 7 est :
11d - 21h - 22d - 32g - 31g - 21d - 23d - 33g - 31h - 41d - 51h - 52d - 61g - 51d - 53d - 41g - 61g - 51h - 71g.
Une solution pour 8 est :
11d - 21h - 22d - 32g - 31d - 41g - 23d - 33g- 31h - 42d - 51d- 21d - 31g - 43d - 62d - 41h - 63d - 61h - 71g - 61d - 51g - 71g.

La plus grande valeur de N pour laquelle la résolution du solitaire à 3 lignes et N colonnes est impossible, est donc N=5.

rép :
les cas impossibles sont N=3 et N=2+3k

Bonjour,

Réponse : infini : au moins les N=3k+1 sont possibles (peut-être y en a-t-il d'autres ?)

Méthode : récurrence sur N=3k+1

Si on s'en tient à l'énoncé de ne pouvoir exploiter que 3xN cases (et pas plus, auquel cas c'est toujours possible), j'ai essayé les premières valeurs de N.

J'ai constaté que pour N=1, c'était possible alors que pour N=2 et N=3 les différents essais n'aboutissaient pas.

Pour N=4, assez rapidement, en tentant de ramener les pionts isolés vers ceux groupés, on parvient à montrer qu'il est possible d'aboutir.

Comme le nombre de cas était assez conséquent pour N=5 et qu'il semblait ne pas aboutir, j'ai arrêté mes essais pour tenter de découvrir une logique : N=1 et N=4 fonctionnant, s'il y avait une suite du type N=3k+1, je me devais de vérifier si N=7 aboutissait.

Effectivement, la configuration N=7 permet de se raccrocher au cas N=4 démontré.
Une relation de type récurrence permet d'affirmer que les cas N=3k+1, au moins, sont de ceux qui fournissent un seul pion en position finale.

Je n'ai cependant pas pu démontrer, les compétences me manquent, que c'étaient les seuls cas possibles : biondo ou piepalm vont certainement s'en charger

J'attache une image d'excel montrant les cas N=1,2,3,4 et 7 qui prouve N=3k+1 => N'=3(k+1)+1.

Merci pour cette énigme qui, si elle avait demandé une démonstration en règle sur les valeurs de N possibles, aurait récolté plus de
Par ailleurs, je crains que d'aucuns rajoutent des cases vides au delà des 3xN ce qui permet, dans tous le cas, d'aboutir; ce risque de mauvaise interprétation de l'énoncé pourra être à l'origine de nombreux poissons.

Philoux

bonsoir
c'est compliqué comme chalenge... mai si n=1, cela fai un carré de trois sur trois.Et il ne restera jamais qu'un pion!

je dirais par hasard

sans s'appuyer sur aucun raisonnement:

la réponse n'est pas

Bonjour
Je pense que cette valeur n'existe pas

donc infini

Bon, j'ai encore posté trop vite: encore un poisson!
La bonne réponse doit être 5.
Il est facile de voir que le problème n'est pas soluble pour N=2, 3 ou 5
On peut faire disparaître une rangée de 3, s'il y a un pion au dessus et
Pour N=4 on peut faire au premier coup
X X X        X X X
X X X        X X X
X X X        X X X
- X X        X - -
On peut ensuite avoir les enchainements de coups suivants:
X X X        X X X        X X X        X X -        X - -        - - -
X X -        X X -        X X X        X X -        X - -        - - -
X X -        - - X        - - -         - - X        - X X        X X X
X - X        X - X        X - -         X - -        X - -        X - -
ou
X X X       X X X       X X X       X X -       X X -       - - X        - - -       - - -       X - -
X X -       - - X       X - X       X - -       X - X        X - X       X - -       X - -       - - -
X X -       X X -       - X -       - X X       - X -        - X -       - X X       X - -       - - -
X - X       X - X       - - X       - - X       - - -        - - -        - - -       - - -       - - -
Le deuxième enchaînement permet de déduire que N=7 est soluble puisque l'on se retrouve alors dans la même situation qu'après le premier coup de N=4
Tandis que si l'on combine le premier avec l'enchainement suivant:
X X X         X X -         X - -         - - -
X X X         X X -         X - -         - - -
- - -         - - X         - X X         X X X
on voit que l'on peut ramener les cas N=4+2p  et N=7+2p à une situation de p lignes de 3 pions séparées par une ligne vide (on a illustré ci-dessous le cas p=2) qui est évidemment soluble
- - -       - - -         X - -        X - -        - - -         - - -        - - -
X X X       X X X        - X X        X - -        - - -         - - -        X - -
- - -       X - -        - - -         - - -        X - -         X - -        - - -
X X X       - X X        - X X        - X X         - X X         X - -        - - -
X - -       - - -         - - -        - - -         - - -         - - -        - - -
Donc pour N supérieur ou égal à 6 le problème est soluble...

Merci à tous de votre participation à cette énigme, la bonne réponse était N = 5.
Bravo à nofutur2 qui a trouvé la bonne réponse mais aussi aux autres qui ont tout de même tenté leur chance !

Ah que j'ai bien fait de ne pas répondre... j'aurais dit 7, et j'aurais récolté un
Je laisse volontiers la 1e place à Nofutur2, qui est bien plus fort que moi

Très jolie démonstration de Nofutur2.

Merci philoux pour les compétences que tu m'attribues, mais celà ne m'a pas empéché de me planter à ma première réponse (et comme c'est celle-là qui compte...)
Une explication sur cette réponse: pour tenter d'aller vite, je me suis fié à de vieux souvenirs, selon lesquels un problème de solitaire pouvait se ramener à un problème équivalent en ramenant tous les pions dans un carré 3x3 en les faisant glisser de 3 cases (en vertu de l'équivalence X - - -, - X X -, - - - X) - il peut alors y avoir plusieurs pions par case - puis en annulant tout nombre pair de pions.
Il semblerait, sur cet exemple, que cette règle, dite règle de trois, ne s'applique que pour un solitaire infini, ou tout au moins où l'on peut négliger les effets de bord... Je ne sais pas si quelqu'un a des lumières là dessus...

Merci piepalm.

Pour ma part, je m'étais arrêté à la récurrence n=3k+1 sans imaginer, tout content de l'avoir trouvé, qu'une récurrence équivalente pouvait s'envisager pour les autres cas.

Au moins, j'en ai trouvé une et le n'a que peu d'importante car j'adhère complètement à la maxime du baron, reprise fréquemment par PolytechMars et son chat : "...l'important c'est de participer...".

et j'en profite pour féliciter Nofutur2 qui confirme son niveau à la première place.

Philoux

Moi je félicite les courageux qui ont répondu. Cette énigme m'a fait découvrir que le solitaire a inspiré des quantités de chercheurs dans le monde, et j'ai trouvé des sites passionnants sur le web anglo-saxon. Il y a des thèses complètes là dessus.
Mais aussi des gens qui avancent n'importe quoi, j'ai cru comprendre sur un site pourtant sérieux que la réponse était 7 (le premier faisable annoncé à 8) Je n'ai pas posté la réponse, car je n'ai pas su la vérifier avec mon solitaire... j'ai bien fait.
Je n'ai jamais été douée en solitaire, car normalement j'aurais dû arriver à finir celui de 3*8

Merci, merci !! N'en jetez plus.
A vrai dire, je ne suis très fier de ma réponse qui est plus "expérimentale", que déductive..
Ca m'a pris du temps pour trouver les solutions pour N = 6, 7 et 8 et j'ai failli laiser tomber à plusieurs reprises.
Mais peut-on résoudre ce problème sans s'attabler devant un jeu de solitaire ??


NF2

Merci bornéo, mais le courage n'a que peu à voir avec l'envie de participer...

A moins de viser le 0 défaut en scrutant toutes les bases de données possibles sur le net, ces énigmes ne sont là, à mon sens, que pour nous divertir...

Pour ma part, c'est dans cet esprit que j'y participe; à telle enseigne, que lorsque je connais l'énigme pour l'avoir déjà cherchée ou déjà vue résolue, je préfère ne pas participer car il n'y a plus de charme (à vraincre sans péril, ...)

En revanche, je me régale des résolutions sidérantes de certains membres (je ne les reciterai pas pour ne pas les faire rougir ), qui mettent en évidence des différences de niveau conséquentes.

Ce n'est que mon avis ...

Philoux

Bonjour Philoux. Le solitaire est le genre d'énigme pour laquelle j'ai tout de suite fait une recherche sur le net, pas forcément dans l'idée de trouver la réponse, mais pour comprendre ce qui était demandé. Et de fil en aiguille, j'ai trouvé des sites de chercheurs américains absolument fabuleux, avec des pages et des pages de calculs mystérieux et fascinants. Je cherchais déjà à comprendre comment ça marche, car je n'ai jamais réussi à finir le solitaire classique. Bref, même sans trouver la réponse, ça m'a appris beaucoup.

Sans internet, je n'y arriverais jamais, car à part Thalès et Pythagore, je ne connais aucune formule. Donc quand on a besoin de retouver les formules des suites géométriques, les arrangements et les combinaisons ou les modulos, internet est drôlement pratique. Car retrouver la forme canonique ou les deux racines du polynôme du second degré avec la formule ax²+ bx + c est à ma portée, mais au-delà, je cale.

Voilà quelques adresses pour le solitaire...

Oups, je me demande si j'ai bien compris la fonction url... too bad.

Je n'ai rien contre les sites américains (quoique...) mais je me permets de vous indiquer que sur le site de la BNF (gallica.bnf.fr) il y a, en libre téléchargement, les Récréations Mathématiques de Lucas (Édouard, pas George) dont un chapitre est consacré au solitaire au milieu de nombreux autres problèmes classiques...

Merci Piepalm, j'y cours. Je ne connaissais que gutenberg.org pour les livres à télécharger gratuitement, mais c'est surtout en anglais.