Probl`emes de Math´ematiques Bijections de Nk sur N ´Enonc´e Bijections de Nk sur N 1. Pour tout p de N, on note � Dp = {(x, y) ∈ N2, x + y = p} Sp = {(x, y) ∈ N2, x + y < p} (a) V´erifier que la famille (Dp)p≥0 constitue une partition de N2. [ S ] (b) Calculer le cardinal dp de l’ensemble Dp, et le cardinal sp de l’ensemble Sp. [ S ] 2. Dans cette question, on forme une bijection f de N2 sur N. Pour tout couple (x, y) d’entiers natruels, on pose f(x, y) = x + (x + y)(x + y + 1) 2 . (a) V´erifier que l’on d´efinit bien ainsi une application de N2 dans N. [ S ] (b) Montrer que pour tout (x, y) de N2, on a : sx+y ≤ f(x, y) < sx+y+1. [ S ] (c) On se donne deux ´el´ements (x, y) et (x′, y′) de N2, tels que f(x, y) = f(x′, y′). Montrer que x + y = x′ + y′, puis que (x, y) = (x′, y′). Conclusion ? [ S ] (d) Soit n dans N. Montrer qu’il existe un unique p de N tel que sp ≤ n < sp+1. [ S ] (e) Avec les notations pr´ec´edentes, calculer f(n−sp, sp+1−n−1). En d´eduire que f est bijective de N2 sur N. [ S ] (f) Quel est l’ant´ec´edent de l’entier 1000 par l’application f ? [ S ] (g) Interpr´eter graphiquement la signification de l’application f. [ S ] 3. Dans cette question, on forme (`a partir de f) une bijection g de N3 sur N. Pour tout (x, y, z) de N3, on pose g(x, y, z) = f(x, f(y, z)). (a) Montrer que g est une bijection de N3 sur N. [ S ] (b) Quel est l’ant´ec´edent de l’entier 1000 par l’application g ? [ S ] 4. On va g´en´eraliser ce qui pr´ec`ede en formant fk bijective de Nk sur N, pour tout k ≥ 1. On d´efinit donc les applications fk de Nk dans N de la fa¸con suivante : – Tout d’abord, f1 est l’application identit´e de N dans N. – Ensuite, si k ≥ 2 et si on suppose que fk−1 est connue, on pose : Pour tout (x1, x2, . . . , xk) de Nk, fk(x1, x2, . . . , xk) = f(x1, fk−1(x2, . . . , xk)). (a) V´erifier les ´egalit´es f2 = f et f3 = g. [ S ] (b) Pour tout k ≥ 1, montrer que l’application fk est une bijection de Nk sur N. [ S ] (c) Soit k un entier sup´erieur ou ´egal `a 2. Montrer que fk(0, . . . , 0, 1) = 1. En d´eduire l’ant´ec´edent de l’entier 1000 par l’application fk, pour tout k ≥ 4. [ S ] 5. La question (4) montre que pour tout entier k ≥ 1, il existe une bijection entre N et Nk. On rappelle que NN d´esigne l’ensemble des applications de N dans lui-mˆeme. Dans cette question, on va montrer qu’il n’existe pas de bijection entre N et NN. Il suffit bien sˆur de montrer qu’il n’existe pas de surjection de N sur NN. Pour cela, on raisonne par l’absurde et on suppose qu’il existe ϕ : N → NN, surjective. Pour tout n de N, l’application ϕ(n) : N → N est not´ee ϕn pour simplifier les notations. Conclure en consid´erant h : N → N d´efinie par : ∀n ∈ N, h(n) = ϕn(n) + 1. [ S ] Page 1 Jean-Michel Ferrard www.klubprepa.net c⃝EduKlub S.A. Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation individuelle et priv´ee sont interdites.