Se balader dans N²...

[Kikoo <3 Bieber]

Salut,

Un petit défi de dénombrement classique et bien sympa (Le titre est légèrement trompeur) :

Considérons le premier cadran d'un repère orthonormé avec des axes gradués selon N (On peut donc mettre l'ensemble des points de ce cadran en bijection avec N², mais ce n'est pas l'intérêt de l'exo).
Nous pouvons nous déplacer de point en point horizontalement ou verticalement. Chaque déplacement compte comme un pas.
Soient x et y de N, tels que xQuel est le nombre de chemins possibles en allant de O pour arriver à M, dont le premier pas est effectué vers le haut et ce sans toucher la première bissectrice ?

Bonne chance

Edit (modif question) : Ca risquait d'être trop facile en effet !
Edit 2 : Et je rajouterai que l'on ne peut se déplacer que vers le haut ou vers la droite.

[Nerra]

Hello,

Si on ne peut se déplacer que vers le haut et la droite, alors la réponse sera différente de l'infini ^^.

Il y a chemins possibles, je pense.

Nerra

[nodjim]

Problème plutôt usé, non ?

[Kikoo <3 Bieber]

Certes, mais ceux qui ne le connaissent pas peuvent y toucher, il nécessite pas mal d'astuce au bout d'un moment ;)

[Kikoo <3 Bieber]

Si c'est d'un indice dont vous avez besoin, en voilà un :

On prendra



Montrer que

PS : est la droite d'équation

[chan79]

salut
pour (a,b)=(6,10), le résultat est 2002. OK ?

[Kikoo <3 Bieber]

Salut Chan,

Edit : 2002 est bien la bonne réponse, bravo :)
J'avais fait une erreur de calcul.

Tu nous montreras bien ta méthode après que d'autres auront un peu cherché ?

[chan79]

Salut Chan,

Edit : 2002 est bien la bonne réponse, bravo
J'avais fait une erreur de calcul.

Tu nous montreras bien ta méthode après que d'autres auront un peu cherché ?

C'est d'accord

[Kikoo <3 Bieber]

Je vois que mon petit défi n'a pas trouvé d'autre preneur que Chan ^^

Je te propose donc de nous donner ta solution !

[Anonyme]

Je vois que mon petit défi n'a pas trouvé d'autre preneur que Chan ^^

En même temps, tu as vu le genre de défi que tu donnes ?

/!\ PAS ACCESSIBLE À TOUS LES NIVEAUX /!\ :zen:

[Kikoo <3 Bieber]

En même temps, tu as vu le genre de défi que tu donnes ?

/!\ PAS ACCESSIBLE À TOUS LES NIVEAUX /!\ :zen:

Chan serait donc hors course car vraiment trop trop trop fort ?

Je donne d'autres indices si tu veux !

[chan79]

Je vois que mon petit défi n'a pas trouvé d'autre preneur que Chan ^^

Je te propose donc de nous donner ta solution !

salut
Je me suis inspiré de la méthode généralement utilisée pour présenter les nombres de Catalan.
Il s’agit de dénombrer les plus courts trajets de l’origine à M sans toucher la première bissectrice, sauf en O, comme ci-dessous.
[img][IMG]http://img809.imageshack.us/img809/3975/az1.gif[/img]

On peut supposer que le départ se fait en D(0,1) et que la première bissectrice ne doit jamais être touchée.

Si on considère tous les plus courts trajets pour aller de D à M, sans autre condition, il y en a :
puisqu’il faut choisir a déplacements vers la droite parmi (a+b-1) déplacements.
Il faut donc dénombrer les trajets pour relier D et M qui ont au moins un point sur la première bissectrice. Le premier de ces points est le point vert ci-dessous. Soit T l’ensemble de ces trajets.
[img][IMG]http://img21.imageshack.us/img21/4589/az2.gif[/img]

A chaque élément de T, on va faire correspondre un autre trajet de la façon suivante :
Jusqu’au point vert, le trajet ne change pas, puis, on remplace la fin du trajet par son symétrique par rapport à la première bissectrice.
Pour le trajet ci-dessus, on obtient le trajet ci-dessous :


[img][IMG]http://img593.imageshack.us/img593/3613/az3.gif[/img]



On note T’ l’ensemble de tous les plus courts trajets reliant D à M’, symétrique de M par rapport à la première bissectrice.
On vérifie facilement que la relation qui, à chaque trajet de T, associe le trajet de T’, comme cela vient d’être expliqué, est une bijection.
Pour obtenir un élément de T’, il faut choisir (a-1) déplacements parmi (a-1+b).
Le cardinal de T’ est donc
Le nombre demandé est donc

[Dlzlogic]

Bonjour,
Ce type de calcul et de configuration me suggère un autre défi :
On appelle "distance de Manhattan" la distance la plus courte d'un point A à un point B, en suivant le quadrillage (cf. rues et avenues du quartier de Manhattan".
On cherche à réaliser un programme dont l'une des variables est la distance d'un point A à un point B.
On connait les positions de A et de B.
Il y a 2 hypothèses possibles :
1- on fournit au programme le plans des chemins possibles (les rues) pour aller de A à B. Le calcul va consister à cherche le chemin entre chaque intersection.
2- on juge que la précision sur la longueur exacte n'est pas la préoccupation principale, et on cherche donc une "formule approchée".

On préfère la seconde solution, question : quelle formule adopter ?

[leon1789]

On connait les positions de A et de B.
(..)
1- on fournit au programme le plans des chemins possibles (les rues) pour aller de A à B. Le calcul va consister à cherche le chemin entre chaque intersection.
2- on juge que la précision sur la longueur exacte n'est pas la préoccupation principale, et on cherche donc une "formule approchée".

On préfère la seconde solution, question : quelle formule adopter ?

Partons sur |x_A- x_B| + |y_A - y_B| avec les notations auxquelles tout le monde pense.

[Kikoo <3 Bieber]

Bravo Chan, c'est la méthode que l'on avait traitée en cours ;)

Pour ceux et celles qui n'ont pas compris la méthode, je pense qu'elle est déjà assez explicitement montrée. Et j'invite les amateurs à se documenter du côté des "chemins monotones" !

Encore merci Chan, pour cette élégante solution bien illustrée !