Bonjour à tous
Un lot de N bonbons au miel vient de nous parvenir , nous ne l'avons pas détaillé mais nous sommes assurés de pouvoir le 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 ) .
N est inférieur à 330 mais quelle est sa valeur maximale ?
On blanke ou pas , comme on le sent
Imod
PS : les piles de bonbons et les tubes sont cylindriques , aucun piège à ce niveau .
@Dpi : on peut faire mieux .
@Ty59847 : c'est la bonne réponse et ça peut se justifier simplement sans distinguer tous les cas de figure .
Imod
@Dpi : tu peux donner un exemple d'agglomérat de 310 bonbons impossible à ranger dans les 11 tubes ?
Imod
Comme d'habitude (ou du moins assez souvent ) je change l'énoncé
Ici je disposais de 330 bonbons à ranger...
Je disais Gn = agglomérat de n bonbons
si nous avons 47G7= 329 bonbons agglomérés ,il n'y en a que 1 libre.
On sait que 4 G7 seulement peuvent entrer dans une boite.
Donc 4x7x11 = 308 et le malheureux libre soit 309.
Nous voyons bien que le 3G7 restent dehors (330-21=309).
J'aurais du raisonner dans l'autre sens ...
Ici tu as des circonstances atténuantes car le problème est vraiment tordu : trouver le plus grand N pour qu'on puisse ranger les N bonbons dans le pire des cas
Imod
Une petite démonstration très largement inspirée de celle de Namiswan .
Lemme : D'un lot de 58 bonbons ou plus on peut toujours extraire une partie contenant entre 28 et 30 bonbons .
Considérons un tel lot , on peut commencer par agglutiner les blocs de 1 , 2 ou 3 bonbons de façon à ce qu'il ne reste plus que des blocs de 4 à 7 bonbons et un reliquat de moins de 4 bonbons qu'on laissera de côté . Il reste au moins 55 bonbons et pas plus de 27 dans chaque type de bloc sinon le résultat serait immédiat : 7X4=28 , 6X5=30 , 5X6=30 et 4X7=28 : il y a donc au moins 3 types de blocs . On ajoute les blocs par ordre décroissant de taille jusqu'à dépasser 27 , si le total est inférieur à 30 c'est fini , sinon le total est compris entre 31 et 33 . On échange alors le plus gros bloc de la somme avec le plus petit restant . Cet échange nous amène entre 28 et 30 bonbons sauf si la somme était égale à 33 et la différence entre les tailles des blocs échangés égale à 2 . Dans ce cas , il suffit de pratiquer un nouvel échange entre le plus gros bloc de la somme et le plus petit non sélectionné pour amener le total dans la bonne fourchette .
Montrons maintenant par récurrence pour n>0 qu'un lot contenant au maximum 28n+2 bonbons peut toujours entrer dans n tubes .
C'est évident pour n=1 , supposons que la condition est réalisée pour n>0 .
Considérons un lot de 28(n+1)+2 bonbons . Il contient plus de 57 bonbons donc d'après le lemme , on peut extraire un nombre de bonbons compris entre 28 et 30 et le ranger dans un tube . Il reste alors au maximum 28n+2 bonbons à ranger dans n tubes ce qui peut se faire par hypothèse de récurrence .
En revenant au problème , la propriété précédente avec n=11 nous dit qu'on peut toujours ranger 310 bonbons Comme on ne peut pas en ranger 311 arrivant en 44 lots de 7 et un de 3 , la réponse à la question initiale est 310 .
Imod
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :