Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 15-06-2017 23:08:31

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

pavage avec drs dominos

Bonjour,

On peut remarquer que dans certains cas, il est possible de paver un rectangle à coordonnées entières avec des dominos.

Chaque domino occupe deux carrés à coordonnées entières et adjacents. Deux dominos ne peuvent pas se superposer, et l'ensemble du rectangle doit être recouvert.

Voici un exemple de pavage  d'un rectangle 6x9 :
http://www.prise2tete.fr/upload/caduk-dominos.JPG

1) Combien de  pavages différents est il possible de réaliser dans un rectangle 2xN?
2) Combien de pavages différents est il possible de réaliser dans un rectangle 3xN?

  • |
  • Répondre

#0 Pub

 #2 - 16-06-2017 09:03:20

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

pavagz avec des dominos

Dans le cas 2xN, c'est la suite de Fibonacci : un pavage 2xN commence à gauche soit par un domino vertical, puis il y a un pavage 2x(N-1) ; soit par deux dominos horizontaux, puis il y a un pavage 2x(N-2). On obtient ainsi U(N)=U(N-1)+U(N-2).

Dans le cas 3xN, on applique la même idée, mais c'est un peu plus complexe. Déjà, inutile d'espérer quoi que ce soit si N est impair, étant donné qu'un domino recouvre deux cases. Sinon, on remarque qu'un pavage de largeur N, en commençant de la gauche, c'est soit un pavage 3x2 (3 possibilités) suivi d'un pavage de largeur N-2 ; soit, un pavage 3x4 ne contenant pas de sous-pavage 3x2 (2 possibilités) suivi d'un pavage de largeur N-4 ; soit...

En poursuivant le raisonnement, il vient V(N)=3V(N-2)+2(V(N-4)+V(N-6)+...+V(0)) ce qui se transforme en V(N)=4V(N-2)-V(N-4) (avec V(0)=1 et V(2)=3).

Il vient [latex]V(N)=\frac{3+\sqrt{3}}{6}(2+\sqrt{3})^\frac{N}{2}+\frac{3-\sqrt{3}}{6}(2-\sqrt{3})^\frac{N}{2}[/latex].

https://oeis.org/A001835

 #3 - 16-06-2017 13:15:58

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

pavage avec dzs dominos

Parfait Ebichu!

 #4 - 16-06-2017 14:28:43

Smok2k
Habitué de Prise2Tete
Enigmes résolues : 27
Messages : 13

Paage avec des dominos

Y'a du Fibonacci dans l'air smile

 #5 - 16-06-2017 14:59:30

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Pavage avec des doominos

Smok2k
Oui, tu es sur la bonne piste smile
Le cas avec 3 de largeur est légèrement plus complexe...

 #6 - 17-06-2017 10:06:59

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,004E+3

pavage avec des domibos

La première question est toute simple : F(N+1) le problème est en tout point identique à celui de "grenouille et escaliers". smile

Pour 3 x N , déjà, N doit être pair...
Ensuite, il faut se concentrer sur les remplissages « intermédiaires », c'est à dire les rangs pour les quels le remplissage est complet au rang 2n.

Pour remplir 2 colonnes, il y a 3 possibilités.

Pour en remplir 4 ,
soit on part d'un remplissage de 2, (3x3 possibilités)
Soit on n'a pas de sécantes = > 2 possibilités
On arrive donc à 11 remplissages.

Pour en remplir 6,
Soit on part de 4 => 11 x 3
Soit on part de 2 (sans sécante pour finir) => 3 x 2
Soit on part de 0 (sans sécante)  => 2
On arrive à 41 possibilités …

2 : 3
4 : 11
6 : 41
8 : 153
….

On a donc 2 fois la somme des termes précédents , plus le terme précédent, plus 2.

Cela peut s'apparenter à une sorte de suite de  Fibonacci avec :

f(N) = 4 f(N-2) – f(N-4) en prenant N pair

f(2)=3
f(4)=11
f(6)=41
f(8)=153
f(10)=571
f(12)=2131
f(14)=7953
f(16)=29681
f(18)=110771
f(20)=413403
f(22)=1542841
f(24)=5757961

 #7 - 17-06-2017 11:43:11

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Paavage avec des dominos

gwen parfait

 #8 - 17-06-2017 13:14:05

Spirou
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 489

pavage avzc des dominos

pour 2 * N je pense que c'est la suite de Fibonacci

Je cherche encore pour le 3 * N

 #9 - 17-06-2017 13:32:18

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

avage avec des dominos

Spirou
C'est bon pour l'instant smile

 #10 - 17-06-2017 23:32:20

Smok2k
Habitué de Prise2Tete
Enigmes résolues : 27
Messages : 13

pavage avec des dominps

1) Pour le premier cas, si on appelle (U(n)) la suite dont le n-ième terme correspond au nombre de pavage possible pour un rectangle 2*n, on commence par remarquer que U(1)=1, U(2)=2, U(3)=3, U(5)=5, on pense à la suite de Fibonacci.
Pour s'en persuader, on démontre par récurrence qu'un rectangle 2*(n+1) admet U(n)+U(n-1) pavages différents.

En effet, un rectangle 2*(n+1) est soit un rectangle 2*(n) auquel on ajoute un domino vertical, => U(n) pavages possibles, soit un rectangle 2*(n-1) auquel on ajoute deux dominos horizontaux => U(n-1) pavages possibles.

On a donc U(n)=U(n-1)+U(n-2), suite récurrente d'ordre 2, équation caractéristique : x²-x-1=0 dont une des racines est le nombre d'or et l'autre l'opposé de son inverse.

Je préfère ne pas écrire U(n) explicitement, c'est moche sans Latex roll

 #11 - 18-06-2017 00:40:18

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

pavage avec des dolinos

Pas besoin du terme général, la relation de récurrence suffit.
Une idée pour 3xN?

 #12 - 18-06-2017 08:02:59

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 6,004E+3

Pavaage avec des dominos

Une fois la récurrence trouvée l'OEIS donne une formule pour f(2n-2) :

f(2n-2) = 1/6 (3 (2 - Sqrt[3])^n + Sqrt[3] (2 - Sqrt[3])^n + 3 (2 + Sqrt[3])^n - Sqrt[3] (2 + Sqrt[3])^n)

 #13 - 18-06-2017 09:58:53

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Pavage avec des domions

exact, il suffit d'appliquer la méthode de résolution classique d'une équation récurrente linéaire avec son polynôme caractéristique, qui se démontre facilement grâce à l'algèbre matricielle par exemple...

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Si il y a 78 pommes et que vous en prenez 43, combien en avez-vous ?

Mots clés des moteurs de recherche

Mot clé (occurences)
Pavage domino (1) —

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete