Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #26 - 25-08-2012 11:39:37

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,469E+3

Gâtea u55

Non, mais tu traites un cas final...

Si j'ai n morceaux dont la moyenne fait 40 g 

Un  fait entre 10 et 20 g
Un autre fait plus de 40g

Je les couple ce qui donne un morceau de 40g et un autre de n'importe quel poids , pas obligatoirement de 40g ou plus.

Ceci dit, je me retrouve avec un morceau de de 40g et (n-1) morceaux dont la moyenne fait toujours 40g du coup. Donc soit ces n-1 morceaux font tous 40g , soit l'un d'entre eux fait toujours plus de 40 g mais ce n'est pas obligatoirement le même qu'au début.

si j'ai n morceaux :  X1 , X2 , 19 et 44 = n x 40 

ça me donne  40 et 23 , X1, X2 = 40 + (n-1)x40 avec n-1 morceaux il y a donc un X >40

#0 Pub

 #27 - 25-08-2012 12:13:31

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

gâyeau 55

Bonjour à tous ,

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

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 smile 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

 #28 - 25-08-2012 12:39:38

MthS-MlndN
Hors d'u-Sage
Enigmes résolues : 49
Messages : 12,414E+3
Lieu: Rouen

Gâetau 55

gwen27 a écrit:

ça me donne  40 et 23 , X1, X2 = 40 + (n-1)x40 avec n-1 morceaux il y a donc un X >40

OK, mais on peut alors revenir de ce cas de figure vers un partage idéal, non ? Si c'est X1 qui fait plus de 40, X1-17 et X2 feront 80 à eux deux, plus qu'à couper un morceau ---- aaaah, attends, et si X1 fait 49 et X2 fait 48 ?
Bon, je retourne à ta démo, du coup.


Podcasts Modern Zeuhl : http://radio-r2r.fr/?p=298

 #29 - 25-08-2012 12:49:30

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,469E+3

gâteai 55

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.

 #30 - 26-08-2012 09:39:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

gâtrau 55

Plus je réfléchis à ce problème, et moins je vois le bout d'une possible démonstration globale. Et pourtant, il est certain qu'il existe, pour chaque config proposée, une infinité de solutions (on est dans le continu).

Vasimolo, sais tu s'il existe une démonstration ?

 #31 - 26-08-2012 10:10:52

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Gâtea 55

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

 #32 - 27-08-2012 19:11:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Gteau 55

Je reformule la démo à ma manière, telle que je crois avoir compris.

On établit un tableau de répartitions de par exemple 5 parts.
----a---b---c---d---e---
40-----x----x-------x--- 
40--x-----------x---x--
40--x--x---x-----------
40--x-----------x---x--
40--------------x----x--

les "abcde" sont les parts de départ et les 5 "40" sont les résultats du partage, la répartition se faisant aux croix (morceaux de 10 g mini).

Il est facile de montrer que cette configuration 5 parts peut être dégradée par une configuration 4 parts.

On suppprime par exemple la seconde ligne 40 et la part d. Ce faisant, il y a seulement à transférer dans a b d ou e, 3ème et 4ème ligne, la valeur de la croix des 3ème et 4ème lignes colonne d, pour conserver le total 40 sur ces lignes.

Comme on peut dégrader la nouvelle configuration 4 parts en une 3 parts, on peut aller jusqu'à l'unité.

La seule chose à laquelle il faut faire attention, c'est de ne pas supprimer une ligne qui éliminerait 2 colonnes en une seule fois, mais évidemment aucune configuration ne peut aboutir à éliminer 2 colonnes pour toutes les lignes, car il y a autant de lignes que de colonnes.

Ainsi, on peut dire que toutes les configurations à n parts sont héritières des config à n-1 parts, elles mêmes issues des config à n-2 parts, elles mêmes.... Car ce qu'on a fait dans un sens , de n vers n-1, peut être bien se faire de n vers n+1.

C'est une sorte de dépliage infini de la configuration "1 part" d'origine...

ça convient ?

 #33 - 27-08-2012 19:49:23

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

gâreau 55

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.

 #34 - 27-08-2012 23:33:26

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Gâtaeu 55

Désolé Nodgim , j'ai une vision plutôt géométrique mais tes graphiques ne me parlent pas .

Je donne un exemple de partage pour illustrer la méthode .

3,6 ; 3,7 ; 3,8 ; 3,8 ; 3,9 ; 3,9 ; 5,3 .

J'ai volontairement choisi des valeurs proches de 4 car les petites valeurs ou les grosses ne posent aucun problème .

Je coupe :

part 1 : 3,6=1+2,6 
part 2 : 3,7=1,4+2,3
part 3 : 3,8=1,7+2,1
part 4 : 3,8=1,9+1,9

Je m'arrête là car le 2ème morceau n'est pas strictement supérieur à 2 .

Je regroupe : 2,6+1,4=4 ; 2,3+1,7=4 ; 2,1+1,9=4 .

Il reste donc à partager : 1 ; 1,9 ; 3,9 ; 3,9 ; 5,3 en quatre enfants .

Je mets ensemble les deux premières parts que je complète avec un bout de l'une des autres .

Il reste donc : 2,8 ; 3,9 ; 5,3 à partager en deux .

On liquide la petite part avec un morceau d'une autre et ainsi de suite ...

Je n'ai pas d'affinité avec l'informatique mais tout ça doit pouvoir se programmer aisément .

Vasimolo

 #35 - 28-08-2012 14:31:24

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

hâteau 55

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

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #36 - 28-08-2012 18:14:27

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Gâteau 555

Je comprends mieux ta démarche avec ton exemple, mais ne peut on racourcir ?

Démo
1) Je sais que 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+C=4. (ça marche toujours car C>4)
Si 3<A<4, on coupe A=A1+A2 et on s'arrange pour faire
A1+B=4 et
A2+C=4.
ce qu'on peut toujours faire car B et C>A>3.

Et donc on a ramené le problème 3 parts à un problème 2 parts car on a pu éliminer A et un 4.

Donc ça marche toujours avec 3 parts.

Par récurrence, on fait la même démarche avec 4 parts, ...n parts.

Et c'est fini.

 #37 - 28-08-2012 18:42:35

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Gâteaau 55

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

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #38 - 28-08-2012 18:43:23

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Gâeau 55

Bonsoir Nodgim

Je ne vois pas trop comment tu fais marcher ta récurrence avec par exemple :

3,7 ; 3,8 ; 3,9 ; 4,6 .

Vasimolo

 #39 - 28-08-2012 19:29:17

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Gâteau 5

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.

 #40 - 28-08-2012 19:35:57

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

fâteau 55

J'ai l'impression que tu te rapproches petit à petit de ma proposition smile

Je ne suis pas vérificateur et je n'aime pas trop ce rôle mais si chacun parle tout seul sans écouter les autres sad

J'ai bien peur que la récurrence doive être forte ( c'est ce que Gwen et moi avons proposé ) .

Vasimolo

 #41 - 28-08-2012 19:53:43

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Gâteua 55

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

 #42 - 28-08-2012 20:06:00

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Gâteau 555

La récurrence simple ramène le cas n à n-1 , la récurrence forte le cas n à un entier quelconque inférieur à n .

Je n'ai pas regardé ton exemple en détail mais dans la méthode que j'ai détaillée , selon la somme des premières valeurs on peut avoir besoin d'utiliser 2 , 3 , 4  ou plus de parts .

Vasimolo

 #43 - 28-08-2012 20:10:16

gwen27
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 5,469E+3

Gâteaau 55

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.

 #44 - 29-08-2012 18:20:18

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

gâtezu 55

Je me suis rendu compte du bug peu de temps après avoir écrit...
J'en resterai donc à la démo Gwen+Vasimolo, pour l'instant.

 #45 - 04-09-2012 17:16:38

hippomint
Amateur de Prise2Tete
Enigmes résolues : 15
Messages : 6

âGteau 55

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...


dans la lune et/ou devant mon PC

 #46 - 04-09-2012 18:09:06

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 4733

Gâtea 55

Bonsoir

Pourquoi tu ne mets pas 28 avec 12 ? Après le reste est facile .

Vasimolo

 #47 - 04-09-2012 18:17:07

hippomint
Amateur de Prise2Tete
Enigmes résolues : 15
Messages : 6

GGâteau 55

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)


dans la lune et/ou devant mon PC

 #48 - 04-09-2012 22:13:48

godisdead
Expert de Prise2Tete
Enigmes résolues : 22
Messages : 639

Gâtau 55

Si on reprend ton exemple, tu donnes 12 et 15 au même enfant. Tu peux couper la part suivante en 13 + 15. Le 13, tu le donnes toujours à ton premier enfant pour faire 40.
Puis la suite est evidente !

 #49 - 05-09-2012 00:41:49

hippomint
Amateur de Prise2Tete
Enigmes résolues : 15
Messages : 6

GGâteau 55

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.


dans la lune et/ou devant mon PC
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pif, Paf et ?

Sujets similaires

Sujet Date Forum
P2T
Gâteau 129 par Vasimolo
11-11-2016 Enigmes Mathématiques
P2T
Gâteau 2 par Vasimolo
09-04-2010 Enigmes Mathématiques
P2T
Gâteau 78 par Vasimolo
28-05-2014 Enigmes Mathématiques
P2T
Gâteau 98 par Vasimolo
07-05-2015 Enigmes Mathématiques
P2T
Gâteau 103 par Vasimolo
02-08-2015 Enigmes Mathématiques
P2T
Gâteau 62 par Vasimolo
31-08-2013 Enigmes Mathématiques
P2T
Gâteau 92 par Vasimolo
07-02-2015 Enigmes Mathématiques
P2T
Gâteau 19 par Vasimolo
31-07-2010 Enigmes Mathématiques
P2T
Gâteau 58 par Vasimolo
19-12-2012 Enigmes Mathématiques
P2T
Gâteau 73 par Vasimolo
27-02-2014 Enigmes Mathématiques

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete