Quelques exercices d'oraux

[lapras]

Bonsoir,
quelques exos élémentaires,
1) (ENS paris 1999) Soit une partie non vide de et stable par addition. (c'est à dire , ).
Montrer qu'il existe un entier naturel et un entier tels que les éléments de supérieurs à sont exactement les multiples de supérieurs à .

2) (Oral ENS-paris PC)
Soient et deux entiers naturels non nuls et premiers entre eux.
Mq est le plus grand entier ne s'écrivant pas sous la forme de avec et naturels.

3) (oral ENS-lyon, option informatique)
On appelle configuration une matrice A de dimension à coefficients naturels. Si un élément est , on peut lui retrancher et ajouter à chacun de ses voisins immédiats (au plus quatre). Si est le résultat de cette transformation, on écrit , ou plus précisément .
a)Mq la relation termine. (c'est à dire que quelquesoit la configuration initiale et la suite des transformations effectuées, on arrive à une situation bloquée où tous les coeffs sont .

b)Mq la configuration bloquée obtenue ne dépend que de la configuration initiale. (quelle que soit la suite des transformations effectuées, on arrive à la même config bloquée)

lapras :happy2:

[ffpower]

La question 1 n était pas tres dure je trouve(etrange pour un oral d ulm)
Pour la 2(solution plutot courte,mais qui m a donné qd meme du mal):
Montrons que ab-a-b n est pas atteint.Si on avait ax+by=ab-a-b, on aurait by=-b modulo a,et comme b est premier avec a,ca donne y=-1 modulo a,autrement dit a divise y+1.En particulier,y>=a-1.De meme, x>=b-1,d ou ax+by>=2ab-a-b,absurde..

Maintenant,soit n>ab-a-b.Partons d une relation de Bezout quelconque du type au+bv=n.La solution générale de l equation ax+by=n pour x,y entiers relatifs est alors

x=u+kb
y=v-ka

ou k est un parametre dans Z.On veut trouver un tel k tel que x et y soient positifs.Autrement dit,on cherche k tel que

-au =< kab =< bv

Comme kab et bv sont des multiples de b, kab=
-a(u+1) < kab < b(v+1)

Autrement dit,on veut montrer l existance d un multiple de ab strictement compris entre -a(u+1) et b(v+1). Or:

b(v+1)-(-a(u+1))=au+bv+a+b=n+a+b>ab

Il y a donc au moins ab entiers strictement compris entre -a(u+1) et b(v+1), et donc on peut forcement trouver un multiple de ab entre ces 2 entiers, ce qui conclut la preuve..

Resultat amusant et etonnant en tout cas,je ne pensais pas qu il existait une formule aussi simple..

Pour le 3,j ai pas encore beaucoup reflechi,j ai montré assez facilement que l algo se terminait forcement,mais pas encore l unicité de la matrice finale..

PS:désolé pour mes "inferieur ou egal" un peu foireux, j avais la flemme de Latexiser..