Bonjour à tous ,

Je trouve qu'on passe beaucoup de temps à répéter la même chose

Pour éviter les longues promenades ...

Nodgim a proposé une simplification en ramenant la masse minimale à 1 et le total à 40 , c'est plutôt une bonne idée Les toutes petites parts sont sans intérêt , il faudrait donc arrêter d'en parler .

Voilà comment j'ai vu le problème . S'il y a une configuration de n galettes pour laquelle le partage est impossible , il en existe une avec un nombre minimal de galettes . On peut donc virer toutes les configurations avec des galettes dont l'une d'elles a une masse inférieure à 3 car elles induisent un contre-exemple avec moins de parts .

Après , l'idée de Gwen est la bonne mais il faut aller au bout ...

Vasimolo

La demo (enfin je crois) ne tient pas compte du nombre de morceaux initial.

Donc oui, on peut tomber sur des cas de 2 nombres complémentaires à 80 , 3 nombres complémentaires à 120 .... Ce sont des raccourcis utiles, mais ça reste des raccourcis.

La démo de Gwen tient le coup et il est clair que dès qu'on commence à détailler , ça devient vite un peu long .

Voilà comment j'avais fait ( ça ressemble beaucoup à ce qu'a fait Gwen ) .

On a [latex]n[/latex] galettes de taille au moins [latex]1[/latex] chacune dont le total fait [latex]4n[/latex] et on suppose qu'on ne peut pas les partager en [latex]n[/latex] parts équivalentes . Alors il existe un partage impossible de [latex]n[/latex] galettes avec [latex]n[/latex] minimum et notons [latex]p_1\leq p_2\leq \cdots \leq p_n[/latex] ce partage . Si [latex]p_1\leq 3[/latex] , en coupant un morceau de [latex]p_n[/latex] qu'on associe à [latex]p_1[/latex] on trouve un partage impossible à [latex]n-1[/latex] parts ce qui contredit le caractère minimal de [latex]n[/latex] on a donc [latex]3< p_1\leq p_2\leq \cdots \leq p_n[/latex] . Et maintenant on commence les découpages des premières parts :
[TeX]p_1=1+r_1[/latex] avec [latex]r_1>2[/TeX]
[TeX]p_2=(4-r_1)+r_2[/TeX]
[TeX]p_3=(4-r_2)+r_3[/TeX]
[TeX]\ldots[/TeX]
[TeX]p_k=(4-r_{k-1})+r_k[/TeX]
On continue les découpages tant que [latex]r_k>2[/latex] . On ne peut pas arriver jusqu'à la fin avec [latex]r_n>2[/latex] sinon en regroupant [latex]r_i[/latex] avec [latex]4-r_i[/latex] et [latex]1[/latex] avec [latex]r_n[/latex] on a un partage équitable . On continue donc jusqu'au premier indice [latex]k[/latex] pour lequel [latex]r_k\leq 2[/latex] ce qui revient à dire que [latex]\sum_{i=1}^kp_i\leq 4k-1[/latex] . Cette dernière inégalité montre que [latex]k<n[/latex] . Il reste à associer comme précédemment [latex]r_i[/latex] avec [latex]4-r_i[/latex] pour fabriquer [latex]k-1[/latex] parts de [latex]4[/latex] . Il reste un résidu de [latex]1[/latex] sur [latex]p_1[/latex] et de [latex]r_k[/latex] sur [latex]p_k[/latex] que l'on met ensemble pour obtenir [latex]1+r_k\leq 3[/latex] et que l'on complète à [latex]4[/latex] avec un morceau de [latex]p_{k+1}[/latex] ou et on a encore une fois un partage impossible avec moins de [latex]n[/latex] parts .

On arrive à une contradiction dans tous les cas .

La méthode est constructive à condition de ne pas chercher les découpes minimales .

Vasimolo

En fait, j'aurais dû faire un tableau avec une ligne à 41, par exemple, c'est à dire une config qui ne marche pas. Et en effet, on montre que ça ne marche pas non plus pour une config plus petite.

Attendons Mathias alors pour le programme.
Perso plus je lis les démos moins je les comprends... Je ne vois pas comment on peut être toujours sur qu'un gros morceau pourra en compléter un petit.

Shadock

Ah merci Nodgim je crois que j'ai compris mais c'est dur en ce moment..

Shadock

Es tu vérificateur de métier ?

Je corrige quelque peu et ça va marcher:

Démo
1) Je sais qu' avec 2 parts ça marche toujours.

2) soit A<B<C 3 parts dont le total fait 12.
Si A<3, on l'associe à une part de C tel A+ extrait de C=4. (ça marche toujours car C>4) et donc on élimine un 4 et A, et le problème est ramené à 2 parts.
Si 3<A<4, on coupe A=A1+A2 et on s'arrange pour faire
A1+extrait de B=4 et
A2+extrait de C=4.
ce qu'on peut toujours faire car B et C>A>3. Ensuite, comme on a ôté 2*4, on regroupe B et C. On a donc ramené à un problème à 1 part.

Et donc on a ramené le problème 3 parts à un problème 2 parts si A<3 et 1 part si A>3. 

Donc ça marche toujours avec 3 parts.

Par récurrence, on fait la même démarche avec 4 parts, ...n parts: Ramener le problème à n-2 parts si la part la plus petite est >3, ou à n-1 parts si la part la plus petite est inférieure à 3.

Et c'est fini.

Bon, là, je ne comprends pas ta réserve, ni le terme de récurrence forte..

La réserve tient au fait qu'à un moment de ton raisonnement, tu regroupes les deux parts qui restent en disant : il reste 40 donc 

Ensuite, comme on a ôté 2*4, on regroupe B et C. On a donc ramené à un problème à 1 part.

Sauf qu'à cette étape tu as deux morceaux pour une seule part à construire.

Si tu te retrouves dans la même situation en partant de 4 morceaux, il t'en restera 3 pour seulement deux parts à construire donc le début du raisonnement ne tient plus.  Il manque donc une astuce pour valider la récurrence qui consiste à ne pas faire un complément avec un morceau >4 même quand tu le peux parfois.

Si A<3, on l'associe à une part de C tel A+ extrait de C=4. (ça marche toujours car C>4)

Oui, ça marche toujours , mais ça met la suite du  raisonnement en défaut pour plus de 3 morceaux.

Bonjour!
Je dois avoir mal compris l'exercice car il me semble avoir un contre exemple, où bien j'ai compris l'exercice et je fais une grossière erreur de raisonnement. Dans les deux cas si quelqu'un peut m'aider?
Edit : Excusez-moi d'avoir repris les anciennes notations...

Voici mon raisonnement, basé sur l'éventuel contre-exemple :

Les galettes du pâtissier pèsent respectivement 12, 15, 28, 55, 90, 50,50, 50, 30 et 20 grammes,
Nous laissons de côté les 5 dernières galettes aisément partageables entre les 10 enfants et dont le poids est de 200g.
Le problème se ramène donc au partage équitable des 5 premières galettes.
Les galettes de 12 et 15 grammes ne pouvant être brisées car leur poids est inférieur à 20grammes elles resteront entières.
Je vois deux cas de figure : Soit les deux galettes reviennent au même enfant, soient elles atterrissent chez deux enfants différents. Dans le premier cas, 15 et 12 = 27, chaque part devra faire minimum 27 grammes.
Or (90 + 55 + 28)/9 = 19,2 et des poussières, inférieur à 27. J'en déduis que les deux parts ne reviennent pas au même enfant.
Mais pour que 12g rattrape 15 grammes on ne peut pas lui ajouter moins de 13 grammes sinon on complète 15 par moins de 10 grammes ce qui est en contradiction avec le fait qu'une galette ne peut engendrer des morceaux si petits.
Chaque part devra faire 25 grammes minimum, et sur les 200 g restants, si j'en enlève 50 pour les deux enfants dont nous avons parlé il nous reste 150g à partager entre 8 enfants. Or 150/8 = 18,75 <25.
Les parts ne pourront pas être équitables...

Ok. Merci beaucoup je viens de comprendre que j'ai fait n'importe quoi. J'ai pris le problème à l'envers, et forcément ça n'a pas aidé!
C'est vraiment très bête ce que j'ai dit.
Merci x)

Oui merci beaucoup, j'ai bien compris après coup que je n'avais pas du tout saisi l'énoncé. Le découpage de mon exemple est évident.
Mais le problème (maintenant que j'ai compris) est vraiment très intéressant!
Pour l'instant je suis sur un autre problème avec une amie, qui nous occupe déjà beaucoup, mais lorsque nous aurons terminé (si nous y parvenons) je reviendrai ici car celui-ci m'intéresse beaucoup.