Probleme janvier 2013

Soit n > 1 un entier. Prouver que parmi 2n − 1 entiers, on peut toujours en trouver n dont la somme est divisible par n.

peut tu écrire l'exercice par des symbole ??

.

Je ne suis pa si sur car je peux prendre k nombre de reste r1 n-k de reste r2 n-1-k' de reste r3 et k' de reste r4 2n-1 element il y a pa le mm reste

Prouve l’existence du k et k' dont tu parle car pour moi ce n'ai pas claire ou sinon donne moi juste un exemple( n=2 ou 3,avec un choix pr k et k' ).

N=4 pour 7 element je prend 2 qui ont pour reste 1 2 qui ont pour reste 2 et 3 qui ont pour reste 3 il y a pas 4 element qui ont le meme reste

Oui , tu as raison , ma faute est bête >< , l'ensemble des restes de n contient n nombres distincts et donc il n'existe que n-1 restes égaux .

Euh meme mes reste je les choisie n'importe comment pas forcement qu il y ai n-1 reste possible en fait je pense que c plus un probleme combinatoire que arithmetique car on dois prendre n element parmi 2n-1 et c(2n-1,n)>n donc d'apres le principe des tiroirs il y aurait au moin 2 somme qui ont le meme reste modulo n je peux soustraire l'une de l'autre mais la je fais a paraitre des termes negatif et j'ai pas n terme c'est ce qui est un peu embetant en fait

j'ai bien dis la division euclidienne , le reste est donc forcement compris entre 0 et n-1 ,c'est d'ici que je tire ma conclusion .

Ouii mais je veux dire qu on a pas forcement n-1 reste egaux ca depend de mes 2n-1 termes

oui,mon raisonnement est complètement faux ....

abdelbaki.attioui a écrit:

Soit n > 1 un entier. Prouver que parmi 2n − 1 entiers, on peut toujours en trouver n dont la somme est divisible par n.

Et si on travaille avec les classes de ces 2n-1 nombres dans Z/nZ, ça devient une classique application du principe des tiroirs à suivre...

Si quelqu'un puisse convertir cette solution en Latex ça sera bien aimable.

On utilise la factorisation en facteur premier de $n$. On commence par montrer que le résultat est vrai pour tout premier, ensuite on prouvera que le résultat est encore vrai pour tout produit de deux premiers, et par conséquent par récurrence qu'il est vrai pour tout $n$.

On considère que n est un nombre premier et en guise de contradiction on suppose que ce n'est pas possible. soit $a_1,a_2,...a_{2n-1}$ un ensemble de $2n-1$ entiers. On considère la somme $ \sum{(a_{i_1}+...+a_{i_n})^{n-1}} $ sur tous les sous ensembles S de $n$ éléments de l'ensemble en question. Par le théorème de fermat, $ \sum{(a_{i_1}+...+a_{i_n})^{n-1}}=\sum_{S} 1 \equiv\dbinom{2n-1}{n}\not\equiv 0\pmod{n} $. Développons terme par terme la grande somme $ \sum{(a_{i_1}+...+a_{i_n})^{n-1}} $ et on considère les coefficients de cette somme développée, on note que tout ensemble de $0<k<n$ des élements est exactement un sous ensemble $ \dbinom{2n-1-k}{n-k} $ sous ensemble de la somme. Puisque $ n|\dbinom{2n-1-k}{n-k} $, tous les coéfficients de cette somme est divisible par $n$, ce qui est une contradiction.

Maintenant on suppsoe que c'est vrai pour $ n=a,b $, on va prouver que le résultat est vrai pour $n=ab$. On considère ainsi un ensemble de $2ab-1$ entier, on choisit $2a-1$ élements parmi eux, on chosit ensuit parmi ces $2a-1$ élements $a$ élements qui sont divisibles par $a$ et on remet $a-1$ éléments qui restent dans l'ensemble premier. On refait cette opération $2b-1$ fois. On considère maintent les sommes $ s_1,...,s_{2b-1} $ les sommes de chaque ensemble de $a$ éléments. On divise chaque somme par $a$ pour construire $2b-1$ ensemble sous la forme de $ \frac{s_i}{a} $. Maintenant on a un ensemble de $2b-1$ élements, ce qui nous permet de choisir un ensemble de $b$ éléments tels que $ b|\sum^b{\frac{s_i}{a}} $, et par suite $ ab|\sum^b{s_i} $, on ainsi $ab$ entiers dont la somme est divisible par $ab$. Ce qui finit la d.montration.

Solution de Radouane_BNE :

Merci Humber, j'ai pas pensé à prendre un Screenshots du fichier pdf

radouane_BNE a écrit:

Merci Humber, j'ai pas pensé à prendre un Screenshots du fichier pdf

Quel fichier ?

Tu laisses rien passer Le fichier PDF généré par Texnicenter (le compilateur de Latex que j'utilise..)

bon solution Mr redouane_BNE mais je veut juste signalier que cette exercice est un theoreme du fameux Paul Erdos