Inscription / Connexion Nouveau Sujet
Niveau exercices
Partager :

Bonbons au miel

Posté par
Imod
10-10-22 à 11:56

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 .

Posté par
dpi
re : Bonbons au miel 10-10-22 à 12:23

Bonjour,
Quelle est la différence entre des bombons libres et des bombons agglutinés

Posté par
Imod
re : Bonbons au miel 10-10-22 à 12:26

Disons que si tu avais 31 bonbons agglutinés , ils ne rentreraient dans aucun tube

Imod

Posté par
ty59847
re : Bonbons au miel 10-10-22 à 14:08

 Cliquez pour afficher

Posté par
dpi
re : Bonbons au miel 10-10-22 à 16:18

Je vais tenter une approche...

 Cliquez pour afficher

Posté par
Imod
re : Bonbons au miel 10-10-22 à 19:11

@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

Posté par
dpi
re : Bonbons au miel 11-10-22 à 08:14

Bonjour,
Je viens de lire la solution de ty59847.

 Cliquez pour afficher
e

Posté par
Imod
re : Bonbons au miel 11-10-22 à 18:41

@Dpi : tu peux donner un exemple d'agglomérat de 310 bonbons impossible à ranger dans les 11 tubes ?

Imod

Posté par
dpi
re : Bonbons au miel 12-10-22 à 08:33

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

Posté par
Imod
re : Bonbons au miel 12-10-22 à 17:52

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

Posté par
Imod
re : Bonbons au miel 19-11-22 à 18:06

Pour ceux qui s'étaient intéressé au problème , il y a une solution complète ici   .

Je ferai un résumé si j'ai le courage , en attendant , bonne lecture

Imod

Posté par
Imod
re : Bonbons au miel 25-11-22 à 18:03

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 :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !