Conditon nécessaire et suffisante:

[invitea5ab8741]

Donner une condition nécessaire et suffisante portant sur n pour que l'ensemble [|1;n|] puisse être partagé en deux sous-ensembles de même somme.

Si n=3 : 1+2 =3 donc la propositon est vérifiée.

Mais comment démarrer ?
-----

[invitedb5bdc8a]

la somme totale est ?
ce doit être un nombre pair, ça c'est nécessaire
(par exemple n=5 ça ne marche pas)
est-ce suffisant ?

[invitea5ab8741]

Mais pourqoui n doit-il être nécessairement pair ?

[invitedb5bdc8a]

Mais pourqoui n doit-il être nécessairement pair ?

3 n'est pas pair.
C'est la somme totale qui doit être paire pour pouvoir être partagé en deux sous ensembles de même somme.

[A voir en vidéo sur Futura]

[invité576543]

Annulé... doublon

[invitea5ab8741]

Donc la somme des entiers de 1 à n est nécessairement paire.

Observation: pour n=3 : 1+2=3 => vrai
pour n=4 : 1+4 =2+3 =>vrai

Donc je dois uniquement raisonner sur la somme je pense.

[invite14e03d2a]

Salut,

Dire que la somme des n premiers entiers est pair est équivalent à dire que n est congru à 0 ou à 3 modulo 4.

Il y a deux cas possibles donc:
Si n est multiple de 4, c'est (relativement) facile de de séparer {1,...,n} en deux parties de même somme (tu l'as fait pour n=4).
Si n=4k+3, avec k un entier, on peut se ramener au cas précédent (assez) facilement.

Cordialement

[invitea5ab8741]

C'est super j'avais remarqué la même chose !

Bon je rédige et dites-moi s'il ya une erreur ou même un petit détail qui manque (je dois donner une rédaction parfaite au prof).

Pour n = 3 : 1+2 = 3.
Pour n = 4 : 1+4 = 2+3.
Pour n = 7 : 3+4+7 = 1+2+5+6.
Pour n = 8 : 8+6+4 = 1+2+3+5+7.

On conjecture que la proposition est vraie si et seulement si :
n congrue à 0 [4] ; ou : n congrue à 3 [4].

On va démontrer par récurrence que pour tout entier naturel n supérieur à 1 tel que n est congrue à 0 [4], la proposition est vérifiée.

Initialisation: Faite plus haut pour n=4.

Hérédité: Soit n fixé, tel que n congrue à 0 [4].
On suppose que la proposition est vérifiée par n.
Montrons que n+4 vérifie la proposition.

On a : 1+2+...+n+(n+1)+(n+2)+(n+3)+(n +4)=M+N+(n+1)+(n+2)+(n+3)+(n+4 ) ; où M et N sont les sous-ensembles vérifiant la propositon pour n.
Donc : M = N.

Or : (n+1) + (n+4) = (n+2) + (n+3).

Donc : M + (n+1) + (n+4) = N + (n+2) + (n+3).

Donc, si n (tel que n congrue à 0 [4]) vérifie la proposition, alors n+4 aussi.

Conclusion : Pour tout n congrue à 0 [4], la proposition est vérifiée.

On démontre de la même manière que la proposition est vraie pour tout entier naturel n congrue à 3 [4].

Montrons maintenant que tous les autres entiers naturels ne véfient pas cette proposition, c'est-à-dire pour n congrue à 1 ou à 2 [4].

Pour qu'un ensemble E d'entiers naturels soit divisible en deux sous-ensembles de même somme, il faut que la somme totale des entiers de E soit paire.

On note S(n) la somme des entiers naturels d'un ensemble pris pour tout n congrue à 0 [4].

Donc S(n) est paire.

Si m = n+1, alors m est congrue à 1[4] . Donc m est impaire.
La somme S(m) prise par les entiers de [|1;m|] est donnée par :

S(m) = S(n) + m.
Donc S(m) est impaire et ne peut être divisée en deux sous-ensembles de somme égale.
Donc pour tout entier naturel congrue à 1 [4], la proposition est fausse.

Si p = m+1; alors p est congrue à 2 [4] . Donc p est paire.

Ainsi : S(p) = S(m) +p => S(p) impaire.

Donc pour tout entier naturel congrue à 2 [4], la proposition est fausse.

Conclusion générale ...