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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Domi
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).
Domi
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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
S'il n'y a que des piles de 7, vous ne pourrez en ranger que $308$.
Cet énoncé n'est vraiment pas clair.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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?
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Domi
Domi
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Domi.
Je vais encore chercher,
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.
Domi.
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
Domi.
Une décomposition est plus fine qu'une autre si elle a plus de blocs.
Cordialement.
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.
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.
Domi.
Un os pour les shtameurs :
$30.7.11=2.3.5.7.11$.
Y aurait-il de la primorielle dans l'air ?
Cordialement.
Paul
De capacité 30 bonbons?
J'ajouterai qu'on peut aussi ne rien dire quand on n'a rien à dire.
Domi.
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
Domi
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
Domi.
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.
@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.
Domi.
Domi.
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.
Domi
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
Domi