Un peu de vaisselle entre les deux réveillons

[chan79]

Salut
Salut
Un exo qu'on m'a posé un jour:
De combien de façons peut-on ranger n tasses dans une boîte rectangulaire, sachant que les deux tasses placées aux extrémités ne peuvent pas avoir leurs anses tournées vers l'extérieur et que deux anses ne peuvent pas se croiser ?
Voici un rangement possible pour 4 tasses
[img][IMG]http://img705.imageshack.us/img705/5467/acz.gif[/img]

[img][IMG]http://img838.imageshack.us/img838/5499/adz.gif[/img]

[Kikoo <3 Bieber]

Hello Chan :)

Sympa le petit défi. Est-ce qu'on compte l'orientation de la tasse (4 façons d'en orienter une) comme étant un choix ?

[chan79]

Hello Chan

Sympa le petit défi. Est-ce qu'on compte l'orientation de la tasse (4 façons d'en orienter une) comme étant un choix ?

Pour chaque tasse (sauf les deux aux extrémités), il y a à priori 4 façons de mettre l'anse mais elles ne peuvent pas se croiser comme l'indique un dessin précédent.
Pour deux tasses, il y a deux possibilités:
[img][IMG]http://img819.imageshack.us/img819/8391/abz.gif[/img]

[nodjim]

2*3^(n-2) ?

[Kikoo <3 Bieber]

Oui, c'est bien ce à quoi je pensais

Donc on a deux façons de ranger la première tasse. Deux façons de ranger la dernière.
Maintenant, on veut voir de combien de façons ranger la deuxième tasse. Il y en a 3, car on ne peut pas se faire croiser deux anses. Pareil pour la troisième, etc jusqu'à la n-1ème, où on a cette fois 2 choix seulement.
On a donc façons de ranger les tasses ?

[chan79]

Oui, c'est bien ce à quoi je pensais

Donc on a deux façons de ranger la première tasse. Deux façons de ranger la dernière.
Maintenant, on veut voir de combien de façons ranger la deuxième tasse. Il y en a 3, car on ne peut pas se faire croiser deux anses. Pareil pour la troisième, etc jusqu'à la n-1ème, où on a cette fois 2 choix seulement.
On a donc façons de ranger les tasses ?

Pour 4 tasses, j'arrive à 28
Pour 3 tasses, c'est bien 8

[fatal_error]

allez, je me mouille :
pour n+2 tasses :

[Skullkid]

Salut, je trouve la même chose que fatal_error si les tasses sont numérotées, c'est-à-dire si on considère [BasDroite - HautGauche - HautGauche] et [BasDroite - BasDroite - HautGauche] comme deux rangements différents. Je cherche si on ne numérote pas les tasses...

[Kikoo <3 Bieber]

Je me disais bien que mon raisonnement était trop simpliste ^^ Mon modèle est incomplet. Je vais voir si ya pas autre chose...

[Skullkid]

Alors si on note et , je trouve que le nombre de façons de ranger les n tasses sans les numéroter est , .

Pour n allant de 2 à 6 ça donne :

- En numérotant : 2, 8, 28, 96, 328
- Sans numéroter : 2, 4, 17, 48, 174

[chan79]

Alors si on note et , je trouve que le nombre de façons de ranger les n tasses sans les numéroter est , .

Pour n allant de 2 à 6 ça donne :

- En numérotant : 2, 8, 28, 96, 328
- Sans numéroter : 2, 4, 17, 48, 174

Super, c'est la première réponse (en numérotant) qui était attendue.
Pour ma part, je suis passé par une application linéaire et une diagonalisation.

[Kikoo <3 Bieber]

C'est bon, je peux pas trouver la réponse ^^ Et en parlant d'algèbre linéaire, je n'en ai pas encore fait donc je vais rester silencieux !
J'attends de voir si qqun peut expliquer la démarche quand vous aurez fini les hostilités :p

[Skullkid]

Je suis également passé par une diagonalisation.

Pour Kikoo, l'idée c'est de chercher une relation de récurrence. Si je connais toutes les façons de ranger n tasses, puis-je en déduire toutes les façons de ranger n+1 tasses ? On se rend compte que non, parce que quand on range n tasses on impose à la n-ième d'être tournée vers l'intérieur, ce qui n'est plus le cas quand on range n+1 tasses (à ce moment-là c'est la n+1-ième qui doit être vers l'intérieur).

D'où l'idée de considérer conjointement le nombre de façons de ranger n tasses avec la première et la n-ième tournées vers l'intérieur (qui est le nombre qu'on cherche au final), et le nombre de façons de ranger n tasses avec la première tournée vers l'intérieur et la n-ième tournée vers l'extérieur. Essaye de trouver deux relations de récurrence couplées qui font intervenir I et E aux rangs n et n+1. C'est pour résoudre la récurrence qu'on a besoin d'un peu de technique algébrique.

[nodjim]

Pareil pour moi, pas trop le niveau pour ce genre de problème.
La démarche est celle ci:
Rn=un+vn un et vn 2 suites adjacentes telles que:
u2=2 et un=2u(n-1)+2v(n-1)
v2=2 et vn=u(n-1)+2v(n-1)
Après il faut avoir la technique pour transformer ça en une somme de 2 suites géométriques....

[chan79]

Je suis également passé par une diagonalisation.



D'où l'idée de considérer conjointement le nombre de façons de ranger n tasses avec la première et la n-ième tournées vers l'intérieur (qui est le nombre qu'on cherche au final), et le nombre de façons de ranger n tasses avec la première tournée vers l'intérieur et la n-ième tournée vers l'extérieur. Essaye de trouver deux relations de récurrence couplées qui font intervenir I et E aux rangs n et n+1. C'est pour résoudre la récurrence qu'on a besoin d'un peu de technique algébrique.

C'est exactement ce que j'ai fait. En reprenant les mêmes notations que skullkid:

On peut aussi avoir facilement et rapidement les premières valeurs avec un tableur ou en programmant une petite routine.

[Kikoo <3 Bieber]

Je suis également passé par une diagonalisation.

Pour Kikoo, l'idée c'est de chercher une relation de récurrence. Si je connais toutes les façons de ranger n tasses, puis-je en déduire toutes les façons de ranger n+1 tasses ? On se rend compte que non, parce que quand on range n tasses on impose à la n-ième d'être tournée vers l'intérieur, ce qui n'est plus le cas quand on range n+1 tasses (à ce moment-là c'est la n+1-ième qui doit être vers l'intérieur).

D'où l'idée de considérer conjointement le nombre de façons de ranger n tasses avec la première et la n-ième tournées vers l'intérieur (qui est le nombre qu'on cherche au final), et le nombre de façons de ranger n tasses avec la première tournée vers l'intérieur et la n-ième tournée vers l'extérieur. Essaye de trouver deux relations de récurrence couplées qui font intervenir I et E aux rangs n et n+1. C'est pour résoudre la récurrence qu'on a besoin d'un peu de technique algébrique.

D'accord j'ai saisi

Tout sauf un point : Il y a E_n façons de choisir le positionnement de n tasses sachant que la première est tournée vers l'intérieur et la n-ième vers l'extérieur. Mais on ne peut pas tourner les tasses extrêmes vers l'extérieur non ?

[fatal_error]

hello artillerie lourde pour moi.

On considere la matrice d'adjacence de schema:
bas gauche| haut gauche | bas droit | haut droit
On a donc
M =
1 1 1 1
1 1 1 1
0 1 1 1
1 0 1 1

ou 1 represente la liaison entre la presente tasse et la suivante.

le nombre de possibilite est la somme M^n.
On ne sinteresse qua la partie gauche de M (car derniere tasse externe tournee vers la gauche)
et a la partie bas, car premiere tasse tournee vers la droite

Si on multiplie M^n, on se rend compte qu on a la relation de recurrence
a_n(3,1)=4a_(n-1)(3,1) -2a_(n-2)(3,1)
il reste plus qu'a expliciter.

[chan79]

C'est exactement ce que j'ai fait. En reprenant les mêmes notations que Skullkid:

On peut aussi avoir facilement et rapidement les premières valeurs avec un tableur ou en programmant une petite routine.

Petit défi supplémentaire (un peu fou, c'est d'accord ...)
Trouver le nombre exact de dispositions avec 500 tasses (donner tous les chiffres, bien-sûr).
S'aider du PC, car à la main, c'est un peu long ... :zen:
on peut utiliser (avec les notations de Skullkid)


avec
et

[Skullkid]

Tout sauf un point : Il y a E_n façons de choisir le positionnement de n tasses sachant que la première est tournée vers l'intérieur et la n-ième vers l'extérieur. Mais on ne peut pas tourner les tasses extrêmes vers l'extérieur non ?

Vois comme un auxiliaire de calcul. Sa valeur n'est pas demandée puisqu'il correspond à un nombre de configurations "interdites", mais pour connaître les rangements autorisés de n+1 tasses, on a besoin de connaître les rangements valides de n tasses ET les rangements interdits de n tasses puisque rien n'interdit à la n-ième tasse d'être tournée vers l'extérieur.

Par exemple 3 tasses peuvent se ranger suivant [HautDroite - HautDroite - BasGauche], bien que [HautDroite - HautDroite] ne soit pas un rangement autorisé pour 2 tasses.

chan79 : je trouve un nombre à 266 chiffres, mais la marge est trop petite ):

[Kikoo <3 Bieber]

Quelque chose comme ça ? J'ai pris les formules de Skullkid :



PS : je ne savais pas comment forcer l'affichage numérique donc j'ai pris 300 digits ^^