un petit problème pour les vacances

[Liet Kynes]

La première chose à comprendre c'est que ce que l'on cherche à calculer, c'est le nombre d'éléments de la réunion des pour allant de 0 à 6. En effet, cette réunion est l'ensemble des pavages qui présentent au moins un chemin traversant horizontal. D'accord ?

C'est cela que je ne comprends pas, Si tu as une ligne traversante en L1 et une en L3 tu as obligatoirement une ligne traversante en L2 donc tu ne peux normalement pas inclure dans la réunion des Li ces sous ensembles là au risque de les compter plusieurs fois ?
-----

[GBZM]

La probabilité demandée par Miss Jenny est 35,87%. Les deux résultats donnés par Liet Kynes sont donc faux, et par ailleurs les symétries n'interviennent pas dans le problème posé par Miss Jenny.

Liet Kynes, tu te poses un faux problème ! Les configurations que l'on cherche à dénombrer ne sont-elles pas celles pour lesquelles il existe au moins une ligne pour lesquelles il existe un chemin traversant horizontal sur cette ligne ? C'est donc bien la réunion des .

[GBZM]

Un pavage peut présenter plusieurs chemins traversants horizontaux, donc apparaître dans plusieurs . Mais justement la formule du crible prend cela en compte en retranchant de la somme des cardinaux des la somme des cardinaux de leurs intersections 2 à 2, puis en ajoutant la somme des cardinaux des intersections 3 à 3 etc.
Médite bien sur cette formule du crible.

[Liet Kynes]

Liet Kynes, tu te poses un faux problème ! Les configurations que l'on cherche à dénombrer ne sont-elles pas celles pour lesquelles il existe au moins une ligne pour lesquelles il existe un chemin traversant horizontal sur cette ligne ? C'est donc bien la réunion des .

Quand tu calcules l'union des Li , le sous ensemble avec L1 et L3 traversants est en fait le sous-ensemble L1,L2 et L3 traversants, comment fais tu pour éviter ce doublon?

[GBZM]

Quel doublon ?
Une configuration donnée avec des chemins traversants horizontaux en lignes 1, 2 et 3. figure une et une seule fois dans la réunion des . Elle figure une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans .
Une nouvelle fois, médite sur la formule du crible !

[Liet Kynes]

Quel doublon ?
Une configuration donnée avec des chemins traversants horizontaux en lignes 1, 2 et 3. figure une et une seule fois dans la réunion des . Elle figure une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans , une et une seule fois dans .

Parmi les Li, si je considère celui qui a des chemins traversants horizontaux en lignes 2 et 3 alors je considère celui qui a des chemins traversants horizontaux en lignes 1,2 et 3 = le cas Li avec uniquement des chemins en L2 et L3 n'existe pas car un chemin en L2 implique obligatoirement un chemin en L1.

[GBZM]

Pourrais-tu faire un "Control reset" ? Là, tu tournes en rond sur un problème qui n'existe pas.

Soit l'ensemble des pavages par dominos qui présentent au moins un chemin traversant horizontal sur une ligne. C'est bien le nombre d'éléments de que l'on essaie de calculer, d'accord ?
Soit l'ensemble des pavages par dominos qui présentent un chemin traversant horizontal en ligne (on ne dit rien sur le reste du pavage, il peut présenter d'autres chemins horizontaux traversants, on s'en fiche). Tu as bien compris cette défiition ?
Alors est une partie de et est la réunion des . Élémentaire, non ?
NB : un même pavage peut appartenir à plusieurs , la réunion n'est sûrement pas disjointe ! Le nombre d'éléments de la réunion n'est pas la somme des nombres d'éléments des , mais la formule du crible s'occupe justement de ça !

[Biname]

Liet msg #59,

La colonne AC de ton tableau représente ce que je nomme S_i : le nombre de grilles sans route dans i lignes horizontales successives.
Si c'est le cas, on ne trouve pas les mêmes valeurs pour les S_i

S_1 = 0
S_2 = 33
S_3 = 86
S_4 = 1920
S_5 = 9656
S_6 = 136933
S_7 = 854559
Avec S_i =

 Cliquez pour afficher

S_1 = 0
S_2 = cas(m, 2) - 1
S_3 = cas(m, 3) - 2 * S_2 - 1
S_4 = cas(m, 4) - 3 * S_3 - 2 * S_2 - 1
S_5 = cas(m, 5) - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2**2 - 1
S_6 = cas(m, 6) - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2**2 - 2 * S_2 * S_3 - 1
S_7 = cas(m, 7) - 2 * S_6 - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_3**2 - S_2**2 - 2 * S_2 * S_4 - 2 * S_2 * S_3 - 1

Pour nous mettre d'accord, on pourrait dessiner tous les cas 'à la main sur une grille réduite : ??6 x 5
cas(4,3) = 11
cas(6,5) = 1183
cas(8,7) = 1292697
Le cas 4 est accessible

Un code qui créerait toutes les grilles :
Avec GPT on a écrit un code qui dessine ceci au hasard

 Cliquez pour afficher

An part à 1, 2, 3, 4, 5, A, ... , V, 3 fois sur 4 ça marche :

En mode texte, un grille occuperait 56 octets, 1300000 grilles 100 MB, c'est jouable.

Ou plus simplement vérifier mes S_i

Biname

[GBZM]

Le problème est résolu. Pourquoi s'obstiner dans un bazar inextricable ?

[Biname]

Le problème est résolu. Pourquoi s'obstiner dans un bazar inextricable ?

Parce que je ne comprends pas ta solution et que je préfère la mienne et aussi parce que ça m'amuse, sinon, je ne vois vraiment pas en quoi ce problème pourrait m'intéresser.

Ton code SageMath fait intervenir une combinaison, je ne la vois pas la formulation Poincaré que tu utilises, j'imagine bien que ...

[GBZM]

"je préfère la mienne"
Existe-t-elle ? Pour le moment, je ne l'ai pas vue.

Pour la formule du crible, ou principe d'inclusion-exclusion, tu peux voir la page wikipedia https://fr.wikipedia.org/wiki/Princi...sion-exclusion. Il y a dans cette page une formule que je recopie :

Tu vois bien que la deuxième somme est indexée par l'ensemble des parties à éléments de ? Voila d'où viennent les combinaisons (dans la formule ci-dessus, combinaisons de éléments pris à ).

[Biname]

Pour une grille 4 * 3, 11 cas possibles, on doit trouver

Manquent 2 cas ????

xxx
HHHH
HHHH
HHHH
1 cas

x00 2 x par symétrie avec 00x
HHHH HHHH HHHH
HHVV VVHH VHHV ou + 1 cas ici ???
HHVV VVHH VHHV
3 cas x 2 = 6 cas

000
VVHH HHVV
VVVV VVVV ou +2 cas là ???
HHVV VVHH

ou PI PI = cas(m, n) est faux

Biname

[Biname]

"je préfère la mienne"
Existe-t-elle ? Pour le moment, je ne l'ai pas vue.

msg #37 pour définitions, principe et par récurrence S_1 à S_6
msg #45 ajout S_7
msg #47 correction et terme ???incongru
msg #51 cas, proba et code

Avec les corrections je trouve
C_7 = 1292697.000000002
S_7 = 854901.0000000021
Cas Favorables C_7 - S_7 = 437796.0
Proba = (C_7 - S_7)/C_7 = 0.338668690342748

Une vérification et critique serait appréciée.

[GBZM]

C'est mieux que les résultats de Liet Kynes, mais ce n'est tout de même pas ça. La réponse correcte pour le nombre de cas favorables est 463 733, ce qui donne une probabilité d'environ 35,87 %

[GBZM]

Tiens, je te donne la liste du nombre de cas favorables (existence d'un chemin traversant horizontal) pour des grilles à n lignes et 8 colonnes, où n varie de 0 à 19 :
0,
1,
1,
67,
272,
5426,
34168,
463733,
3558245,
40423745,
341774922,
3543203530,
31430594248,
310092581147,
2815096255711,
27009936374613,
247773142270344,
2338769967876768,
21540614004729318,
201292564878142083
Ça te permettra de vérifier tes calculs.

[Biname]

Tiens, je te donne la liste du nombre de cas favorables (existence d'un chemin traversant horizontal) pour des grilles à n lignes et 8 colonnes, où n varie de 0 à 19 :
Ça te permettra de vérifier tes calculs.

Je calcule ta valeur avec C_i - S_i et je trouve :
GB_1 = 1.0000000000000007
GB_2 = 1.0
GB_3 = 66.99999999999999
GB_4 = 325.00000000000045 ça décroche ici et c'est justement là que j'ai un truc bizarre, un 3 qui devrait être un 2
GB_5 = 5167.999999999998
GB_6 = 30156.00000000003
GB_7 = 438138.0


Théoriquement mon S_i = C_i - ta_valeur , C_i = PI PI = cas(m, i)
Mon principe est bon(msg #37), par contre une erreur de ma part n'est pas exclue, j'ai fait ça en vitesse hier.

Je m'y recolle ... rai

Biname

[GBZM]

Ce que tu essaies de faire avec ta récurrence, c'est ce que fait sans peine le principe d'inclusion-exclusion ou formule du crible.
Tu devrais pouvoir compter le nombre de pavages par dominos qui ont des chemins traversants horizontaux en des lignes données et qui font ce qu'ils veulent en dehors de ces lignes.
Il vaut mieux prendre les choses par le bon bout ...

[Biname]

Ce que tu essaies de faire avec ta récurrence, c'est ce que fait sans peine le principe d'inclusion-exclusion ou formule du crible.
Tu devrais pouvoir compter le nombre de pavages par dominos qui ont des chemins traversants horizontaux en des lignes données et qui font ce qu'ils veulent en dehors de ces lignes.
Il vaut mieux prendre les choses par le bon bout ...

Et avec ce qu'on sait/comprend, je parle pour moi
On progresse trouvé deux erreurs
GB_1 = 1.0000000000000007
GB_2 = 1.0
GB_3 = 66.99999999999999
GB_4 = 272.00000000000045
GB_5 = 5359.999999999998 ca déroche ici maintenant !
GB_6 = 29878.00000000003
GB_7 = 441914.0

Il devient évident que ça va coller et maintenant je sais où chercher mes erreurs

Biname

[GBZM]

Avec un minimum d'investissement, tu comprendrais la formule du crible et comment elle s'applique ici (comme dans pas mal d'autres problèmes). Ça n'a rien de compliqué et ça t'éviterait ces tâtonnements fastidieux.
Enfin, comme on dit (et sans te prendre pour un bourricot), "On ne saurait faire boire un âne qui n'a pas soif".

[Liet Kynes]

Tiens, je te donne la liste du nombre de cas favorables (existence d'un chemin traversant horizontal) pour des grilles à n lignes et 8 colonnes, où n varie de 0 à 19 :
0,
1,
1,
67,
272,

Pour n=2 , 1 seul cas favorable ? C'est à dire que sur l'ensemble des pavages possibles 1 seul contient une ligne traversante?
Pourtant on peut avoir L1, L2 et (L1,L2)

[GBZM]

Apparemment tu n'as pas encore fait ton "Control reset".
C'est bien évident qu'il y a un seul pavage par dominos dans ce cas avec au moins un chemin traversant horizontal !
C'est le pavage où tous les dominos sont horizontaux. Il est dans , dans et dans (je numérote à partir de 0).

[Biname]

Pour n=2 , 1 seul cas favorable ? C'est à dire que sur l'ensemble des pavages possibles 1 seul contient une ligne traversante?
Pourtant on peut avoir L1, L2 et (L1,L2)

"??" : Tu ne peux pas avoir L1 sans avoir L2 et l'inverse, tu n'as que deux cas tous HH ou tous VV
L1: HHHHHHHH
L2: ?????????? comment places-tu des VV ici ?

Biname

[Liet Kynes]

Apparemment tu n'as pas encore fait ton "Control reset".
C'est bien évident qu'il y a un seul pavage par dominos dans ce cas avec au moins un chemin traversant horizontal !
C'est le pavage où tous les dominos sont horizontaux. Il est dans , dans et dans (je numérote à partir de 0).

Je suis long pour appuyer sur les touches

[Biname]

Avec un minimum d'investissement, tu comprendrais la formule du crible et comment elle s'applique ici (comme dans pas mal d'autres problèmes). Ça n'a rien de compliqué et ça t'éviterait ces tâtonnements fastidieux.
Enfin, comme on dit (et sans te prendre pour un bourricot), "On ne saurait faire boire un âne qui n'a pas soif".

Réponse goguenarde de l'âne : il n'y pas que le cerveau dans la vie, à chacun son truc.

Je lis mal ces trucs intersection, union, ... !
J'y vais à mon rythme. J'ai fait l'effort de demander à GPT de me lister, les "combinaisons" utilisées dans ton code SageMath.

 Cliquez pour afficher

Contenu de C:
[

[(0,), (1,), (2,), (3,), (4,), (5,), (6,)],

[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)],

[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 1, 5), (0, 1, 6), (0, 2, 3), (0, 2, 4), (0, 2, 5), (0, 2, 6), (0, 3, 4), (0, 3, 5), (0, 3, 6), (0, 4, 5), (0, 4, 6), (0, 5, 6), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 4), (1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (1, 5, 6), (2, 3, 4), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)],

[(0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 2, 5), (0, 1, 2, 6), (0, 1, 3, 4), (0, 1, 3, 5), (0, 1, 3, 6), (0, 1, 4, 5), (0, 1, 4, 6), (0, 1, 5, 6), (0, 2, 3, 4), (0, 2, 3, 5), (0, 2, 3, 6), (0, 2, 4, 5), (0, 2, 4, 6), (0, 2, 5, 6), (0, 3, 4, 5), (0, 3, 4, 6), (0, 3, 5, 6), (0, 4, 5, 6), (1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 3, 6), (1, 2, 4, 5), (1, 2, 4, 6), (1, 2, 5, 6), (1, 3, 4, 5), (1, 3, 4, 6), (1, 3, 5, 6), (1, 4, 5, 6), (2, 3, 4, 5), (2, 3, 4, 6), (2, 3, 5, 6), (2, 4, 5, 6), (3, 4, 5, 6)],

[(0, 1, 2, 3, 4), (0, 1, 2, 3, 5), (0, 1, 2, 3, 6), (0, 1, 2, 4, 5), (0, 1, 2, 4, 6), (0, 1, 2, 5, 6), (0, 1, 3, 4, 5), (0, 1, 3, 4, 6), (0, 1, 3, 5, 6), (0, 1, 4, 5, 6), (0, 2, 3, 4, 5), (0, 2, 3, 4, 6), (0, 2, 3, 5, 6), (0, 2, 4, 5, 6), (0, 3, 4, 5, 6), (1, 2, 3, 4, 5), (1, 2, 3, 4, 6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6)],

[(0, 1, 2, 3, 4, 5), (0, 1, 2, 3, 4, 6), (0, 1, 2, 3, 5, 6), (0, 1, 2, 4, 5, 6), (0, 1, 3, 4, 5, 6), (0, 2, 3, 4, 5, 6), (1, 2, 3, 4, 5, 6)],

[(0, 1, 2, 3, 4, 5, 6)]

]

Il s'agit de l'itération des diverses combinaisons et non de leur comptage, ce que fait la ligne suivante


Et le (-1)^n va faire alterner le signe ?

[GBZM]

Je m'étonne que tu aies besoin de ChatGPT pour comprendre ce que sont les parties à 1 élément, à 2 éléments, à 3 éléments ... de {0,1,2,...,6}
Oui les signes alternent ! (PLUS pour les nombres d'éléments des , MOINS pour les nombres d'éléments des intersections 2 à 2, PLUS pour les intersections 3 à 3 etc.).
Prenons l'exemple bête d'une grille à deux lignes et 8 colonnes
(ensemble des pavages par dominos où la ligne n° 0 est un chemin traversant horizontal) a un et un seul élément
(ensemble des pavages par dominos où la ligne n° 1 est un chemin traversant horizontal) a un et un seul élément, c'est le même.
L'intersection a toujours un et et seul élément, toujours le même.
La formule du crible dit que le nombre de cas favorables (existence d'un chemin traversant horizontal) est le nombre d'éléments de plus celui de MOINS le nombre d'éléments de , ce qui fait 1+1-1 = 1. Idiot, n'est-ce pas ?
Maintenant je te conseille de recommencer avec une grille à 3 lignes et 8 colonnes.
Compte les nombres d'éléments de et applique la formule du crible en faisant bien attention aux signes. Tu obtiendras le nombre d'éléments de la réunion , qui est le nombre de pavages avec au moins un chemin traversant horizontal.

[GBZM]

Allez, je t'aide : a 34 éléments, puisque c'est le nombre de pavage par dominos du rectangle 2x8 en-dessous de la ligne n° 0.

[Biname]

Allez, je t'aide : a 34 éléments, puisque c'est le nombre de pavage par dominos du rectangle 2x8 en-dessous de la ligne n° 0.

Si tu veux m'aider, c'est en S_5 que nos résultats divergent. C'est aussi en S_5 qu'apparaissent les termes au carré ?
Quel cas manque, ou, où est l'erreur ?

Calculons S_5
nombre de cas sans routes parmi 5 lignes, C_5 = PI PI (8, 5) dont on retire tous les cas avec routes
on a calculé S_2, S_3, S_4 avant et jusqu'à S_4 nos résultats sont égaux

Si tu ne trouves rien, Poincaré ne convient peut-être pas à notre cas.

pour "?????" : C_5 cas
pour "x0000" : S_4 cas
pour "00x00" : S_2² cas
pour "0000x" : S_4 cas
pour "xx000" : S_3 cas
pour "000xx" : S_3 cas
pour "x000x" : S_3 cas
pour "xxx00" : S_2 cas
pour "00xxx" : S_2 cas
pour "x00xx" : S_2 cas
pour "xx00x" : S_2 cas
pour "xxxxx" : 1 cas
les autres "????" = "xxxxx" ou "00000" = S_5
pour "00000" = S_5 = C_5 - 2 * S_4 - 3 * S_3 - 4 * S_2 - S_2² - 1

Ton discours toxique en dit long sur ta personnalité

Biname

[GBZM]

Donc et on chacun 34 éléments, tandis que , les intersections 2 à 2 et l'intersection des 3 ont toutes un élément, toutes le même : le pavage avec tous les dominos horizontaux. Ça fait donc 34+1+34-1-1-1+1 = 67.

Poincaré se débrouille sans difficulté du cas à 5 lignes (j'ai déjà donné le résultat).

Pourquoi ne demandes-tu pas à ChatGPT ce qui ne va pas dans ton compte ?

[Liet Kynes]

Donc et on chacun 34 éléments, tandis que , les intersections 2 à 2 et l'intersection des 3 ont toutes un élément, toutes le même : le pavage avec tous les dominos horizontaux. Ça fait donc 34+1+34-1-1-1+1 = 67.

Poincaré se débrouille sans difficulté du cas à 5 lignes (j'ai déjà donné le résultat).

Pourquoi ne demandes-tu pas à ChatGPT ce qui ne va pas dans ton compte ?

Si tu écris la formule en remplaçant les nombres par des mots cela marchera mieux.. perso j'ai pigé globalement mon erreur mais le début de ma démarche n'était pas idiote.. j'aurais du rester sur l'idée intuitive d'une formule pour dénombrer les partitions d'entiers, c'est cousin.

[GBZM]

"Si tu écris la formule en remplaçant les nombres par des mots cela marchera mieux"
Heu ?

Poincaré pour 5 lignes, avec la notation de Biname
Il y a 5 : 2 x 2 x ,
Il y a 10 intersections 2 à 2 : 3 x , 6 x , 1
Il y a 10 intersections 3 à 3 : 4 x + 6 x 1
Il y a cinq intersections 4 à 4 : 5 x 1
Et l'intersection des 5 : 1
La formule du crible donne

Le procédé est systématique, c'est plus agréable d'écrire un code (je l'ai fait).