un petit problème pour les vacances

**Liet Kynes** · 12/08/2023, 20h39

18 config sur 7 lignes:

**Biname** · 12/08/2023, 21h40

Liet,

Envoyé par Liet Kynes

Non à mon avis on en est loin.. mais cela va venir

La solution du msg #28 avec ses hypothèses ajoutées me semble répondre à la demande ?

Il faut comprendre que dans le cas L1_est_une_route(par exemple), le nombre de pavages possibles contenant cette route, comprend tout les pavages dans la grille sous la ligne en L1 soit cas(8,6) = 167089 pavages différents. Parmi ces 167089 pavages, on trouve des pavages sans autre route que L1, des pavages avec route en L2 et/ou route en L3 et/ou en L4 et/ou en L5 et/ou en L6 et/ou en L7.

C'est vrai aussi pour les cas route en L2 ou L3 ou L4 ou L5 ou L6 ou L7.

Biname

**Biname** · 12/08/2023, 22h14

Salut,
Un petit dessin mal fait vaut mieux qu'un long texte :
Nom : grid_image_02_filled_Tittled_50pc.jpg
Affichages : 122
Taille : 123,3 Ko

Tous ces pavages sont inclus dans les cas(8,6) = 167089 pavages
Biname

**Liet Kynes** · 13/08/2023, 06h29

La probabilité d'avoir une route en L1 devrait être : nombre de pavages sans routes du rectangle 6*8 / nombre de pavages total du rectangle 7*8 ->comment connaître le nombre de pavage sans routes du rectangle 6*8 ?

Si on se penche sur la probabilité d'avoir une route en L3 on touche à une difficulté supplémentaire puisque la formule devient :

((nombre de pavages sans routes du rectangle 2*8)*(nombre de pavages sans routes du rectangle 4*8)) / nombre de pavages total du rectangle 7*8

**Biname** · 13/08/2023, 10h08

Liet,
@Biname = moi #32 et 33 : non, on a pas la solution ! Manquent à ce comptage toutes les routes qui ne comprennent pas la route en L1, exemple : une unique route en L3. Mais mon image montre la grille 6,8 ... et aussi la complexité du problème qui ne se résoudra pas en quelques heures ?

Envoyé par Liet Kynes

La probabilité d'avoir une route en L1 devrait être : nombre de pavages sans routes du rectangle 6*8 / nombre de pavages total du rectangle 7*8 ->comment connaître le nombre de pavage sans routes du rectangle 6*8 ?

Oui, ce qui équivaut à dire : le nombre de cas de pavages ne comprenant qu'une seule route en L1 et plus généralement en L_i.
Supposons qu'on ait la formule qui calcule ce nombre de cas Ligne_unique_en_Li(m,n) ou Pas_de_ligne_en(m,n)
Il faudrait donner des noms corrects à ces fonctions : ??? n_cas(m,n) ou n_pav(m,n) = mon 'PI PI', n_sans(m,n) ... bon ça, non ?

Si on se penche sur la probabilité d'avoir une route en L3 on touche à une difficulté supplémentaire puisque la formule devient :
((nombre de pavages sans routes du rectangle 2*8)*(nombre de pavages sans routes du rectangle 4*8)) / nombre de pavages total du rectangle 7*8

n_sans(2,8), n_sans(4,8) et n_pav(7, 8) ou n_cas(7, 8) mais il faudra réécrire PI PI en permutant m et n ??? ligne, colonne c'est mieux.

Biname

**Liet Kynes** · 13/08/2023, 10h30

J'ai l'impression que cela ressemblerait de loin à le méthode pour dénombrer le nombre de partitions d'un nombre sans répétition, formule à rallonge. Mais avec une incertitude quand même sur le calcul des pavages sans routes.

Je ne sais pas si MissJenny est arrivée à ce problème en considérant comme valide l'existence d'une formule permettant de calculer le nombre de pavages d'un rectangle ?

**Biname** · 13/08/2023, 16h28

Salut,

EUREKA ? Ou un coup de latte sur les doigts ?

Par recurrence on trouve sans(l, c) le nombre de pavages sans routes

sans(l, c) est noté ici S_i, de même pour cas(l, c) qui est noté C_i ou i est l'indice de ligne

Résumé :
S_1 = 0
S_2 = C_2 - 1
S_3 = C_3 - 2 * S_2 - 1
S_4 = C_4 - 2 * S_3 - 3 * S_2 - 1
S_5 = C_5 - S_4 - 2 * S_3 - 2 * S_2 - S_2² - 1
S_6 = C_6 - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2² - 2 * S_2 * S_3 - 1

Avec C_7 - S_7 on a tous les pavages comportant au moins une ligne
et avec (C_7 - S_7)/C_7 la probabilité demandée au message #1

Reste à trouver l'algorithme ?

Le raisonnement est bon, la démo aussi mais une erreur d'addition des termes n'est pas exclue ?
Je voudrais aller faire du vélo avant la nuit, je balance ainsi

Démo par récurrence

Cliquez pour afficher

Biname

**Biname** · 13/08/2023, 16h38

Salut,
La récurrence fonctionne car lorsqu'on a une route au moins dans une grille de n lignes, le nombre de ligne sans routes dans cette grille est toujours inférieur à n. On le voit très bien dans la 'démo'.

Biname

**GBZM** · 13/08/2023, 17h53

Bonjour,

La probabilité demandée est $\text{[math]}$ .

**Biname** · 13/08/2023, 18h14

GBZM,
Tu as utilisé 'mon' algorithme ?
Biname

**Liet Kynes** · 13/08/2023, 18h27

Envoyé par GBZM

Bonjour,

La probabilité demandée est $\text{[math]}$ .

Curieux de voir le détail aussi

**Liet Kynes** · 13/08/2023, 18h29

@Biname
Tu peux me donner les valeurs pour les pavages 2*8, 3*8, 4*8 , 5*8 ,6*8 et 7*8 ?

**Biname** · 13/08/2023, 18h53

Salut,

Envoyé par Liet Kynes

@Biname
Tu peux me donner les valeurs pour les pavages 2*8, 3*8, 4*8 , 5*8 ,6*8 et 7*8 ?

cas(8C, 2L) = 33.99999999999999
cas(8C, 3L) = 153.0000000000001
cas(8C, 4L) = 2245.0
cas(8C, 5L) = 14824.00000000002
cas(8C, 6L) = 167089.0000000001
cas(8C, 7L) = 1292697.000000002

Code:

for i in [2,3,4,5,6,7]:
    print (f"cas(8C, {i}L) = ", cas(8,i))

Les S_i peuvent se factoriser et l'algorithme doit être assez simple ...

Dans C_7 - S_7, C_7 saute car S_7 = C_7 - .... f(S_6, ...)

Biname

**Liet Kynes** · 13/08/2023, 19h03

Je trouve comme toi avec ce code:

Code:

def formula(m, n):
...     result = 1
...     for j in range(1, floor(m/2) + 1):
...         for k in range(1, floor(n/2) + 1):
...             result *= (4 * cos(pi * j / (m + 1))**2 + 4 * cos(pi * k / (n + 1))**2)
...     return result
...
>>> result = formula(6, 8)
>>> print(result)
167089.0000000004

Je vais développer ma formule pour voir ce que je trouve

**Biname** · 13/08/2023, 19h04

Salut,
Sauf erreurs, voici ce qu'on trouve pour S_7

Calculons S_7
pour "??????N" : C_7 cas
pour "x000000" : S_6 cas
pour "00x0000" : S_2 * S_4 cas
pour "000x000" : S_3² cas
pour "0000x00" : S_4 * S_2 cas
pour "000000x" : S_6 cas
pour "xx00000" : S_5 cas
pour "00xx000" : S_2 * S_3 cas
pour "000xx00" : S_3 * S_2 cas
pour "00000xx" : S_5 cas
pour "xxx0000" : S_4 cas
pour "0000xxx" : S_4 cas
pour "00xxx00" : S_2² cas
pour "xxxx000" : S_3 cas
pour "000xxxx" : S_3 cas
pour "xxxxx00" : S_2 cas
pour "00xxxxx" : S_2 cas
pour "xxxxxxx" : 1 cas
les autres "???????" = "xxxxxxx" ou "0000000" = S_7
pour "000000" = S_7 = C_7 - 2 * S_6 - 2 * S_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_3²
- S_2² - 2 * S_2 * S_4 - 2 * S_2 * S_3 - 1

S_7 = C_7 - 2 * (S_6 + S_5 + S_4 + S_3 + S_2) - S_3² - S_2² - 2 * (S_2 * S_3 + S_2 * S_4) - 1

Qui sortira l'algorithme ? Moi, je vais Pythonner.

Biname

**Liet Kynes** · 13/08/2023, 19h21

J'ai un petit doute, par exemple pour "00x0000" : S_2 * S_4 cas" mais il faut oter les cas déjà dans S2 et S4 non ? tu les as soustraits ?

**Biname** · 13/08/2023, 19h22

Liet msg #44
Dans mes valeurs de S_i
J'ai trouve une étrangeté
S_4 = C_4 - 2 * S_3 - 3 * S_2 - 1
normalement on a jamais 3 * S_i ? mais 2 * S_i ? Je ne vois pas l'erreur

et au mins une erreur, je crois que c'est ici, 2 * S_4 et non S_4
S_5 = C_5 - 2 * S_4 - 2 * S_3 - 2 * S_2 - S_2² - 1

Biname

**Biname** · 13/08/2023, 19h23

Envoyé par Liet Kynes

J'ai un petit doute, par exemple pour "00x0000" : S_2 * S_4 cas" mais il faut oter les cas déjà dans S2 et S4 non ? tu les as soustraits ?

Quels cas ?
Tu as i cas sans route(S_?) dans le rectangle du haut et j cas sans routes(S_?) dans le rectangle du bas
P.S. 1
Au fond, oui peut-être ?????
P.S. 2
Non, S_i voir définition

**GBZM** · 13/08/2023, 19h48

La partie difficile, c'est le dénombrement des pavages par dominos. Mais ça, c'est déjà connu.
Le reste, c'est la routine de la formule du crible de Poincaré pour calculer le cardinal de la réunion de L_i, où L_i est l'ensemble des configurations avec un chemin traversant horizontal en ligne n° i.

J'ai calculé en SageMath. C'est pratiquement du python, et avec un peu d'effort je pourrais traduire en code python pur.

Code:

# Nombre de pavages 8*n
def Pav(n) :
    nb=1
    for j in range(1,5) :
        nb *= prod(4*cos(j*pi/9)^2 + 4*cos(k*pi/(n+1))^2 
                   for k in range(1,ceil(n/2)+1))
    return round(nb)

Pav=[Pav(n) for n in range(8)]
Pav

[1, 1, 34, 153, 2245, 14824, 167089, 1292697]

Code:

# Nombre de pavages 8*n avec chemin horizontal en lignes
# de la liste L (numérotation des lignes de 0 à n-1)

def PLH(L,n) :
    nb=Pav[L[0]]
    for i in range(len(L)-1) :
        nb *= Pav[L[i+1]-L[i]-1]
    nb *= Pav[n-1-L[-1]]
    return nb

# Nombre de pavages 8*n avec au moins un chemin horizontal
# (formule du crible de Poincaré)

def H(n) :
    H=0
    for k in range(n) :
        C=Combinations(range(n),k+1).list()
        H += (-1)^k * sum(PLH(L,n) for L in C)
    return H

H(7)

463733

**Liet Kynes** · 13/08/2023, 19h50

Voilà les cas possibles de configurations différentes avec des lignes traversantes que je trouve, 16 configurations dont 3 sont symétriques (vert plus une croix = ligne traversante):

	x	x	x	x	x	x	x

	x	0	0	0	0	0	0

	x	x	0	0	0	0	0

	x	x	x	0	0	0	0

	x	x	x	x	0	0	0

	x	x	x	x	x	0	0

	0	0	x	0	0	0	0

	0	0	x	x	0	0	0

1	0	0	x	x	x	0	0

	x	x	x	x	0	0	x

1	0	0	0	x	0	0	0

	x	x	0	0	x	0	0

	x	x	x	0	0	x	x

	x	x	0	0	0	0	x

	x	x	x	0	0	0	x

1	x	x	0	0	0	x	x

Si je calcul pour la configuration suivante:

x

0

x

0

Je commence par déterminer le de pavages sans ligne pour les deux groupes "00", un groupe 00 correspond au rectangle 2*8, pour ce rectangle on peut avoir la ligne 1 traversante ,la ligne 2 traversante et les deux lignes traversantes donc le nombre de pavages sans ligne traversantes est de 34-3=31 ensuite je combine les deux groupes "00" (donc sans ligne) et j'obtiens 31*31= 961 façons de paver de manière à ce que les ligne 1,2,5 soient traversantes.

je fait la même chose pour les autres configurations en sachant que la difficulté est de déterminer le pavage sans lignes traversantes , cela se complique très vite

**Biname** · 13/08/2023, 19h54

Salut,
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

Sans la correction pour S_5, je trouve
C_7 = 1292697.000000002
S_7 = 850955.0000000021
Cas Favorables C_7 - S_7 = 441742.0
Proba = (C_7 - S_7)/C_7 = 0.3417212231481927

Python

Cliquez pour afficher

Sauf erreurSSS

Sejam

**Biname** · 13/08/2023, 20h01

GBZM,
Je me disais aussi avec mes petits dessins qu'un vrai matheux allait y reconnaître un cas connu.
Biname

**Biname** · 13/08/2023, 20h52

Envoyé par GBZM

J'ai calculé en SageMath. C'est pratiquement du python, et avec un peu d'effort je pourrais traduire en code python pur.

Faut demander à GPT

Cliquez pour afficher

Echanges avec GPT

Cliquez pour afficher

Et ça marche sortie python :

Code:

Pav_list: [1, 1, 34, 153, 2245, 14824, 167089, 1292697]
Result: 463733

? 5 minutes ? Moins que pour rédiger ce msg. Tu aurais pu demander C++, HTML, et plein d'autres ... dont SageMath

Biname

**Biname** · 13/08/2023, 21h25

Liet msg #50,

Tu peux trouver ici un interpréteur python en ligne avec mon code domino python de référence (avec Poincaré) :
Si tu t'inscris, tu peux 'forker' ce code et en créer d'autres, c'est gratuit.
https://onlinegdb.com/E31SqcbHr

Je ne comprends pas pourquoi tu rejettes les symétriques ? Ca ne signifie pas que tu as tort

Biname

**GBZM** · 13/08/2023, 22h00

Plutôt que de jouer avec ChatGpt, il serait plus formateur de comprendre la formule du crible de Poincaré, comment elle intervient ici et dans pas mal d'autres problèmes.

**Liet Kynes** · 13/08/2023, 22h07

Envoyé par Biname

Je ne comprends pas pourquoi tu rejettes les symétriques ? Ca ne signifie pas que tu as tort

Biname

Je me dit que s'agissant d'un jeu de plateau, une symétrique revient à le tourner deux fois vers la gauche ou la droite ..

**Biname** · 14/08/2023, 00h12

Salut,

Envoyé par GBZM

Plutôt que de jouer avec ChatGpt, il serait plus formateur de comprendre la formule du crible de Poincaré, comment elle intervient ici et dans pas mal d'autres problèmes.

A mon âge, les formations !

Votre rejet de ChatGPT ou GPT est incompréhensible, voire pathologique ... mais bon. Il n'est pas bon à tout, mais pour écrire du code, il est devenu à mon avis indispensable, sauf dans le langage qu'on connait bien et encore, ce qui n'est pas mon cas pour Python.

Poincaré : https://www.techno-science.net/definition/6063.html
Crible de Poincaré : c'est la première fois que je vois une application pratique de la théorie des ensembles

, je ne suis pas non plus une référence.
Il faut avoir fait les exercices pour se souvenir et comprendre, je lis tous, mais je ne vois pas comment ceci pourrait s'appliquer à notre cas. Je pourrais éventuellement faire un parallèle avec ton code, je vois (-1)^n chez les deux.

Merci

Biname

**Liet Kynes** · 14/08/2023, 03h47

Envoyé par GBZM

Plutôt que de jouer avec ChatGpt, il serait plus formateur de comprendre la formule du crible de Poincaré, comment elle intervient ici et dans pas mal d'autres problèmes.

Tu peux expliquer pourquoi et comment tu raisonnes avec cette formule?
Un truc que je ne comprends pas c'est le fait que le pavage implique des règles implicites dans la formation des lignes traversantes, pour trouver tout les cas de lignes traversantes d'un rectangle 4*8 par exemple on ne peut pas dire qu'il y'en aura 2^4 car une traversante en position 2 ou en position 3 implique une traversante en position 1 ou en position 4, de même un écart de une case entre deux lignes traversantes implique que la ligne intermédiaire soit aussi traversante.

**Liet Kynes** · 14/08/2023, 07h21

Je trouve en excluant les symétries : 0.21946 (22%) avec les symétries 0.42158 (42%)

Détail du calcul dans le fichier joint

**GBZM** · 14/08/2023, 07h43

Le problème n'est pas d'écrire du code (ce que ChatGpt peut faire), le problème est de comprendre ce que fait cette formule du crible et comment elle s'applique ici (et ça ChatGpt ne peut pas le faire à votre place !).
J'ai déjà donné l'essentiel, alors je répète en détaillant plus : soit $\text{[math]}$ l'ensemble des pavages par dominos de la grille 8x7. Je note $\text{[math]}$ le sous-ensemble de $\text{[math]}$ formé des pavages qui présentent un chemin traversant horizontal en ligne n° $\text{[math]}$ (pour faire comme dans mon code, je numérote les lignes de 0 à 6).
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 $\text{[math]}$ pour $\text{[math]}$ 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 ici qu'intervient la formule du crible. Elle nous dit que le nombre d'éléments de cette réunion est la somme des nombres d'éléments des $\text{[math]}$ , moins la somme des nombres d'éléments de leurs intersections deux à deux, plus la somme des nombres d'éléments de leurs intersections trois à trois etc.
En formule,

$\text{[math]}$

où les barres désignent le cardinal d'un ensemble et $\text{[math]}$ .

Il reste à calculer ces $\text{[math]}$ . Je le fais sur l'exemple $\text{[math]}$ . On a donc un chemin traversant en ligne 0, un autre en ligne 1, un autre en ligne 5. Au dessus de la ligne 0, on a un rectangle de largeur 8 et hauteur 0 : une seule façon de la paver !: Entre la ligne 0 et la ligne 1,un rectangle de largeur 0 et hauteur 8 : une seule façon de le paver. Entre la ligne 2 et la ligne 5, un rectangle de largeur 8 et hauteur 2 : 34 façons de le paver. Enfin en-dessous de la ligne 5, un rectangle de largeur 8 et hauteur 1 : une seule façon de paver. En conclusion, le nombre d'éléments de TEX]L_I[/TEX] est 1 x 1 x 34 x 1=34

un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Re : un petit problème pour les vacances

Discussions similaires

Bonsoir petit coup de main pour un DM spéciale vacances

Petit catamaran pour vos vacances

Un petit DM pour les vacances

Retour de vacances et petit souci...