Défi de la semaine
Avec \(100\) cartes numérotées de \(1\) à \(100\), on doit former des paquets de trois cartes de sorte que dans chaque paquet, le nombre d’une des cartes soit le produit des deux autres. Par exemple \(\{3, 32, 96\}\) est un tel paquet. Quel est le nombre maximal de paquets que l’on peut former ?
Solution du 4e défi de mai 2023
Réponse : le nombre \(3\,654\,712\) est en position \(2009\).
Puisque les nombres sont dans l’ordre croissant, tous les nombres qui commencent par \(1\) ou \(2\) se trouvent avant \(3\,654\,712\) et il y en a \(2 \times 6!\).
Également, les nombres qui commencent par \(3\) et dont le deuxième chiffre est \(1\), \(2\), \(4\) ou \(5\) se trouvent avant, et il y en a \(4 \times 5!\).
De même, en raisonnant sur les nombres commençant par \(36\) et dont le troisième chiffre est \(1\), \(2\) ou \(4\), il y a encore \(3 \times 4!\) nombres avant notre nombre.
En continuant compter suivant ce procédé, on montre qu’il y a au total \[(2 \times 6!)
+ (4 \times 5!)+ (3 \times 4!) + (2 \times 3!) + (2 \times 2!)=2008\] nombres avant le nôtre. Ainsi, le nombre \(3\,654\,712\) est en position \(2009\).
Post-scriptum
Le calendrier est publié aux Presses Universitaires de Grenoble, sous la direction scientifique de Romain Joly.
Crédits images
©JROBALLO / Adobestock
ÉCRIT PAR
Romain Joly
Maître de conférences - Institut Fourier de Grenoble
14h19
Bonjour
Soit a, b et c les trois cartes d’un paquet avec a < b < c. On veut donc axb = c et on a a^2 < c < 101 , donc a <= 10. Le cas a = 10 est impossible car on aurait au minimum b = 11 et c = 110. Le cas a = 1 est impossible car on aurait b = c. a peut donc prendre 8 valeurs entre 2 et 9 et donc 8 tas possibles au maximum. Par exemple : 9 x 11 = 99 8 x 12 = 96 7 x 14 = 98 6 x 15 = 90 5 x 19 = 95 4 x 23 = 92 3 x 31 = 93 2 x 47 = 94 Cordialement
17h02
Alors, de 2∗3=6 à 2∗50=100, ça fait 50−3+1=48 paquets possibles.
3∗4=12 à 3∗33=99, ça fait 33−4+1=30 paquets possibles.
4∗5=20 à 4∗25=100 ça fait 25−5+1=21 paquets possibles.
5∗6=30 à 5∗20=100 ça fait 20−6+1=15 paquets possibles.
6∗7=42 à 6∗16=96 ça fait 16−7+1=10 paquets possibles.
7∗8=56 à 7∗14=91 ça fait 14−8+1=7 paquets possibles.
8∗9=72 à 8∗12=96 ça fait 12−9+1=4 paquets possibles.
9∗10=90 à 9∗11=99 ça fait 11−10+1=2 paquets possibles.
On a au total 48+30+21+15+10+7+4+2=137 paquets possibles.
17h15
Bonjour
Ha, oui pour votre réponse, mais j’avais pensais à des paquets en même temps.
Cordialement
19h48
Ah ok !!!
C’est peut-être vous qui avez raison…
J’ai peut-être mal compris la question…
La question est plus belle avec votre réponse 🙂
21h48
Je n’ai pas la solution mais le problème me semble beaucoup plus complexe car on veut déterminer le nombre maximal de paquets ayant la propriété mais quand on a utilisé des cartes pour former un paquet, les nombres correspondant à ces cartes ne peuvent plus être ré-utilisés pour former de nouveaux paquets.
22h12
La carte 1 est exclue du partitionnement car aucun triplet ayant la propriété ne peut la contenir.
Il faut donc raisonner sur 99 cartes (2 à 100).
Avec 99 cartes et sans aucune considération sur les paquets formés, on ne peut former au maximum que 99 / 3 = 33 paquets de trois cartes.
Le nombre recherché est donc inférieur à 33.
Propriétés intéressantes à exploiter peut-être :
le produit maximum ne peut pas dépasser 100,
le nombre de plus grand de chaque triplet puisqu’il est le produit des deux autres nombres ne peut pas être un des nombres premiers entre 2 et 100.
13h44
Les triplets que nous cherchons sont de la forme (a, b, ab).
a et b ne peuvent être tous les deux supérieurs ou égal à 10.
Sans perte de généralité considérons que a est le plus petit nombre ; il ne peut donc varier qu’entre 2 et 9 soit 8 valeurs possibles (1 est exclu car il ne peut pas faire partie d’un triplet ayant la propriété recherchée).
Le nombre maximum recherché est donc inférieur ou égal à 8.
L’ensemble contenant les triplets (9, 11, 99), (8, 12, 96), (7,14, 98), (6,15, 90), (5, 19, 95), (4, 22, 88), (3, 28, 84) et (2, 29, 58) possède 8 éléments.
Le nombre recherché est donc égal à 8.