Défi 2.3

[namfoodle sheppen]

Soit n un entier naturel. Trouver le plus petit N tel que pour tout ensemble d'entiers de cardinal N on peut trouver une somme de n éléments de cette ensemble divisible par n.

[Blueberry]

Dans la somme à n éléments considérée, les n éléments ajoutés doivent-ils tous être distincts ?

[namfoodle sheppen]

oui sinon le défi n'en est pas un :id:

[alben]

Bonsoir,
J'ai suivi une démarche un peu identique mais je ne vois pas ce que le passage par les polynomes peut apporter

On peut raisonner dans Z/nZ et avec les mêmes notations que Rain'
On veut minimiser sous la contrainte :
, on a
Si n est premier, ça pourrait être un espace vectoriel
En tout cas, c'est intéressant

[aviateurpilot]

Dans la somme à n éléments considérée, les n éléments ajoutés doivent-ils tous être distincts ?

mais l'important ici c'est la congruence des nombres modulu n.
donc a la place de prendre le meme nombre deux fois (ce qui est interdit ) on peux prende par exemple et qui sont different mais :happy2:

[namfoodle sheppen]

euh ... en fait l'exo est difficile, on me l'a donné avec la solution . Si vous voulez je vous donne des étapes !

[yos]

euh ... en fait l'exo est difficile,

C'était donc ça.

[Scorbe]

Je soutiens Rain'...

J'aimerais autant ne pas avoir les étapes, au moins pour le moment. Encore un peu de réflexion, s'il vous plaît...

[yos]

Oui je pense comme toi que c'est 2n-1.
Si on imagine les 2n-1 entiers comme autant de tours alignées (la première empile jetons, ...tours négatives acceptées), on peut déjà raboter les tours en ne gardant que le reste des modulo n, mais on peut aussi les raboter en retirant 1 jeton à chaque tour (cela ne changera pas le reste modulo n d'une somme de n tours).
Après je m'enlise et je trouve rien.

[alben]

Bonsoir,
en reprenant l'image des n cases. On sait (remarque de yos) qu'une des cases doit être vide et qu'aucune ne doit contenir plus de n-1 éléments. Par ailleurs, toute permutation circulaire d'une solution est encore solution.

[Imod]

Uniquement pour mettre de l'huile sur le feu :we:

Il s'agît d'un exercice proposé par Erdös , il ne faut donc pas espérer une solution simple . Sans aide je ne suis pas sûr que quelqu'un puisse trouver mais je laisse namfoodle sheppen seul juge .

Imod

[alben]

On est bien d'accord, tes n cases contiennent au total N éléments (2n-1 si ton hypothèse est correcte comme je le pense). Chaque case correspond à un élément de Z/nZ. Si aucune case n'est vide, il est clair qu'en prenant un élément dans chaque case on aura une somme multiple de n, c'est le même raisonnement que tu appliques si une case contient n ou plus éléments

[fahr451]

Un peu de proba, on prend n petites cases, la ième case est intitulée "congru à i-1 modulo n".

On a 2n-1 allumettes dans la main et on doit les mettre dans les cases. Ca fait combien de possibilités ? :marteau:

juste cette question de dénombrement ( j'ai pas lu le reste notamment la case vide )et non de probas

combinaison avec répétition

2n-1 allumettes et n- 1 séparations verticales pour les n cases
une disposition est une façon de placer en ligne ces 3n-2 objets

on choisit la place des n-1 séparations
il y a (n-1 parmi 3n-2) façons

[alben]

Oui Rain' mais c'est le même raisonnement que tu utilises. Partant de 2n-1 éléments à placer dans n cases, tu affirmes que les configurations où une case contient n éléments ne sont pas à prendre en compte car solubles trivialement et tu les éliminent. De même celles qui ne contiennent pas de cases vides sont aussi solubles et doivent être éliminées (ton exemple contient précisément une case vide). Enfin ma remarque sur les permutations circulaires permet de ne s'intéresser qu'aux cas où la première case est vide.
Autrement dit, il s'agit de dénombrer combien de façons pour répartir 2n-1 objets dans n-1 cases (la première est vide) avec au plus n-1 éléments dans chaque cases. Ca fait beaucoup moins que ce que donnes Fahr

[alben]

Oui Rain' tu as raison

[namfoodle sheppen]

oui vous avez raison la réponse est bien 2n-1; Voici deux indices :
- montrer que si c'est vrai pour n et m, c'est encore vrai pour nm
- montrer que c'est vrai pour p premier

[Imod]

Notre ami namfoodle sheppen se montre plutôt avare pour les indices , la deuxième partie ( vraiment délicate ) peut se résoudre par l'absurde mais le mauvais sujet est particulièrement difficile à exhiber :doh:

Imod

[namfoodle sheppen]

pour ceux qui veulent la réponse voici un lien : http://prepas.org/forum/viewtopic.php?t=3532&postdays=0&postorder=asc&start=315&sid=9948419b2db0947edbcc64931d6b69e2
sinon pour la démonstration que le résultat est vrai pour les nombres premiers, il faut résonner par l'absurde : en considérant sur 2p-1 éléments la somme
S=somme (a(i1)+a(i2)+...+a(ip))^(p-1) où les ai décrivent l'ensemble des 2p-1 éléments. La contradiction consiste dans le fait que S est à la fois divisible par p et non divisible par p.

(pour le défi je suggère que fahr451 propose un nouvel exo puisque de toute façon le défi 2.2 n'avait pas été complètement résolu et le miens était inadapté car trop capillotracté :hein: ...)