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 : 180

pavage avec des domunos

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?



Annonces sponsorisées :
  • |
  • Répondre

#0 Pub

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

Ebichu
Professionnel de Prise2Tete
Enigmes résolues : 49
Messages : 425

Pavage avec dess 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 : 180

Pavage avce des dominos

Parfait Ebichu!

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

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

Pavaage 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 : 180

pavage avec des sominos

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 : 5,627E+3

pavage avec des diminos

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 : 180

pavage avec ded dominos

gwen parfait

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

Spirou
Professionnel de Prise2Tete
Enigmes résolues : 48
Messages : 447

Pavagge avec des dominos

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

Je cherche encore pour le 3 * N


Il vaut mieux mobiliser son intelligence sur des choses betes que de mobiliser sa betise sur des choses intelligentes.

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

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

Pavage avc 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 deq dominos

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 : 180

Pvage avec des dominos

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 : 5,627E+3

Pavae 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 : 180

pavage avec des domibos

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 : 

Un berger a 10 moutons, ils meurent tous sauf 9, combien en reste-t-il ?

Sujets similaires

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