Chemins monotones dans le plan

[minouchette]

bonjour,

je suis en classe prépa et j'ai un petit soucis sur un exo de math (logique ^^) et j'aimerai bien recevoir un peu d'aide si c'est possible :we:

sujet:

on considère un plan rapporté à un repère orthonormé. Les coordonnées d'un point M sont noté x et y.
Q est l'ensemble des points de M de P dont les coordonnées x et y sont entières, positives, ou nulles.

Etant donnés deux points A et B de Q tels que B se trouve "au nord est de A"

On note C(A,B) l'ensemble des chemins monotones joignant A et B, et
N(A,B)= Card C(A,B)


questions:

on note D la première bissectrice. A et B sont tous les deux strictement au dessus de la bissectrice. B' est l'image de B par la symétrie orthogonal par rapport à D, et Cd(A,B) l'ensemble des chemins monotones joignant A et B en rencontrant D en au moins un point.

Partie A

a)Montrer que Nd(A,B) = N(A,B').
on construira une bijection entre Cd(A,B) et C(A,B')

b)en déduire le nombre N+(A,B) de chemins monotones joignant A et B sans rencontrer D

c)B étant un point de Q situé strictement au dessus de D, déterminer à l'aide des résultats précédents, le nombre de chemins monotones joignant O et B sans rencontrer D en dehors de O.


je n'arrive pas à démontrer la question a) grace à une bijection. En utilisant les longueurs je pense avoirs trouver mais ce n'est pas la consigne...

si vous pouviez m'aider ce serait gentils merci d'avance !!! :help:

[Ben314]

Bonsoir,
L'énoncé ne me parrait pas trés clair ("chemin" = chemin passant de (p,q) à un des 4 "voisins" de (p,q) dans Q ? "chemin monotone" = monotonie des changement d'abscice et d'ordonnée ?)
Pour le a) je pense qu'il faut utiliser un "principe de réflexion" c'est à dire associer à un chemin qui va de A à B EN COUPANT D le chemin qui "commence pareil" j'usqu'à ce que l'on coupe D puis qui s'obtient en faisant une reflexion d'axe D de la fin du chemin. (je ne sais pas si je suis trés clair...)
Il te reste à expliquer qu'il s'agit bien là d'une bijection...

Bon courage

P.S. Là où l'énoncé ne me parrait pas clair (par exemple) c'est que le fait que B soit au "nord-est" de A n'implique pas du tout que B' soit aussi au "nord-est de A"

[alavacommejetepousse]

bonsoir

pas tout compris mais on dirait bien les nombres de catalan

[nuage]

Salut,
c'est un exemple typique d'énoncé «rigoureux» qui finalement relèvent du blabla sans signification.
De façon triviale
Ce qui n'est bien entendu pas la réponse attendue. Car, comme l'énoncé ne le précise pas, il s'agit de chemin formé de segments de longueur 1 reliant un point de Q à un autre point de Q. Ou plus précisément de chemin sur un quadrillage.
Pour la question a)
Un chemin de A à B' coupe nécessairement D (par continuité)
Soit M le premier point de D sur un chemin de A à B'.
On prend le symétrique par rapport à D du chemin de M à B' : c'est un chemin de M à B. En concaténant le chemin de A à M et celui que l'on vient d'obtenir on a un chemin de A à B.
Il est facile de voir que l'on obtient ainsi tous les chemin de A à B qui touchent D.

[Ben314]

Bonsoir nuage,
C'est bien l'idée que j'avais, mais quelque chose m'échappe sur la notion de "chemin monotone". J'avais pensé que cela signifiait que les seule direction autorisées (de A vers B) étaient EST ou NORD.

Si c'est le cas (je n'en suis pas sur du tout) il y a un problème : le symétrique (par rapport à D) d'un chemin monotone n'est plus monotone.
(Et si on fait une croix sur le caractère "monotone" des chemins de A a B, il se met a y en avoir une infinité....)

Pense tu avoir compris le "monotone" ?

[nuage]

...
il y a un problème : le symétrique (par rapport à D) d'un chemin monotone n'est plus monotone.
(

Il me semble clair que le symétrique par rapport à D d'un chemin monotone est monotone.
En fait, tel que j'interprète l'énoncé les chemins monotones sont décrit par une suite de N (pour Nord) et de E (pour Est).
La symétrie par rapport à D échange les N et les E : un chemin monotone reste monotone.

[Ben314]

Je crois qu'il est grand temps que j'aille me coucher....................

[nuage]

Pour être, peut être plus clair.
Je suis convaincu que les chemins à considérer sont sur un quadrillage. En utilisant les notations par les points cardinaux un chemin se décrit par une suite de lettres N, S=-N, E, O=-E.
N étant la translation de vecteur (0;1) et E celle de vecteur (1;0)
un chemin est monotone croissant si il ne comporte que des N et des E.
Ik est facile de vérifier que la symétrie par rapport à D échange les N et les E ainsi que les O et les S.

[nuage]

Je crois qu'il est grand temps que j'aille me coucher....................

Moi aussi .................;

[minouchette]

Bonjour a vous deux,

Nuage vous avez annoncé:

Je suis convaincu que les chemins à considérer sont sur un quadrillage.

j'ai demandé a mon professeur ce matin et c'est effectivement le cas. De plus, comme vous l'avez si bien dis, on ne considère que les déplacements vers le nord et vers l'est.



Ben314, vous annoncez :

le fait que B soit au "nord-est" de A n'implique pas du tout que B' soit aussi au "nord-est de A".

je ne suis pas d'accord avec vous...


pour finir, pour la question a) en faite j'ai essayer de reprendre votre idée nuage mais je ne suis pas sure de l'avoir bien utilisé. pour ce la je me suis aidée d'un schéma... voici mon raisonnement (à critiquer) :

Soit X le point d'intersection entre un segment issus de A et la bissectrice D. X a été obtenu grace à un enchainement de déplacement Est et Nord comme l'oblige l'énoncé.

AB= AX + XB
AB'= AX + XB'

or, tous les points de D sont equidistants de B et de B' donc XB= XB' ainsi on a AB = AB' pour tout chemin joignant A à B en rencontrant D en au moins un point.

par contre je ne vois pas comment interprété mon résultat en une bijection donc je ne pense pas que ce soit la bonne méthode de raisonnement... :--:

please help !

[Ben314]

Boujour, minouchette.
Sans vouloir te vexer, il me semble que B:(2,10) est au nord-est de A(1,9) alors que B'(10,2) ne l'est pas.... mais, cela n'est pas génant car dans ce cas, N(A,B')=0.

En ce qui concerne ta preuve, je ne comprend pas trés bien ce que tu fait...
Il te faut construire une bijection entre les ensembles Cd(A,B) et C(A,B'). Pour cela, il faut que tu explique comment EN PARTANT D'UN ELEMENT DE Cd(A,B) on peut fabriquer un (unique) élément de C(A,B') puis montrer que la fonction ainsi définie est bijective.

Il me semble donc que la preuve doit commencer par :
"Considérons un élément de Cd(A,B), c'est à dire un chemin joignant A et B en rencontrant D en au moins un point et construisont, a l'aide de ce chemin, un chemin de A à B'....."
puis tu doit montrer que cette "construction" est bijective.

[minouchette]

rebonjour Ben 314 :we:

oui effectivement je l'avoue vous avez raison pour la position de A et B :lol5:

j'ai réfléchi au probléme, voici ma réponse :

alors dans un premier temps j'ai chercher a démontrer qu'il sagissait bien d'une bijection en démontrant une surjection puis une injection (comme le conseil la définition de bijection). pour cela:

appelons f la fonction qui associe a un chemin Cd(A,B) un chemin C(A,B').
c'est à dire qui associe un élément de l'ensemble I (moitié supérieur de la bijectrice) à un élément de l'ensemble J (moitié inférieur de la bissectrice).



Considérons un élément de Cd(A,B) c'est à dire un chemin joignant A et B en rencontrant D en au moins un point et construisons à l'aide de ce chemin, un chemin de A à B'.

B' étant séparé de A par D, C(A,B') passe automatiquement par D.
Ainsi les débuts des chemins Cd(A,B) et C(A,B') allant de A à D sont confondus.=>C(A,D)
De plus, tout élément I entre admet une image par f dans J (évident). (surjection)
cette image est unique. =>B' a un unique antécédent B par f.
Contenu du fait que chaque déplacement entre deux points d'un même ensemble s'effectuent soit de gauche à droite ou de bas en haut, il n'existe pas deux déplacements ayant les mêmes coordonnées. donc chaque déplacement est unique et admet ainsi une unique image par D.(injection)
Ainsi, si on appelle X un point de D, C(X,B) admet un unique antécédent par f qui est C(X,B'). f est donc une bijection.

D étant équidistant de B et B', Card C(X,B) = Card C(X,B')
d'où Card Cd(A,B)= Card C(A,B') = Nd(A,B)

c'est ça??

vous avez pas une petite piste pour m'aider pour la question b) svp??

[Ben314]

s.t.p. arrête de me vouvoyer (sans quoi je fait pipi par terre et je me roule dedans....na!)

c'set pas encore bien tip-top...

appelons f la fonction qui associe a un chemin Cd(A,B) un chemin C(A,B').
c'est à dire qui associe un élément de l'ensemble I (moitié supérieur de la bijectrice) à un élément de l'ensemble J (moitié inférieur de la bissectrice).

Si tu veut mon avis, je n'ai pas l'impression que cette phrase définisse bien grand chose... et surtout, j'ai l'impression que tu n'as pas bien compris les notations du problème : Cd(A,B) n'est pas UN chemin de A à B qui coupe la droite D, c'est L'ENSEMBLE DE TOUT LES CHEMINS de A à B qui coupent la droite D (idem pour C(A,B') ).

Pour définir une fonction de l'ENSEMBLE Cd(A,B) "vers" (ou "sur" ou "dans") l'ENSEMBLE C(A,B') tu dois écrire :

"Soit X un ELEMENT de L'ENSEMBLE Cd(A,B), c'est à dire un chemin de A à B coupant la droite D...."

(c'est sans doute plus simple de lui donner un nom) puis tu explique comment, à partir du chemin X tu fabrique un chemin Y qui est un ELEMENT de C(A,B').
Cette construction est celle dont je parle dans ma première réponse.

Ensuite, pour montrer que la fonction qui à X associe Y est bijective, plutôt que de montrer qu'elle est injective puis surjective, on peut faire les deux en même temps en expliquant comment connaissant le chemin Y, on peut retrouver le (seul) chemin X qui donne Y (c'est la construction donnée par nuage à la fin de son premier post)

Bon courage

[minouchette]

ok:

Soit J un chemin de A à B' passant par un point de D. On note M ce point de D. On prend le symétrique du chemin allant de M à B' par rapport à B : on obtient le chemin de M à B. En réunissant le chemin de A à M et le chemin que l'on vient d'obtenir, on obtient le Chemin de A à B. Ainsi on vient de montrer que l'on obtient par cette manière tous les chemins de A à B qui touche D. Chaque chemin ayant une seule image.
Pour chaque trajet de A à B passant par D on associe un trajet de A à B' d'ou Nd(A,B)=N(A,B').



c'est mieux?

pour la question 2 je pense avoir trouvé le raisonnement mais je suis pas très sure de savoir comment l'exprimer:

on peut calculer le nombre de chemin joignant A et B sans rencontrer D par le faite que ce nombre de chemin correspond à la différence entre le total du nombre de chemin joignant A à B et le nombre de chemin Joignant A et B en passant par un point de D. on peut exprimer cette idée grâce au binome de Newton:

k parmi n+1 = (k parmi n) + (k-1 parmi n)

nn? un petit coup de pouce serait bien venu :S

[Ben314]

C'est bon, à quelque point virgules prés :

Soit J un chemin de A à B' passant par un point de D. On note M ce point de D. On prend le symétrique du chemin allant de M à B' par rapport à B : on obtient le chemin de M à B. En réunissant le chemin de A à M et le chemin que l'on vient d'obtenir, on obtient le Chemin de A à B. Ainsi on vient de montrer que l'on obtient par cette manière tous les chemins de A à B qui touche D. Chaque chemin ayant une seule image.

1) Si tu part d'un chemin J de A à B', c'est à dire un élément de C(A,B'), tu n'as pas le droit de supposer qu'il coupe D (car ce n'est pas dans la définition de C(A,B'), tu dois montrer qu'il coupe D (ce qui est évident vu les positions de A et B')
2) Lorsque tu écrit "on note M ce point", c'est incorrect : il peut y avoir plusieurs points d'intersection (essaye de le voir sur un desssin). Comme tu doit complètement expliquer la construction du nouveau chemin, il faut préciser quel point d'intersection tu choisi (grosso modo, soit tu dit "le premier", soit "le dernier...")
3) la symétrie c'est par rapport à D (je pense que c'est une faute de frappe)
4) tu devrais écrire on obtient un chemin de M à B (là, c'est plus du français que des maths) puis un chemin de A à B.
5) Pour la fin, tu n'as pas "montré que l'on obtient par cette manière tous les chemins de A à B qui touche D". Tu as pour le moment construit un chemin de A à B qui touche D. Il faut expliquer que tu obtient ainsi TOUT les chemins de A à B qui touchent D et que chacun d'eux n'est obtenue qu'une seule fois (si c'était moi qui rédigait, je m'emmerderais pas trop, j'écrirais "il est clair que..." en faisant un dessin à coté : ca passe ou ca casse)

Pour la deuxième méthode, je pense qu'il faut commencer par calculer N(A,B) pour A et B quelconques, puis constater (c'est trés con) que, pour n'importe quel chemin de A à B, soit il coupe D, soit il ne coupe pas D !!!

[minouchette]

ok pour les modifs mais bon le principale c'est que j'ai compris ce qu'on me demandais ^^

pour la deuxième question, dans le cas général l'expression du nombre de chemin joignant A à B est:

y = le nombre de déplacement vertical pour aller de A à B
x = le nombre de déplacement horizontal pour aller de A à B

x parmi x+y ou y parmi x+y ce qui équivaut à : (x+y)!/ (x!*y!)

mais on me demande de déduire de la question précédente le nombre de chemin allant de A à B sans rencontrer D...

[Ben314]

Oui, mais c'est là qu'il faut écrire le truc complètement con :

Le nombre total de chemins de A à B (on sait combien il y en a)
=Le nombre de chemin de A à B qui coupent D (on sait aussi combien il y en a)
+Le nombre de chemin de A à B qui ne coupent pas D (ca, on sait pas, mais on va bientot savoir...)

[minouchette]

yes!! ok ok !! cool merci llol !!!!

bon il reste plus que la troisième question mais petit bug: à quoi sert le point Q???? j'ai pas bien pigé..

[minouchette]

oups!! nan autant pour moi, Q est un ensemble xD :hum: