Parmi 2n-1 entiers, la somme de n entiers ...
dans Arithmétique
Bonjour
Montrer que parmi tout ensemble de $2n-1$ entiers il existe au moins un sous-ensemble de $n$ entiers dont la somme est divisible par $n.$
Montrer que parmi tout ensemble de $2n-1$ entiers il existe au moins un sous-ensemble de $n$ entiers dont la somme est divisible par $n.$
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si $n$ est impair, il suffit de prendre $n$ entiers consécutifs car modulo $n$ la somme sera $1+2 + \dots + n = \frac{n(n+1)}{2} \equiv 0 \bmod n$ car $2$ et $n$ sont premiers entre eux.
Le cas $n$ pair est plus intéressant j'imagine.
On obtient une somme congrue modulo $n$ soit à $0+2+\dots +2n-2 = n(n-1)$, soit à $1+3+\dots+(2n-1)=n^2$ selon que le premier terme de cette série de $2n-1$ nombres est pair ou impair. Dans tous les cas cette somme est divisible par $n$.
Edit : autant pour moi, les entiers ne sont pas consécutifs.
Quelques preuves dont des élémentaires ici : http://www.tau.ac.il/~nogaa/PDFS/egz1.pdf
Si je comprends l'énoncé on ne cherche pas à trouver une configuration des $2n-1$ entiers mais, au contraire, la configuration est donnée et rien ne dit que les $2n-1$ entiers sont consécutifs ou obéissent à une répartition particulière autre que celle à démontrer.
Cela m'évoque une application du principe des tiroirs sans que je sache préciser cette pensée.
Ce problème m'a séché pendant deux mois. Ma démonstration correspond au décompte exposé dans le lien de @Gilles http://www.les-mathematiques.net/phorum/read.php?5,1766908,1766938#msg-1766938.
@Fin de Partie : Le principe des tiroirs est effectivement très utile, par exemple pour $n=3$, on travaille module $3$, et alors s'il n'existe pas cinq entiers dont la somme est divisible par $3$, alors au plus deux entiers sont $0,1$ ou $2$ modulo $3$ et nécessairement, par les tiroirs, on a un entier congru à $0$, le deuxième à $1$ et le troisième à $2$ modulo $3$ : contradiction.
D'abord, j'ai besoin de l'ensemble de toutes les parties à $p$ éléments de l'ensemble $\{1, 2, \cdots, 2p-1\}$ Je monte mon anneau de polynômes $A = \F_p[X_i, \ 1 \le i \le 2p-1]$ et je pose $S_I = \sum_{i \in I} X_i$ Attention, c'est du lourd : je (sic) calcule $S_I^{p-1}$. Et la somme $\sum_{\# I = p} S_I^{p-1}$ Cela fait 0, donc ``c'est bon''.
Si $n = 4$ je prends les $7$ entiers $\{5,\;9,\;13,\;6,\;10,\;14,\;7\}$: quelle est la bonne combinaison ?
Alain
On voit mieux modulo 4.
Dans l’ordre on a 5,6,7,9,10,13,14 transformé en 1,2,3,1,2,1,2 modulo 4.
Et on trouve 2+3+1+2=0 modulo 4 qui correspond à 6,7,9,10.
Par exemple,
et pour la question de babsgueye, il a 9 possibilités.
Dans le pdf, on peut lire que la preuve proposée par Edos, Ginzburg et Ziv est élémentaire et courte.
Or en parcourant le pdf, je n'ai vu que le cas où $n$ est premier.
Auriez-vous cette preuve élémentaire et courte?
Al-Kashi
Il faudrait que j'améliore mon anglais:-D.
Al-Kashi
J'ai bien compris qu'il suffisait de prouver le résultat pour un $n$ premier. j'ai aussi compris la conséquence du Lemme 2.2 pour prouver le résultat souhaité. Néanmoins, quelqu'un pourrait-il préciser le passage :
its not difficult to show that there is a $c\in\Z_p$ so that $B\cap (A+c)$ is a nonempty proper subset of $B$.
N'ayant pas vu encore l'utilisation du fait que $p$ soit supposé premier, je pense que c'est ici que l'on utilise cette hypothèse, non?
Al-Kashi
J'avais commis ce pdf il y a 10 ans... La même 'idée apparaît dans le pdf en anglais plus haut.
lien vers le pdf
Bien cordialement,
Ritchie
En lisant cela Cauchy-Davenport-lemma avec une traduction et une compréhension approximative je ne comprends toujours pas où l'hypothèse $p$ premier est utile?
Al-Kashi
Je n'ai pas lu la démonstration, mais est-ce que plus généralement on ne peut pas dire :
Montrer que parmi tout ensemble de $2n-1$ entiers il existe au moins un sous-ensemble de $n$ entiers dont la somme est égale à $p$ modulo $n$ pour tout $p\in [\![1; n]\!]$.
Quelqu'un voit-il un contre-exemple ?
J'ai aussi séché comme toi Yves de longues heures en cherchant une preuve.
J'ai d'abord prouvé aisément qu'il existe toujours une somme contenant au plus $i$ termes de la séquence $(a_1,a_2,...,a_{2n-1})$ nulle modulo $i$ pour toute valeur $i\leq 2n+1$.
On a donc en particulier une somme nulle modulo $n$ et contenant au plus $n$ termes.
J'ai ensuite essayé de construire une somme contenant exactement $n$ termes mais sans succès.
Al-Kashi
Al-Kashi