Divisibilité de sommes de d'entiers par un nombre premier.

[Teyva]

Bonjour à tous,

Je me permets de vous poser une question. Pour un devoir de probabilité et dénombrement une question s'intitule : "Soit E un sous-ensemble de {1, 2, . . . , (2^p)−2}. On note sE la somme des éléments de E. Combien de sous-ensembles E sont tels que sE est un multiple de p ? On suppose que s{} = 0.".

J'avoue être complètement bloqué et me perdre dans certains parterns relatifs au problème (notamment la divisibilité de (2^p)−2 par p).

Tout aide serait acceuillie avec admiration.

Merci beaucoup d'avance.

[lyceen95]

Quand on développe , on obtient toute une somme de termes, avec les coefficients du triangle de Pascal. Et en particulier, quand est premier, tous ces coefficients sont multiples de .
Si on applique ça avec et et premier, on obtient que une somme de termes, tous multiples de

Ensuite, ça se complique beaucoup. Tentons de décomposer.
Je vais noter la somme de tous les entiers de 1 à . est un multiple de .
Combien de sous-ensembles de U sont tels que sE vaut . Facile
Combien de sous-ensembles de U sont tels que sE vaut . Beaucoup moins facile, mais ça doit se faire. Par symétrie, ça nous donne aussi la réponse à la question : Combien de sous-ensembles de U sont tels que sE vaut
Etc ?

Au final, on peut se dire que parmi tous les sous-ensemble, '''statistiquement''', il y en a une proportion proche de qui auront multiple de .
Si est le nombre de sous(ensembles de U, quel est l'entier le plus proche de , et peut-être que c'est la réponse ??? En tout cas, c'est un ordre de grandeur cohérent, et c'est un moyen de contrôle.

[GaBuZoMeu]

Bonsoir,
Un point de détail :
"la divisibilité de (2^p)−2 par p" : que dit le petit théorème de Fermat ? (je suppose que est premier >2 ?)
Par ailleurs, si la question vient dans un problème, il y a peut-être avant des questions qu'il serait intéressant de commaître.

[Teyva]

Bonsoir,
Un point de détail :
"la divisibilité de (2^p)−2 par p" : que dit le petit théorème de Fermat ? (je suppose que est premier >2 ?)
Par ailleurs, si la question vient dans un problème, il y a peut-être avant des questions qu'il serait intéressant de commaître.

Malheureusement, c'est la seul question, mais je te remercie quand meme ! (:

[Teyva]

Quand on développe , on obtient toute une somme de termes, avec les coefficients du triangle de Pascal. Et en particulier, quand est premier, tous ces coefficients sont multiples de .
Si on applique ça avec et et premier, on obtient que une somme de termes, tous multiples de

Ensuite, ça se complique beaucoup. Tentons de décomposer.
Je vais noter la somme de tous les entiers de 1 à . est un multiple de .
Combien de sous-ensembles de U sont tels que sE vaut . Facile
Combien de sous-ensembles de U sont tels que sE vaut . Beaucoup moins facile, mais ça doit se faire. Par symétrie, ça nous donne aussi la réponse à la question : Combien de sous-ensembles de U sont tels que sE vaut
Etc ?

Au final, on peut se dire que parmi tous les sous-ensemble, '''statistiquement''', il y en a une proportion proche de $1/p$ qui auront $sE$ multiple de $p$.
Si $n$ est le nombre de sous(ensembles de U, quel est l'entier le plus proche de $n/p$ , et peut-être que c'est la réponse ??? En tout cas, c'est un ordre de grandeur cohérent, et c'est un moyen de contrôle.

Merci pour la reponse ! C'etait l'une de mes pistes, mais je ne savais pas comment la mettre en forme! Ton idee de proportion est vraimeent interessante. En codant la chose je suis arrive a peu pres a ce resultat la! Merci encore! (: