Ranger les bonbons
Bonjour à tous
Un exercice que j’ai déjà proposé à un autre site, la
réponse vient assez vite mais comment la justifier simplement pour tous les blocs
réalisant ce maximum ?
Un lot de bonbons au miel vient de nous parvenir, nous ne
l'avons pas détaillé mais nous sommes assurés de pouvoir les ranger dans 11
tubes identiques de capacité 30. Pourtant il arrive régulièrement
que certains bonbons s'agglutinent (jamais plus de 7 par pile).
Quel est le nombre maximal de bonbons que nous avons
commandés ?
Merci d’avance pour les réponses Domi.
Réponses
-
Le maximum est inférieur ou égal à $310$ bonbons car avec $311=44\times 7 + 3$, on n'est pas certain de tout pouvoir faire tenir dans les tubes.Mais il reste à prouver que pour toute valeur inférieure ou égale à $310$ peut rentrer dans les tubes, ce qui n'est pas trivial ni même certain.[Edit] Si j'ai bien calculé, si on veut explorer toutes les possibilités lots de 1 à 310 bonbons, il y a 14.880.707.581 décompositions en paquets de 1 à 7 bonbons. C'est faisable de tout explorer numériquement, mais ça risque de prendre un moment.
-
Je pense en effet (sans certitude) que 310 est la réponse. Il serait joli de trouver une idée qui permettrait de l'assurer sans lister tous les cas.
Domi -
Salut:
Je ne suis pas sûr d'avoir très bien compris, mais je trouve $308$, pensant qu'il faut simplement faire le produit $28\times 11$ (le cas où il y a que des lots de 7). -
Et si j'ajoute un bloc de 2 bonbons à ton lot , tu pourras le ranger avec les autres ou pas ?
Domi -
Question bête: je n'ai pas compris l'énoncé, peux-tu reformuler?
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Je ne comprends pas l'énoncé, il est demandé un maximum, donc une situation qui maximise le nombre de bonbons, et la réponse est évidente : $330$, il suffit de n'avoir que des piles 2 max, ou 44 piles de 7 et le reste en piles de 2 ou des tonnes d'autres solutions.Il ne faut pas respirer la compote, ça fait tousser.
J'affirme péremptoirement que toute affirmation péremptoire est fausse -
Je précise l'énoncé.
On passe une commande de $N$ bonbons, on ne sait pas dans quel état cette commande va nous parvenir mais on est certain de pouvoir la ranger dans les tubes. Il est clair que $330$ ne convient pas ni même $311$ mais $310$ convient-il ?
Domi -
Donc, ce n'est pas le max que vous cherchez, avec votre énoncé ce n'est pas clair que $330$ ne convient pas.
S'il n'y a que des piles de 7, vous ne pourrez en ranger que $308$.
Cet énoncé n'est vraiment pas clair.Il ne faut pas respirer la compote, ça fait tousser.
J'affirme péremptoirement que toute affirmation péremptoire est fausse -
C'est toujours très confus. Je tente de débroussailler:1/ Les bonbons n'arrivent pas dans des tubes, c'est à l'arrivée qu'on les met dans des tubes?
2/ Les bonbons arrivent en vrac, mais certains se mettent ensemble par tas de 7 max, on n'arrive pas à les séparer avant de les mettre dans les tubes?Tentative de reformulation de la question: "Quel est le nombre maximum de bonbons que nous pouvons commander pour être certains que quelle que soit la configuration d'agglutination on arrive à les mettre dans les 11 tubes sans séparer les tas?"The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
En fait Soc a dit :Tentative de reformulation de la question: "Quel est le nombre maximum de bonbons que nous pouvons commander pour être certains que quelle que soit la configuration d'agglutination on arrive à les mettre tous dans les 11 tubes sans séparer les tas?"Il ne faut pas respirer la compote, ça fait tousser.
J'affirme péremptoirement que toute affirmation péremptoire est fausse -
Si je commande 330 bonbons et qu'ils arrivent en $47$ lots de $7$ et un bonbon libre, comment vais-je les ranger dans les tubes ? Je rappelle que l'on n'a pas déballé la marchandise et qu'on ne sait donc pas comment les bonbons sont agglutinés.
Domi -
J'imagine que ça veut dire "oui"
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Il y a toujours des non-dits dans ces problèmes, ranger veut dire "tout" ranger et si les bonbons arrivent en lots, on ne va pas les casser pour les ranger sinon il n'y a plus de question. Certaines interrogations frisent la mauvaise foi.
Domi -
Si vous le dites.Il ne faut pas respirer la compote, ça fait tousser.
J'affirme péremptoirement que toute affirmation péremptoire est fausse -
Le langage montre souvent ses limites. Une reformulation ou un simple "oui" eut été plus élégant qu'un jugement moral basé sur on ne sait quoi.
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Je n'avais tout simplement pas vu la reformulation, nos messages sont partis en même temps. C'est bien comme ça que j'avais vu le problème.
Domi.
-
Pour ton exemple
7-7-7-7 sept fois
7-7-7-6 deux fois
7-7-7-5-4 une fois
7-7-6-5-5 une fois.
Domi. -
On peut limiter l'étude aux blocs supérieurs ou égaux à 4. En effet notons $n$ le plus petit nombre de bonbons qu'il est possible d'agglomérer de façon à ce que l'ensemble n'entre pas dans les tubes. Soient $p_1\leq p_2\leq \dots \leq p_k$ les cardinaux des différents blocs alors par hypothèse $p_2,p_3, \dots ,p_k$ peuvent être rangés dans les tubes. Ce rangement fait, aucun tube ne peut accepter un bloc supplémentaire de taille $p_1$ donc $10p_1\geq 341-n$ et comme $n\leq 311$ alors $p_1\geq 4$.
Domi. -
A mon avis 310 fonctionne :
44x7 reste 2 que l'on combiné avec un 4x7=28 (reste 10 boîtes pour 40x7 ça rentre)
43x7 reste 9, que l'on combiné avec un 3x7=21 (reste 10 boîtes pour 40x7 ça rentre)
42x7 reste 16, que l'on combiné avec un 2x7=14 idem
41x7 reste 23, on Coline avec 1x7...
Si 40x7, reste 30, on remplit un tube avec....
Si moins de 40x7, ça me paraît de plus en plus simple mais je vais me coucher !
A finir demain -
Plus globalement je me demande si la stratégie "bête" qui consiste à classer les blocs en ordre décroissant puis à les déposer successivement et un par un dans les tubes 1 , 2 , 3 , 4 , 5 ,6 , ... ,10 ,11 ,1 ,2 ... ne fonctionne pas.
Domi.
-
Une idée serait de prouver que comme la décomposition $310 = 7\times 44 + 2$ peut être rangée dans les 11 tubes, toutes autres décomposition plus fine pourra être rangée dans les 11 tubes (en remarquant $310 = 7\times 44 + 2$ est la décomposition la moins fine possible)
Une décomposition est plus fine qu'une autre si elle a plus de blocs.
Cordialement. -
Chacun son idée, je précise la mienne.
On place les blocs successivement dans les différents tubes jusqu'à un possible blocage, on continuerait alors en passant au tube suivant. Arrivé au dernier tube on réordonne et on reprend la distribution. Il reste à voir pourquoi on peut toujours distribuer ainsi les 310 bonbons.
Domi.
-
Avec mon idée, on peut tenter une récurrence.
La décomposition à 41 blocs est ''rangeable''. Soit $p_n$ la propriété : ''la décomposition à n blocs est ''rangeable'' (pour un n tel que $41\lt n\lt310$ quelconque)''
Pour montrer $p_{n+1}$, il ne doit pas être difficile de montrer que $(\neg p_{n+1})\implies (\neg p_{n})$.
Cordialement. -
Je ne suis pas sûr qu'on y arrive par là, en ne prenant que des blocs contenant au moins 4 bonbons, on ne pourra donc jamais en agglutiner deux pour en faire un. Il reste bien sûr les possibilités de faire deux blocs avec trois, ... mais ça devient vite compliqué.
Domi. -
Bonjour
Un os pour les shtameurs :
$30.7.11=2.3.5.7.11$.
Y aurait-il de la primorielle dans l'air ?
Cordialement.
Paul
-
Domi a dit : https://les-mathematiques.net/vanilla/index.php?p=/discussion/2332259/ranger-les-bonbons[Inutile de recopier le message initial. Un lien suffit. AD]
De capacité 30 bonbons?
-
Un autre Alain va bientôt te dire : inutile de répéter un message précédent, il suffit de donner un lien
J'ajouterai qu'on peut aussi ne rien dire quand on n'a rien à dire.
Domi. -
-
Re
Pour participer:
Le cas de 44 cas blocs de 7 (plus 2) n'est ni plus ni moins remarquable que celui de 77 blocs de 4 (plus 2).
Cordialement
Paul -
J’ai lu 2 fois le fil et je n’ai toujours pas compris le problème… snifJe suis donc je pense
-
Je laisse à d'autres le soin d'expliquer, plus je le fais et moins c'est clair
Domi. -
Salut Domi
Merci de me répondre.
Pour ce qui est de la primorielle, ça frôle la plaisanterie: il se trouve que trois nombres apparaissent dans ton énoncé et qu'ils sont $30,7$ et $11$. Je n'ai pu m'empêcher de voir $2.3.5, 7$ et $11$ et de penser aux accros à la primorielle qui sévissent dans shtam. Pour autant, je n'ai pas décidé encore que cette remarque n'avait rien à voir avec ta choucroute (qui me plaît comme souvent).
Ce que j'ai compris (à tort peut-être):
On se donne un multiensemble $M$ de naturels appartenant à $[[1,7]]$. On note, pour tout $i$ appartenant à $[[1,7]]$, $k_i$ son nombre d'occurrences dans $M$. On conjecture que si la somme des éléments de $M$ est $310$ il existe une partition de $M$ en $11$ parties telle que la somme des éléments de chacune de ces parties est inférieure à $30$.
Avant de continuer éventuellement dans le vide, dis-moi si je suis dans les clous!
Amicalement
Paul -
D'accord, je ne lis jamais le shtam. Ta reformulation est correcte, j'espère qu'elle éclairera ceux qui sont encore dans le noir (je préfère tout de même l'originale un peu moins abstraite). Ce que tu relèves sur les primorielles est curieux mais comme tu le dis il faudrait trouver un lien avec l'exercice. Je continue à croire que le problème a une solution faisant l'économie d'une longue liste de possibilités mais le travail reste à faire.
Domi. -
@Domi, je pense que tu maitrises bien le sujet pour l'avoir longtemps regardé. Si tu voudrais bien travailler avec mon idée de récurrence, je suis sûr que tu arriverais facilement à lister les cas gênant et les écarter. J'ai l'impression que tu ne veux pas l'utiliser ? Alors bonne chance avec la tienne.
-
Puisque je suis dans les clous, je continue .
D'abord il a été noté, dès le début, que si la somme des éléments de $M$ était supérieure à $310$ on ne pouvait pas toujours "ranger les bonbons". L'argument fut que si l'on avait $44$ blocs de $7$ et un bloc de $3$ on était marron. Au nom de cet argument indéniablement correct, il y a eu une tendance à chercher à prouver la conjecture en additionnant des éléments de $M$ de façon à ce que le $M$ transformé par cet ensemble d'additions contienne un minimum d'éléments, le graal étant $44*7+1*2$.
Ce que je dis, c'est qu'il y a d'autres graals: le plus opposé à $44*7+1*2$ est $77*4+1*2$, mais il y a aussi tous les $(4k)*7+(7l)*4+1*2$ tels que $k+l=11$.
Bref, il n'est pas nécessaire d'"approcher" par des additions astucieuses le graal initial, il suffit de montrer qu'on peut "approcher" l'un des douze cités ci-avant.
-
Hypothèse de récurrence : pour n tubes on peut ranger toute quantité inférieure ou égale à 28n +2.On initialise à 1, et on montre qu'on peut extraire un tube de 28 ou plus pour se ramener à n-1.J'essaie de faire ça demain !The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic
-
Chacun développe ses idées sur un problème bien plus riche qu'il en a l'air.
@babsgueye : je suis les idées qui m'inspirent sans jugement de valeur, raisonner sur le nombre de blocs de 7 me parle plus que la récurrence sur le nombre de blocs, sans plus
Domi. -
Je suis parti comme Soc. Et pour faire marcher la récurrence, je montre que si on a plus de 2*28+2=58 bonbons divisés en blocs de 1 à 7, on peut trouver une somme de blocs entre 28 et 30. Pour faire ça je prends grossièrement une somme proche de [28,30] et je fais des petites rectifications. Cette dernière partie n'est pas très agréable, il y a plusieurs cas à traiter, mais je crois que ça marche. Je peux donner les détails quand j'aurai le temps si ça intéresse (et si je n'ai pas fait d'erreurs...)
-
Je crois en effet que cette idée est la bonne, la partie délicate est de montrer que de toute partition de $28n+2$ éléments en ensembles de taille inférieure ou égale à 7, on peut extraire une partie dont la réunion contient entre 28 et 30 éléments.
Domi. -
Les différents cas restant trop nombreux, j'ai tenté de faire varier d'autres paramètres que le nombre de tubes. Il est agréable de constater que l'on obtient la même borne $28n+3$ si on limite les blocs à $4$ bonbons, l'étude devrait en être grandement simplifiée.
Domi. -
Bon, vu que pas de solutions n'a été proposé depuis, je poste donc la mienne.
Je rappelle que je veux montrer qu'étant donné 58 bonbons ou plus divisés en blocs de 1 à 7, on peut sélectionner des blocs dont la somme est entre 28 et 30.
1)Préliminaires (pour limiter le nombre de cas à traiter)
-A chaque fois que l'on a deux blocs de 3 ou moins on les colle. Ainsi il reste à la fin au plus un bloc de 3 ou moins, dont on ne servira pas (mangeons le!).
On a donc maintenant 55 bonbons ou plus, divisés en blocs de 4 à 7.
-Si on a suffisamment de blocs du même type pour dépasser 28 bonbons, le problème se résout trivialement en utilisant que ces blocs (4 blocs de 7 donne 28, 5 blocs de 6 donne 30, etc.). On peut donc supposer que chaque type de blocs donne un total d'au plus 27 bonbons.
Une conséquence à noter est qu'il y a alors au moins 3 types de blocs, car 2 types donne un total max de 27+27=54 bonbons, pas assez.
2)La méthode
-On trie nos blocs par ordre décroissant. On les sélectionne dans cet ordre un par un jusqu'à dépasser 28.
-Si on tombe alors entre 28 et 30, super, on s'arrête là et on s'ouvre une bière. Sinon, le dernier bloc sélectionné est d'au plus 6 (car pas assez de blocs de 7 pour atteindre 28), et fait donc arriver à un nombre entre 31 et 33.
-On fait un premier échange: le plus gros bloc sélectionné, contre le plus petit bloc non sélectionné. La différence de bonbons entre les deux est d'au plus 3, et d'au moins 2 (car il y a au moins trois types de blocs). L'échange nous ramène entre 28 et 30 sauf dans un seul cas (on était à 33 et la différence est 2) qui nous amène à 31.
-Dans ce dernier cas où on est à 31 on va faire un deuxième échange. Il faut remarquer que si on laisse de coté les deux blocs échangés, il y a encore au moins deux blocs de types différents, car sinon il n'y aurait pas assez de bonbons: un seul type de blocs donne au plus 27 bonbon, on rajoute les deux blocs laissés de côté, c'est trop peu. On peut donc faire un deuxième échange entre deux blocs de différence au moins 1. Un tel échange nous ramène alors forcément entre 28 et 30, et c'est gagné.
Voilà. Ensuite, prouver qu'on peut ranger au plus 28n+2 bonbons dans n boites est une récurrence facile: c'est évident si n=1, et si n>1 on peut supposer que l'on a exactement 28n+2 bonbons (quitte à en rajouter artificiellement), on fait une sélection de 28 à 30 bonbons que l'on range dans une boite et on utilise l'hypothèse de récurrence sur les bonbons restants.
-
Je n'ai pas lu en détail, mais je fais globalement la même chose en partant des petits. Attention par contre ta récurrence ne fonctionne pas, c'est le fait de justifier que tu peux en extraire 28 à 30 qui est la difficulté. Il faut donc transformer ton cas particulier (58) en cas général (28n+2), la méthode sera à peu près la même .
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Une version pour n'étudier que les premiers cas consiste à rajouter dans l'hypothèse de récurrence que si le nombre de bonbons à ranger est maximum alors il existe une façon de les ranger pour laquelle au moins 2 tubes seront remplis de 28+. Cette fois le saut de récurrence devient simple, mais c'est l'initialisation qui est plus lourde.
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
parce que le plus gros vaut au max 6 et le plus petit au moins 3.
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic -
Soc: je ne vois pas pourquoi ma récurrence ne marcherait pas: le fait que d'en sélectionner entre 28 et 30 est certes la difficulté, mais c'est ce que j'ai prouvé au dessus.
Domi: je me suis ramené au cas où il n'y a que des blocs entre 4 et 7, donc la différence est au plus 7-4=3 -
D'accord , des blocs de 4 à 7 .
Domi -
Namiswan a dit :Voilà. Ensuite, prouver qu'on peut ranger au plus 28n+2 bonbons dans n boites est une récurrence facile: c'est évident si n=1, et si n>1 on peut supposer que l'on a exactement 28n+2 bonbons (quitte à en rajouter artificiellement), on fait une sélection de 28 à 30 bonbons que l'on range dans une boite et on utilise l'hypothèse de récurrence sur les bonbons restants.
The fish doesnt think. The Fish doesnt think because the fish knows. Everything. - Goran Bregovic
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 58 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres