Basket à New-York — Les-mathematiques.net The most powerful custom community solution in the world

Basket à New-York

Modifié (29 Jan) dans Combinatoire et Graphes
Bonjour, j'ai un petit jeu dont je voudrais si possible connaître une solution. 
On dispose de 3 paniers de basket : 1 panier pouvant contenir au maximum 2 ballons, 2 paniers pouvant contenir au maximum 3 ballons. On dispose de 5 ballons. Les 5 ballons sont disposés dans les paniers librement : cela donne une configuration (les ballons ne peuvent pas sortir par le bas des paniers et on ne peut pas insérer ni sortir un ballon par le bas). Le but du jeu est de trouver le nombre minimal de déplacements de ballons pour passer d'une configuration des ballons à l'autre...
Bien sur, cela dépend des configurations...
Mais quel algorithme appliquer pour connaître ce nombre ?
Un dénombrement montre que le nombre de configurations est : N=8*7=56. Il y a donc C=56*55=3080 couples de configurations différentes ça fait un peu beaucoup. 
Je pense qu'il faut intégrer dans une stratégie de résolution le fait de commencer à placer les ballons en bas de chaque panier. Dénombrer ça en fonction des configurations et après faire de même avec les 2emes ballons des 2 gros paniers...
Qu'en pensez-vous ?
Merci d'avance de vos réponses.

Réponses

  • SocSoc
    Modifié (30 Jan)
    Tous les ballons sont dans les paniers?
    Les ballons sont indifférenciés?
    Les paniers contenant 3 ballons sont différenciés?
    Si tel est le cas, je trouve juste 7 9 configurations différentes et pas 58 (simplement on regardant où sont les 3 espaces libres, cela va vite).
  • Modifié (29 Jan)
    Bonjour Soc, merci pour votre réponse. Tous les ballons sont dans les paniers. Les ballons sont différenciés par des numéros : 1,2,3,4,5. Les paniers contenant 3 ballons sont différenciés : un à droite et un à gauche. Du coup je ne comprends pas votre calcul. 
  • Modifié (29 Jan)
    Le 56  que tu trouves, tu peux l'expliquer ? 
    Quand les gens auront compris ton 56, ils pourront peut-être comprendre ton 3080, puis comprendre ce que tu veux faire.
  • SocSoc
    Modifié (29 Jan)
    8 places dans les paniers, 5 ballons, donc 3 emplacements vides. Je cherche à répartir ces 3 emplacements vides.
    Si 2 vides dans le panier à 2, il en reste 1 pour les 2 autres: 2 cas. (1;0) et (0;1)
    Si 1 vide dans le panier à 2, il en reste 2 pour les 2 autres: 3 cas (2;0) (1;1) et 0;2)
    Si 0 vide dans le panier à 2, il en reste 3 pour les 2 autres: 4 cas: (3;0) (2;1) (1;2) et (0;3)
    Au total 9 cas (et non pas 7 comme je disais).

    Si on commence à différencier en fonction des ballons, et éventuellement en fonction de l'ordre dans lequel ils sont empilés il y a beaucoup plus de cas.
  • Modifié (29 Jan)
    [Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
    $56=\binom{8}{5}$ et $3080=\binom{56}{2}\times 2$
  • Modifié (29 Jan)
    Je pense que tout le monde avait remarqué que $56 = \binom{8}{5}$

    La question était : Pourquoi le nombre de dispositions serait $\binom{8}{5}$ ?
    Tu as 8 emplacements, mais mettre un ballon dans le 1er emplacement du panier 1, et un autre au 3ème emplacement, et aucun au 2ème emplacement, c'est possible ?

    S'il y avait 8 paniers avec un ballon maximum par panier, tu aurais aussi 56 ?
    Et s'il y avait 2 paniers, avec 7 ballons maximum dans le premier et 1 ballon maximum dans le 2ème , tu aurais aussi 56 ?
    Mais avec 2 paniers, avec 8 ballons maximum dans le premier et 1 ballon maximum dans le 2ème , tu aurais 72 ?
  • Modifié (30 Jan)
    @lourrran mes calculs sont faux. Il y a en réalité plus de configurations possibles. Les 5 ballons doivent être dans les paniers: c'est ce que j'appelle une configuration des ballons. Amis matheux, la physique ne nous autorise pas à avoir un emplacement vide au milieu d'un panier, si on insere un ballon dans un panier, il va dans l'emplacement disponible le plus bas du panier. 

    Un exemple sera plus parlant.
    b=ballon suivi du numéro du ballon
    Panier 1: (b4,b2,b3)
    Ici je veux dire que le ballon 4 est à l'emplacement le plus bas du panier 1 suivi du ballon 2 à l'emplacement du milieu puis du ballon 3 à l'emplacement le plus haut.
    Panier 2 (ne peut contenir que 2 ballons): (b1,rien)
    Le ballon 1 est à l'emplacement le plus bas, et il n'y a rien à l'emplacement du haut.
    Panier 3: (b5,rien,rien)
    L'emplacement du bas contient le ballon 5 et rien au dessus.

    A présent on note P=panier
    On veut savoir combien de déplacements au minimum de ballons pour obtenir une autre configuration.
    Exemple:
    On veut obtenir la configuration:
    P1:(b4,b2,b3)
    P2:(rien,rien)
    P3:(b5,b1,rien)
    Solution: il suffit de prendre le ballon 1 du panier 2 et de le mettre dans le panier 3. Le nombre de déplacements de ballons minimum est donc 1. 
  • Si tu différencies effectivement les ballons et l'ordre dans lequel ils sont empilés alors le calcul n'est pas trop fastidieux et donne:
    nombre de cas possible =  9 x factorielle (5)  = 9 x 120 =1080.
  • @Soc oui merci j'ai trouvé pareil en me servant de votre idée de dénombrer les vides.
    Quelles stratégies mettre en place pour déplacer le moins de ballons possibles d'une configuration à l'autre?
  • Je suis sûr que je n'arriverai pas à répondre à ta question, par contre je peux essayer de mieux la comprendre:

    Tu veux trouver un majorant du nombre minimum de coups? Le meilleur majorant?
    Tu veux pour chaque position trouver le minimum de coups?
    Tu veux un algorithme pour trouver comment passer d'une configuration à l'autre?

    Je pense par contre que la réponse va être compliquée dans tous les cas. Peut-être que des spécialistes du Rubik's cube peuvent t'aider à avancer :)
  • Modifié (30 Jan)
    @Soc ce que j'attends est un mélange de ta 2ème et 3ème questions: je voudrais pour un couple de configurations données, un algorithme ou une formule qui me permette de trouver le nombre minimal de ballons à déplacer pour passer de la configuration 1 à la configuration 2.
    Merci pour ta réponse.
  • Je pense que epiKx cherche pour chaque couple (position de départ / position cible) à choisir parmi les 1080*1079 couples, quel est le plus court chemin.
    Donc 1080*1079 exercices.  Ou 2 fois moins, parce que trouver le plus court chemin de A vers B revient à trouver le plus court chemin de B vers A.

    Il y aurait un autre exercice ambitieux : partant d'une situation quelconque, quel est le plus court chemin qui passe par les 1080 positions, et qui revient à la situation de départ.  Le choix de la situation de départ est donc sans impact sur la solution.

  • @lourrran oui tu as tout compris. ;)
    Je cherche des formules, des stratégies ou des algorithmes qui permettent de faire ça...
  • Alors, il te faut construire la matrice d'adjacence, puis appliquer un algo du type Dijkstra ou tous ceux que tu pourras trouver sur cette page : 
    https://fr.wikipedia.org/wiki/Problème_de_plus_court_chemin 
  • Pour l'algorithme, ok. Mais il n'y aurait pas plus simple parce que l'idée c'est quand même de résoudre le truc de tête si possible... Merci quand même! Je vais essayer de programmer ça.
  • On a 1080*1079/2  exercices. Si tu veux résoudre tous ces exercices, écrire tous les chemins , idéalement, il faudrait trouver des familles de configurations. 
    Ne pas lancer Djikstra 1080*1079/2 fois, mais beaucoup moins.
    Identifier en particulier que les 2 paniers avec 3 emplacements sont interchangeables.

    Et en fait, ramener les problèmes à des problèmes plus simples. Dès qu'un ballon est au bon emplacement, et au fond de son panier, on se ramène à un exercice avec 4 ballons seulement.

    On doit donc recenser les solutions pour les problèmes avec 1 seul ballon mal placé, puis 2 ballons mal placés etc etc...
    Pour réutiliser au maximum les résultats obtenus... et ne pas répéter plein de calculs un million de fois.
  • Modifié (30 Jan)
    Ce code (en R) te donne la distance la plus courte entre 2 positions.
    convl<-function(l){n<-0
    for(i in 1:8){n<-6*n+l[i]}
    return(n+1)}
    
    convn<-function(n){l<-c(0,0,0,0,0,0,0,0);i<-8
    while(n>0){l[i]<-n%%6;n<-n%/%6;i<-i-1}
    return(l)}
    
    pk<-function(aa,bb){l<-array(100,(6**8));na<-convl(aa);l[na]<-0;nb<-convl(bb);i<-(-1)
    while(l[nb]==100){i<-i+1;m<-which(l==i)
    for(k in m){a<-convn(k)
    
    if(a[1]>0){y<-max(which(a[1:3]>0))
    if(a[5]==0){z<-3+min(which(a[4:5]==0))
    a1<-a;a1[y]<-0;a1[z]<-a[y]
    l[convl(a1)]<-min(l[convl(a1)],i+1)}
    if(a[8]==0){z<-5+min(which(a[6:8]==0))
    a2<-a;a2[y]<-0;a2[z]<-a[y]
    l[convl(a2)]<-min(l[convl(a2)],i+1)}}
    
    if(a[4]>0){y<-3+max(which(a[4:5]>0))
    if(a[3]==0){z<-min(which(a[1:3]==0))
    a3<-a;a3[y]<-0;a3[z]<-a[y]
    l[convl(a3)]<-min(l[convl(a3)],i+1)}
    if(a[8]==0){z<-5+min(which(a[6:8]==0))
    a4<-a;a4[y]<-0;a4[z]<-a[y]
    l[convl(a4)]<-min(l[convl(a4)],i+1)}}
    
    if(a[6]>0){y<-5+max(which(a[6:8]>0))
    if(a[3]==0){z<-min(which(a[1:3]==0))
    a5<-a;a5[y]<-0;a5[z]<-a[y]
    l[convl(a5)]<-min(l[convl(a5)],i+1)}
    if(a[5]==0){z<-3+min(which(a[4:5]==0))
    a6<-a;a6[y]<-0;a6[z]<-a[y]
    l[convl(a6)]<-min(l[convl(a6)],i+1)}}}}
    return(l[nb])}
    
    > pk(c(1,2,3,4,5,0,0,0),c(1,2,3,4,0,5,0,0))
    [1] 1
    > pk(c(1,2,3,4,5,0,0,0),c(3,2,1,5,4,0,0,0))
    [1] 13
  • @Zgrb Merci pour le code je ne connais pas le R je vais voir si je peux faire ce genre de choses en python... En tout cas ça a l'air bien compliqué... Peut être ce serait plus simple en récursif mais je sais pas si R le fait.

    @lourrran ce que tu dis suggère du récursif mais il faut faire attention: les paniers ont des emplacements en moins.

    A vous 2: Je vais essayer de regrouper les configurations. L'idée est plus de faire du calcul mental que de la programmation mais je vais faire les 2... Les 2 sont un bon exercice intellectuel.
  • Je te rajoute les positions les plus "éloignées" pour les 5 types de configuration de départ possible (5 configurations, en renommant les ballons si nécessaire et en échangeant les paniers 1 et 3 si nécessaire)
    Pour un départ en (3,2,0) : 
    distance 14 
    1 2 3 4 5 0 0 0
    4 5 1 0 0 2 3 0
    Pour un départ en (3,1,1) : 
    distance 14
    1 2 3 4 0 5 0 0
    4 5 3 1 0 2 0 0
    
    Pour un départ en (3,0,2) : 
    distance 14
    1 2 3 0 0 4 5 0
    3 4 5 1 2 0 0 0
    
    Pour un départ en (2,2,1) : 
    distance 13
    1 2 0 3 4 5 0 0
    3 5 1 4 2 0 0 0
    Pour un départ en (2,1,2) : 
    distance 14
    1 2 0 3 0 4 5 0
    4 5 3 0 0 1 2 0
  • @Zgrb tu pourrais m'expliquer comment marche ton programme en langage courant? 
    C'est bizarre parce que dans ce jeu, je n'ai jamais eu des configurations espacées de plus de 10... Tu es sur de ce que tu as fait?
  • Modifié (30 Jan)
    En récursif, le problème est que tu vas revisiter des positions un grand nombre de fois. En gros il te faut une table de hashage.

    L'algo part avec une liste de toutes les positions. Il remplit inscrit petit à petit dans la liste la distance de celles qui sont à une distance 1, puis 2, puis 3, jusqu'à obtenir la distance de la position finale. C'est un des algos les plus efficaces pour ce problème !

    Edit : (P1 de taille 3, P2 de taille 2, P3 de taille 3)
    Comment passes-tu en 10 coups de 
    P1 : 1,2,3 (la 1 étant "au fond")
    P2 : 4,5
    P3 : vide
    à
    P1 : 4,5,1
    P2 : vide
    P3 : 2,3
    ?

    Moi j'ai, en 14 déplacements : 
    [1] 1 2 3 4 5 0 0 0
    [1] 1 2 3 4 0 5 0 0
    [1] 1 2 3 0 0 5 4 0
    [1] 1 2 0 3 0 5 4 0
    [1] 1 0 0 3 2 5 4 0
    [1] 1 4 0 3 2 5 0 0
    [1] 1 4 5 3 2 0 0 0
    [1] 1 4 5 3 0 2 0 0
    [1] 1 4 0 3 0 2 5 0
    [1] 1 0 0 3 0 2 5 4
    [1] 0 0 0 3 1 2 5 4
    [1] 4 0 0 3 1 2 5 0
    [1] 4 5 0 3 1 2 0 0
    [1] 4 5 1 3 0 2 0 0
    [1] 4 5 1 0 0 2 3 0
  • Ça paraît impossible, en effet, les 2 positions sont trop distantes. Disons comment faire pour regrouper les configurations pour des positions pas trop distantes(<10)?
  • Je n'ai pas compris ta question...
  • Modifié (30 Jan)
    Je veux dire comme disait @lourrran identifier des familles de positions pour lesquelles la distance est la même. C'est sans doute ce que tu as fait dans ton programme mais je vois pas bien comment...
  • Mon programme peut exhiber toutes les positions qui sont a une distance n de la position de départ si tu le souhaites !
  • Modifié (30 Jan)
    Comment faire? Une boucle for avec ta fonction pk dedans?
  • Les configurations les plus éloignées sont à une distance de 14 mouvements ? Intuitivement, j'aurais pensé nettement plus.

    Je suggérais du récursif, oui, mais ça se gère.   
    Une position peut être décrite par '12x.3x.45x'  :  chaque panier a une case vide.
    Le problème (12x.3x.45x ; 134.xx.25x ) se ramène en fait au problème (2x.3x.45x  : 34.xx.25x )  Toujours 3 paniers , mais de taille 2, 2 et 3
    Avec quand même des réserves.
    Le problème (12x.34.5xx ; 25x.34.1xx ) ne peut pas se ramener au problème (12x.5xx ; 25x.1xx ). Il faut qu'il y ait toujours 3 paniers utilisables.
    Quand je parlais de familles de configurations, je pensais plutôt à (12x.3x.45x ; 134.xx.25x)  et (21x.3x.45x : 234.xx.15x)  : ces 2 problèmes sont les mêmes. 
    Quand on a résolu 1 problème, on en a en fait résolu 120.  Et même quasiment le double, vu que les paniers 1 et 3 sont interchangeables.
  • @lourrran oui c'est plus ça que je cherchais merci beaucoup. On ne pourrait pas aussi utiliser le fait que toute permutation est un produit de transpositions? 

  • Je t'explique le détail du programme. Tout d'abord 2 sous-programmes préliminaires : 
    Le premier qui convertit une liste (que je considere comme un entier en base 6) et un entier en base 10
    Le second qui fait le travail inverse, qui transforme un entier en base 10 en une liste avec des nombres de 0 à 5.

    De telle sorte que chaque position possible soit associé à un entier entre 0 et 6^8. Bien évidemment, ce n'est pas une bijection, car il y a seulement 1080 positions possibles, mais ce n'est pas un soucis.

    Mon programme veut relier la liste a à la liste b
    Du coup, je pars avec une liste L 6^8 éléments remplie de nombres 100.
    J'initialise en mettant l'élément a de la liste L à 0. (Car a est à une distance 0 de lui même)
    Et ensuite, en boucle : 
    Je cherche toutes les positions accessibles à partir de la position a (il y en a au plus 6). Je leur donne la valeur 1 dans la liste (distance 1)
    Je cherche toutes les positions accessibles à partir des positions ayant une valeur 1. Je leur donne la valeur 2 si elles n'ont pas encore eu de valeur (autre que 100)
    Je cherche toutes les positions accessibles à partir des positions ayant une valeur 2...
    Puis quand le nombre associé à b a une valeur autre que 100, c'est fini.

    Remarques : Si on veut juste la distance entre a et toutes les positions, on fait la boucle 14 fois, et toutes les positions accessibles auront une valeur (distance)
    Si on veut connaître le chemin, il faut le faire en remontant. Je pars de b, et je cherche toutes les positions accessibles de b ayant une valeur juste plus petite de 1, et ainsi de suite. Cela me donnera un des chemins minimaux jusque a.

    J'espère que c'est clair !
  • Modifié (30 Jan)
    parfait! J'ai compris ton programme. Juste pourquoi tu arrêtes à 14? Merci. Et aussi tu n'as pas utilisé ce qu'a dit @lourrran?
  • Modifié (30 Jan)
    Ben, j'ai pris les 5 configurations possibles pour le départ, et j'ai testé avec chacune des 5 positions les 1080 positions d'arrivées, et la distance maximale est 14. Donc pas besoin d'aller plus loin pour avoir toutes les distances !

    Mais je me rends compte que j'aurais pu faire plus efficient, remplir la liste avec les distances jusqu'à ce que la distance maximale (hormis les 100) soit plus petite que le nombre d'itérations (ce qui voudrait dire que on a pas trouvé de nouvelles positions à explorer, i.e. on les as toutes explorées)
  • Modifié (30 Jan)
    Ok merci j'ai compris. Mais comment as-tu divisé autant les cas? Comment on passe de la distance d'une position $a$ à une position $b$ à la distance d'une position $a$ à $\sigma(b)$ où $\sigma$ est une permutation à 5 éléments?
  • Pour les 5 combinaisons possibles de départ ?
    Ben si tu regarde les paniers de droite à gauche ou bien de gauche à droite, sans s'occuper du numéro des ballons tu tomberas forcément sur une de ces configurations : 
    (En gros je renommé le panier le plus rempli entre le 1 et le 3 panier 3, et je renomme les ballons de 1 a 5 en commençant par celui au fond du nouveau panier 1)
    (3,2,0)
    (3,1,1)
    (3,0,2)
    (2,2,1)
    (2,1,2)
    Du coup, ce sont les 5 configurations de "base". Après pas le choix malheureusement, il faut calculer la distance de ces 5 chemins a toutes les possibilités, cette fois ci je ne peux pas réduire les cas par symétrie ou en changeant les numéros de ballons.
  • Modifié (31 Jan)
    En fait tu te sers du fait si j'ai bien compris que: en notant $d$ la distance, $d(\sigma(a),\sigma(b))=d(a,b)$ où $a$ et $b$ sont les 2 positions et $\sigma$ une permutation des ballons. C'est bien ça? Mon problème c'est plus de savoir comment on fait pour calculer la distance avec les ballons numérotés parce que suivant comment on numérote les ballons la distance au cas de base ne sera pas la même...
  • Euh c'est juste pour éviter de calculer 200 fois la même chose, mais on peut obtenir la distance de n'importe quelle position à n'importe quelle position
    Après, au lieu de faire la liste des distances pour 1080 positions, je la fais pour 5. 
    Mais si tu ne veux la distance qu'au cas de base, ben pas besoin de faire 5 positions, il suffit de partie d'une seule (le cas de base)
  • Modifié (31 Jan)
    Ok. Ce que je n'ai pas compris c'est que ton cas de base regroupe plusieurs positions distantes, du coup la distance au cas de base n'a pas de sens...
  • Zgrb prend comme positions de départ ces 5 positions  : 123.45.xxx  123.4x.5xx 123.xx.34x  12x.34.5xx  et  12x.3x.45x 
    Toutes les positions de départ peuvent se ramener à une de ces 5 positions, par une renumérotation des paniers (inverion des paniers 1 et 3) et/ou par une permutation des 5 ballons.

    Pour un exercice donné ( position de départ et position d'arrivée imposées), on peut se ramener à cette position de départ, ... et donc recoder aussi la position d'arrivée visée, en appliquant les mêmes permutations.

    A partir de ces 5 positions de bases, il recense toutes les positions (1080 max) qu'on peut atteindre en 1 mouvement, puis en 2 mouvements , puis en 3 mouvements.
    En éliminant les doublons à chaque fois.
    Partant de 123.4x.5xx , on peut faire 12x.43.5xx puis 12x.4x.53x  ...mais ça n' pas d'intérêt . La position 12x.4x.53x pouvait aussi être atteinte par un seul mouvement.

    Il calcule les chemins en partant des 5 positions de bases du départ, mais il cherche comment atteindre les 1080 positions finales, pas uniquement les 5 positions de bases. 
  • Ok la c'est parfaitement clair merci beaucoup à vous deux! Et du coup, est-ce que vous auriez des astuces de calcul mental pour résoudre un exercice avec un couple de positions données? (Ce qui revient à jouer un peu avec le programme)
  • Regarde du côté de la littérature parlant du jeu des tours de Hanoï.
    Ton problème est un problème cousin.
  • Les tours de Hanoï c'est récursif donc de tête j'y arrive bien: par exemple on peut distinguer selon la parité d'un palet. Par contre là, de tête j'ai plus de mal...
  • Partant de 123.45.xxx , on veut atteindre la position 45x.xx.123

    Et donc, on peut avoir 2 techniques : commencer par atteindre une position du type ---.--.1--   ou bien commencer par atteindre une position du type 4--.--.---
    Ou bien faire en sorte d'atteindre ---.--.1--  puis très vite, 4--.--.1--
    Les pires configurations nécessitent 14 mouvements.  Et j'imagine que les configurations qui nécessitent 10 mouvements ou plus sont majoritaires.

    Dérouler un process, partant de 123.45.xxx, je vois quels mouvements il faut faire pour emmener le 1 en bas du panier 3, puis une série de mouvements pour emmener le 4 en bas du panier 1 ... tout ça en aveugle, c'est un exploit. 
    Et on n'a pas du tout l'assurance que le chemin obtenu soit le plus court.

  • Ok epiKx je viens de comprendre ce que je ne comprenais pas dans ta demande en tombant la dessus : 
    https://www.scientificbraintrainingpro.fr/nos-programmes/presco?module=Fonctions-Executives

    Tu veux devenir meilleur à ce jeu, de tête. Pour cela, pas de miracle, Je te conseille un entrainement bête et méchant.
    Tu choisis une situation de départ, d'arrivée, et tu essaies de faire au mieux.
    Puis tu regarde via un algo (je peux te filer le mien) si il y avait un chemin plus court, et surtout quel est ce chemin, et tu l'analyses.
    Je pense que tu devrais vite voir les bons coups, et être aussi performant que l'algo.

    En revanche, je pense que malheureusement, je pense que ce jeu est trop spécifique pour être réellement intéressant cognitivement ! Tu vas juste apprendre par cœur les meilleurs coups et ne plus réfléchir, comme on le ferait pour jouer au morpion.

  • Ahhhh  
    Je me demandais pourquoi ce titre 'Basket à New-York', pourquoi ces questions autour du calcul mental, et tu as trouvé la réponse.
  • Modifié (31 Jan)
    On ne peut rien vous cacher apparemment... :D Merci pour vos réponses. Je vais expérimenter un peu tout ça... 
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!