Une "Freecell" ingagnable ?

nerosson · 03-09-2010 17:40:10

Salut à tous,

J'ai lu (je ne me souviens plus où) qu'on "conjecturait" qu'au jeu de "Freecell", toutes les parties étaient gagnables, mais qu'on n'avait pas pu le prouver.

En dépit de l'immense admiration que j'éprouve pour les brillantes intelligences qui illuminent ce site, je doute moi aussi que ce soit prouvable. Mais ne pourrait-on pas prendre le problème à rebrousse-poil et essayer de concevoir une partie qui soit ingagnable ?

freddy · 03-09-2010 20:57:52

Salut,

en fait, il existerait 2 situations ingagnables. C'est pourquoi on conjecture que presque toutes les parties sont gagnables.

IL reste à trouver les deux situations. A nos méninges ...

nerosson · 04-09-2010 13:41:31

Hé ! Hé ! Mon bon Freddy,

C'est pas "armons-nous et partez !". Prends-toi par la main !

Dès le départ, il y a un os, c'est que dans ce jeu, c'est le logiciel qui crache les parties. Rien n'est prévu pour qu'on puisse disposer soi-même les cartes à sa guise.

Faire des essais à la main avec un vrai jeu de cartes, ça n'est pas une solution bien séduisante.

Ce qui serait bien, c'est que parmi les fondus d'informatique qui pullulent sur ce site comme des morp... (Oh! pardon, je t'avais oublié, Yoshi, modo ferox. je reprends donc :)...parmi tous les fondus d'informatique qui pullulent sur ce site, virgule, il y en ait un qui conçoive un logiciel que même un nul comme moi pourrait télécharger et qui permettrait d'aborder ce problème.

Allez, Yoshi, qu'est-ce que tu attends ?

nerosson · 05-09-2010 16:14:40

Salut à tous,

Premier point : il est bien entendu que je ne suis sûr de rien : je vous présente la première idée qui m'est venue à l'esprit :

Dernière modification par nerosson (07-09-2010 14:50:37)

nerosson · 07-09-2010 13:57:02

Salut à tous,

1° Même si la disposition des cartes ci-dessus a une physionomie bien particulière, elle a une chance sur factorielle 52 de se présenter, c'est à dire la même probabilité que chacune de celles que le logiciel de « Freecell » vous crachera à longueur de journées si vous jouez.

2° Si, comme je le « conjecture », elle est ingagnable, on peut en déduire, par des variations bien choisies, une multitude d'autres qui seront ingagnables elles aussi.

pas-glop · 07-09-2010 17:53:00

Il me semble que ta partie est facilement gagnable :

-Monter le roi de coeur
-Mettre les trèfles pairs et les coeurs impairs sur le roi de carreau, carte par carte...

Ensuite :
-Monter le roi de trèfle
-Mettre les coeur pairs et les trèfles impairs sur le roi de de pic, carte par carte...

Les cartes de coeur et de trèfle sont rangées, les rois sont en haut et les as accessibles en bas des 2 tas formés. On en a terminé avec la moitié des cartes. La partie se termine sans encombre je présume.

nerosson · 08-09-2010 16:20:34

Salut, Pas-glop, et bienvenue sur le site,

Comme il est difficile de se représenter les mouvements et que d'autre part tu ne parlais pas des dames et des valets dans ton explication, j'ai pris un jeu de cartes et j'ai réalisé ton processus matériellement. A ma grande honte, je suis obligé de convenir qu'il fonctionne parfaitement.

Je suis un peu mortifié de ne pas l'avoir vu. J'ai eu de la m... dans les yeux."Pan sur le bec", comme on dit au "Canard enchaîné". J'essaye de m'inventer des excuses en me disant que mon problème a attendu deux jours avant que la solution y soit apportée. Pas très convaincant....

Maintenant la balle est dans ton camp : à toi de trouver une partie ingagnable : pour mon compte, je me sens un peu échaudé....

Cordialement.

pas-glop · 08-09-2010 18:37:00

merci pour ton message de bienvenue nerosson, et bonjour à tous.
(j'avais oublié le salut parce que j'avais posté un message juste avant sur un autre post, "définition globale d'une fonction")

J'ai envisagé une autre partie qui me semble compliquée à gagner. Pour la faire, j'ai utilisé 2 idées :
- Si les AS sont bien planqués, le joueur n'y aura pas accès. Donc il ne gagnera pas.
- Comme les cartes sont empilées rouges sur noir, j'ai décidé de séparer les 2 couleurs.

Vous pouvez mettre les cartes restantes dans les cases vides dans l'ordre qui vous plaira.

[tex]\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
AS - noir & AS - noir & AS - rouge & AS - rouge &&&&\\
\hline
&&&& 7 - rouge & 7 - rouge & 6 - rouge & 6 - rouge \\
\hline
8 - rouge & 8 - rouge & 9 - rouge & 9 - rouge & V - rouge & V - rouge & 10 - rouge & 10 - rouge \\
\hline
R - rouge & R - rouge & D - rouge & D - rouge & D - noir & D - noir & R - noir & R - noir \\
\hline
8 - noir & 8 - noir & 9 - noir & 9 - noir & 10 - noir & 10 - noir & V - noir & V - noir \\
\hline
6 - noir & 6 - noir & 7 - noir & 7 - noir & 4 - noir & 4 - noir & 5 - noir & 5 - noir \\
\hline
2 - noir & 2 - noir & 3 - noir & 3 - noir &&&&\\
\hline
\end{array}[/tex]

pas-glop · 08-09-2010 18:45:05

edit : après quelques essais, j'arrive à faire quelques manipulations sur les 4 dernières colonnes : des suites rouge - noir de 2 chiffres... On peut imaginer pas mal de variantes de cette partie pour générer des parties ingagnables. Mais elles sont sacrément bien ordonnées, et c'est ce qui me chagrine. L'idéal serait une partie qui semble aléatoire mais est insoluble.

nerosson · 09-09-2010 15:54:38

Salut, Pas-Glop,

Concernant tes deux idées de base, je remarque que :
1° la première vient automatiquement à l'idée : moi aussi, mes quatre as étaient, comme les tiens, soigneusement planqués, ce qui ne t'a pas empêché d'aller me les dénicher en deux coups de cuillère à pot,
2° concernant la séparation des couleurs, il ne faut pas perdre de vue qu'on peut monter jusqu'à quatre cartes successives dans ce que j'appelle les "cases de transit" (en haut et à gauche), ce qui permet éventuellement d'aller chercher loin une carte dont on a besoin.

Par ailleurs, je ne comprends pas bien ton tableau : il y a des cases vides dans le haut.

D'autre part, travailler avec un vrai jeu de cartes est assez rebutant.

Si l'on en croit Freddy (il faut toujours croire Freddy...), il n'y aurait que deux parties ingagnables, ce qui semblerait indiquer que cette affirmation serait le résultat d'une déduction. J'en viens à penser que la réponse au problème ne peut pas être acquise par des essais plus ou moins tâtonnants, mais par le raisonnement. Mais il y a une telle variété dans la manière de faire face à un dispositif donné....

Je constate avec regret que tous les éblouissants logiciens qui pullulent sur ce site "restent tous dans un profond sommeil", comme dit la chanson.

freddy · 09-09-2010 17:52:32

Salut nerosson !

toujours me faire confiance, oui, surtout quand je puise ma science dans la Toile :

http://fr.wikipedia.org/wiki/FreeCell

C'est 8 parties qui seraient ingagnables ...

Donc ton sujet reviendrait à demander si on peut construire une arborescence générant des parties ingagnables. De mon humble point de vue, c'est du ressort de la théorie des graphes, mais vraiment c'est purement le début d'une ombre d'un commencement d'une intuition.

Bien à toi,

Freddy

nerosson · 10-09-2010 16:59:29

Salut à tous,

merci, Freddy, pour cette référence.

Pour ceux que cela pourrait intéresser je cite les numéros des huit parties ingagnables :

« Huit parties sont impossibles : no 11982, 146692, 186216, 455889, 495505, 512118, 517776 et 781948. »

Il faut remarquer que ces huit parties appartiennent au million de parties proposées par WINDOWS-FREECELL. On peut donc « conjecturer » que si on prenait en considération les « factorielle 52 » parties mathématiquement possibles, on en trouverait davantage.

J'ai demandé à la calculatrice de mon ordinateur ce que donnait « factorielle 52 », mais elle m'a envoyé sur les roses.

A noter que la rubrique « discussion » du site cité par Freddy renvoie à d'autres sites traitant de cette question.

freddy · 10-09-2010 17:19:48

'lut nesorron,

si tu approximes factorielle 52 par la formule de Stirling, soit [tex]\sqrt{2\pi\times 52}\left(\frac{52}{e}\right)^{52}[/tex], tu as un nombre de l'ordre de [tex]5,6\times 10^{67}[/tex].

T'es pas encore couché !!!

nerosson · 10-09-2010 18:06:32

Salut,

tu vas au devant de mes désirs : j'étais justement tracassé (comme tu sais, mes compétences ne vont pas loin, cette discussion le prouve) par le fait de ne pas savoir combien de chiffres il pouvait y avoir dans factorielle 52. J'ai erré sur la toile sans trouver de réponse.

Il semble que la calculatrice (32 chiffres) de mon ordinateur demande grâce au delà de factorielle 29.

thadrien · 10-09-2010 18:34:02

Salut,

Début de réponse ici : http://fr.wikipedia.org/wiki/Formule_de_Stirling

yoshi · 10-09-2010 19:06:49

Salut,

nerosson a écrit :

j'étais justement tracassé (comme tu sais, mes compétences ne vont pas loin, cette discussion le prouve) par le fait de ne pas savoir combien de chiffres il pouvait y avoir dans factorielle 52. J'ai erré sur la toile sans trouver de réponse.

Bin, ô vénérable ancien, fallait demander, tout simplement...
Il y en a 68 !

Regarde, un pt'it coup de Python :

****Valeur de 52 ! ****
80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000

pour une durée de calcul inférieure à 1/1000e s...

Au passage, une approximation de ce nombre est [tex]8 \times 10^{67}[/tex]
Pas mauvais Stirling...

@+

freddy · 10-09-2010 22:37:56

Re,

j'ai fait le calcul en ne retenant que le facteur 19 en lieu et place de 52/e ... et 18 pour la racine de 2Pi*52 et on voit de combien on se trompe à l'arrivée : 30 % d'erreur ! Gloups, de quoi "tuer" une boîte ou faire atterrir une navette spatiale sur le Mont Blanc ...

Remarque : [tex]\frac{52!}{\sqrt{2\times \pi \times 52}\times {\left(\frac{52}{e}\right)}^{52}}=1,0016[/tex]

Étonnant, non ?

Dernière modification par freddy (10-09-2010 22:44:37)

yoshi · 11-09-2010 11:01:57

Re,

Euh... De quoi dois-je m'étonner ? De la précision de l'approximation de Stirling ?

Et puis pour faire bien, un nombre bien rond :

**** Valeur de 100 ! ****

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

158 chiffres obtenus en un temps toujours pas mesurable...
Ce qui ne m'étonne pas, puisque karlun ayant initié l'affaire, j'ai suivi et j'obtiens le nombre d'or avec 20 000 décimales en moins de 3 s, alors 168 chiffres, bagatelle !...

@+

karlun · 11-09-2010 13:01:26

Salut,

Pour vous encourager à vous passer de votre calculette et passer à Python, voici le (mini) programme qui permet d'arriver au résultat.
Sans doute celui de Yoshi sera encore plus mini... ;-)

def d():

    j=1

    for i in xrange(52,1,-1):

        j=i*j

    print j

mini A+-*/

P.S. As-tu constaté, comme moi, cher Yoshi, que le temps d'exécution d'un même programme peut notablement varier? Pour quelle raison? Serait-ce dû au travail de l'ordinateur en parallèle (internet ou autre par ex.)?

nerosson · 11-09-2010 18:31:29

Salut à tous,

Mon cher Karlun, je crois que tu te fais des illusions sur mes capacités mathématiques. Tes savantes formules sont du grec pour moi. Remarque, ton erreur est bien excusable : Qu'est-ce qu'un primitif comme moi fout à traîner sur un site comme celui-là. Je ne suis allé que jusqu'à mathélem il y à très très longtemps, c'est dire que mon parcours sur le chemin des maths a été bref et par surcroît, j'ai tout oublié.

En outre, j'ai l'impression que les maths ont beaucoup évolué depuis les années 30/40. C'est peut être une impression fausse qui tient à ce que je suis resté au rez-de-chaussée pendant que vous autre avez élu domicile dans les étages. Alors qu'est-ce que je fous là : peut être une sorte de fascination et puis aussi, de temps en temps, je tombe sur une discussion où l'arithmétique a encore sa place et où je peux mettre mon grain de sel. C'est le sujet d'une controverse prolongée avec l'ami Yoshi : il prétend que je dénigre tout ce qui n'est pas arithmétique dans les maths. Ca n'est pas ça, mais :

1° J'ai oublié tout le reste,

2° S'il a raison de dire qu'avec l'arithmétique on ne va pas loin, elle a par contre un privilège sur les autres disciplines : c'est la seule où le raisonnement est à l'état pur, alors que les autres sont un mélange de raisonnement et des formules toutes faites, qui ont été démontrées une fois pour toutes, j'en conviens. Messieurs les matheux, vous êtes comme des alpinistes qui escaladent la falaise en plantant des pitons : ils ne font pas de la varappe, ils grimpent un escalier (la volée de bois vert que je vais me ramasser par Freddy : j'en frémis d'avance). Le pauvre Nérosson, il reste comme un bêta au pied de la paroi : il n'a pas de pitons.

Il y a autre chose qu'il faut bien que je te dise, mon cher Karlun : dans ta dernière intervention, j'ai vu un « vous » qui paraissait bien s'adresser à moi, ce qui m'a foutu la chair de poule. Je « conjecture » qu'au hasard de tes lectures dans ce site, tu as du tomber sur un allusion à mon âge. C'est bienfait pour moi, j'avais qu'à fermer ma gueule. Tu en as conclu que j'avais droit à des égards particuliers, mais je vous le dis à tous : JE N'EN VEUX PAS. Tu peux utiliser à mon égard tous les vocatifs que tu veux : « grand père », "vieux fossile », « vieux débris », je te jure que je ne me formaliserai absolument pas. Mais de de grâce, pas de « vous ». Ca me fait l'effet d'une piqûre d'épingle.

Il y a une autre remarque que je me suis faite à plusieurs reprises : ce brave Nérosson lance timidement une remarque toute simple, dont il se demande même si elle mérite de figurer là, et voilà que les acrobates des maths s'en emparent, multiplient les interventions, ouvrent leurs boites à formules comme une boîte de Pandore devant le pauvre Nérosson éberlué, dépassé, qui contemple avec stupeur l'arbre géant auquel a donné naissance la petite pousse qu'il avait repiquée avec la crainte que l'un de vous pose dessus un pied négligent.

Au fait, pourquoi je vous raconte tout ça ? Vous êtes allés jusqu'au bout ?

karlun · 11-09-2010 19:20:40

Très...,

Le vous employé n'est adressé qu'à tous; les tous-ceux qui lisent nos élucubrations (à nous tous).

Cher Nerosson, j'ai déjà annoncé que je ne possédais que des plus, des moins, des fois et des divisés et quelques autres broutilles dans ma besace.

Mon niveau math ne doit pas être beaucoup plus élevé que le tien et comme tu peux le voir les sujets qui m'animent ne requièrent que peu de connaissances.
Souviens-toi que mon premier post traitait du « plus long chemin entre deux points » auquel tu as participé et pas plus qu'un peu (il n'a pas été fort pris au sérieux alors qu'il traitait de série mais je compte bien en remettre une couche un jour peut-être).

Le sujet « bizarre » que tu as amorcé et que j'ai poursuivi, se basait sur la logique arithmétique confrontée au domaine de définition. J'ai également souffert les foudres (légitimes) de Yoshi. Mais on était (et maintenant également) au café, non?
J'ai pu aussi déclarer à notre Modo Ferox de service que la logique ne souffrait pas des plombes passées à essayer de la cerner. Je veux dire que je te rejoins sur le terrain de l'arithmétique; mais si je peux proposer un petit (ou un plus grand) programme Python c'est que ce n'est pas compliqué du tout. J'ai commencé il y a peu et 80 pages d'un bouquin d'aide très très abordable (en ligne ) suffit à se lancer.
Programmer (à mon stade) ce n'est qu'appliquer un chemin logique comme 1+1=2 (si 1+1=3 alors on reprend et on cherche l'erreur qui est nôtre).

Il n'y avait, dans mon message, qu'encouragement à tous à s'y mettre.

Que vive la logique.

...,peu d'A+-*/

yoshi · 11-09-2010 19:49:03

Bonchoir Madââme, bonchoir Mademoiselle, bonchoir Monsieur,

Plus mini ?
Pas vraiment, mais c'est la même technique évidemment...
Autre conception.

#!/usr/bin/env python

# -*- coding: cp1252 -*-

from time import time

def factorielle(x,fin):

    for i in xrange(2,fin):

        x*=i

    return x

####  nb est le nombre dont on veut calculer la factorielle

nb = 1000

####

tp_d=time()   

x = factorielle(1,nb+1)

temps=time()-tp_d

print

print "**** Valeur de",str(nb),"! ****"

print x

print"\n",temps,"s"

Pour 1000 ! l'affichage démarre toujours instantanément...

Cher nerosson, un langage de programmation, c'est comme un patois qui permet de causer avec l'ordinateur et lui faire faire (en principe) ce que tu veux. Il a sa grammaire et son vocabulaire et ne pardonne ni les fautes du 1er type, ni celles du 2e type...
N'importe qui d'un peu logique (et donc un féru d'arithmétique) peut s'y mettre, à condition
- de ne pas vouloir avaler la Terre entière tout de suite,
- de bien se mettre dans le crâne que bien souvent (90 % des cas au moins) un programme ne marche pas du 1er coup...

@+

freddy · 12-09-2010 19:13:19

Hello tutti !

Pour répondre à mon ami nerosson, voici : http://fr.wikipedia.org/wiki/Escalade

La varappe n'a jamais été l'escalade sans protection. Par contre, quand on grimpe des blocs de rochers de moins de 5 mètres (comme à 'Bleau ou ailleurs - il y a un très joli spot de blocs en Savoie, à côté de Peisey-Valandry, où Edlinger lui même à ouvert une 6c un jour de visite ...), on grimpe "en solo", avec les copains en protection en dessous.

Voilà mon ami, qui me donne une belle image : quand on raisonne en maths, on fait comme pour gravir un sommet, on se sert des points d'assurage bien solides pour passer de difficultés en difficultés.

Quand on ouvre une voie (on crée un nouveau théorème, on développe une nouvelle branche des maths), on progresse lentement, mais sûrement.

Et il en est de même en arithmétique comme en analyse, en topologie différentielle, en géométrie algébrique, und so weiter, meiner Kamerad !!!

Bises de Bâle

Dernière modification par freddy (12-09-2010 19:35:18)

nerosson · 13-09-2010 15:19:59

Salut à tous,

Freddy, ce que tu dis des maths n'est pas contradictoire avec le commentaire que j'en ai fait.

Quant à la varappe : il suffit que je monte sur une chaise pour avoir le vertige. J'ai essayé une fois, quand j'étais ado, avec un copain : le pauvre ! Il a failli y laisser la vie ! (après relecture, je précise : essayé de faire de la varappe, pas de monter sur une chaise !)

Post scriptum qui n'a rien à voir (comme dirait Delfeil de Ton) : le vertige, ça n'est pas seulement une trouille. C'est plus compliqué que ça : quand, à la télévision, je vois un mec accroché à une paroi vertigineuse, je suis dans mon fauteuil, je sais que le gars ne s'est pas cassé la gueule, et pourtant j'ai les jambes en flanelle !

Dernière modification par nerosson (13-09-2010 15:26:22)

Forum de mathématiques - Bibm@th.net

#1 03-09-2010 17:40:10

Une "Freecell" ingagnable ?

#2 03-09-2010 20:57:52

Re : Une "Freecell" ingagnable ?

#3 04-09-2010 13:41:31

Re : Une "Freecell" ingagnable ?

#4 05-09-2010 16:14:40

Re : Une "Freecell" ingagnable ?

#5 07-09-2010 13:57:02

Re : Une "Freecell" ingagnable ?

#6 07-09-2010 17:53:00

Re : Une "Freecell" ingagnable ?

#7 08-09-2010 16:20:34

Re : Une "Freecell" ingagnable ?

#8 08-09-2010 18:37:00

Re : Une "Freecell" ingagnable ?

#9 08-09-2010 18:45:05

Re : Une "Freecell" ingagnable ?

#10 09-09-2010 15:54:38

Re : Une "Freecell" ingagnable ?

#11 09-09-2010 17:52:32

Re : Une "Freecell" ingagnable ?

#12 10-09-2010 16:59:29

Re : Une "Freecell" ingagnable ?

#13 10-09-2010 17:19:48

Re : Une "Freecell" ingagnable ?

#14 10-09-2010 18:06:32

Re : Une "Freecell" ingagnable ?

#15 10-09-2010 18:34:02

Re : Une "Freecell" ingagnable ?

#16 10-09-2010 19:06:49

Re : Une "Freecell" ingagnable ?

#17 10-09-2010 22:37:56

Re : Une "Freecell" ingagnable ?

#18 11-09-2010 11:01:57

Re : Une "Freecell" ingagnable ?

#19 11-09-2010 13:01:26

Re : Une "Freecell" ingagnable ?

#20 11-09-2010 18:31:29

Re : Une "Freecell" ingagnable ?

#21 11-09-2010 19:20:40

Re : Une "Freecell" ingagnable ?

#22 11-09-2010 19:49:03

Re : Une "Freecell" ingagnable ?

#23 12-09-2010 19:13:19

Re : Une "Freecell" ingagnable ?

#24 13-09-2010 15:19:59

Re : Une "Freecell" ingagnable ?

Pied de page des forums