DEFI 54 : Les 100 000 jetons.

Posté par minkus minkus

Bonjour à tous.

Suite à une forte demande de la part de certains membres j'ai décidé de donner plus souvent 4 étoiles aux enigmes, à commencer par ce défi. La suite nous dira peut-etre que c'était exagéré pour celui-ci.

On dispose de 100 000 jetons numérotés de 2 à 100 001. Attention !

On souhaite classer tous ces jetons en 3 groupes en respectant les deux conditions suivantes :

1. On prend les jetons dans l'ordre de leur numéro : 2, 3, 4 ... etc

2. Si les jetons numéros p et q (non nécessairement consécutifs) sont dans un groupe alors le jeton numéro pq n'y est pas.
Par exemple si les jetons 2 et 3 sont dans le même groupe alors le jeton numéro 6 est obligatoirement dans un autre groupe.

Est-il possible de classer les 100 000 jetons ?

Si vous pensez que oui alors vous indiquerez une répartition possible des jetons.
Pour simplifier la lecture des réponses, vous pourrez indiquer des  ensembles de nombres sans les énumérer un par un. Par exemple vous pourrez dire que vous mettez dans le groupe 1 tous les nombres de 3000 à 3561.

Si vous pensez que c'est impossible alors vous indiquerez le numéro du dernier jeton que vous avez réussi à classer.

Bonne réflexion.

minkus

Posté par nobody (invité)

A mon avis, cette énigme mérite ses 4 étoiles.

Dans un premier temps, on va essayer de ne placer dans ces 3 groupes que les jetons numérotés par des puissances de 2 ( à ), soit 17 jetons seulement. A la main, ou avec l'aide de l'informatique, on se rend compte qu'il est impossible de réaliser un tel défi jusqu'à la puissance 16 de 2; cela n'est possible que jusqu'à seulement.
Gr1: , , ,
Gr2: , , ,
Gr3: , , , ,
Le défi demandé n'est donc pas possible avec les jetons.

Si on trouve une solution qui utilise tous les jetons jusqu'au numéro , alors nécessairement ce sera la meilleure. Si ce n'était pas la meilleure, cela voudrait dire qu'il existe une solution placant le jeton numéroté par , ce qui est faux d'après la remarque précédente.
Voilà donc une solution qui place tous les premiers jetons, qui est donc la meilleure solution :
Gr1: à , à , à , à
Gr2: à , à
Gr3: à
On vérifie facilement que cette solution vérifie les conditions de l'énoncé.
Le dernier jeton alors placé est celui numéroté , soit 16383.

Posté par Nofutur2 Nofutur2

Tout d'abord, j'ai considéré que si p et q étaient égaux, la propriété étaient toujours vérifiée, donc p² n'est pas dans le groupe de p.
Je commence par travailler avec les puissances de 2.
J'essaie de trouver quelles puissances de 2, il est possible de classer. Je trouve plusieurs classements possibles jusqu'à 2¹³ inclus. Par contre, 2¹⁴=16384 n'est pas classable.
Par exemple :
Dans le groupe 1, je peux classer 2 à la puissance : 1, 4, 7, 10 et 13
Dans le groupe 2, je peux classer 2 à la puissance 2, 3, 11 et 12
Et dans le groupe 3, je peux classer 2 à la puissance 5, 6, 8 et 9.
(Il suffit de vérifier que la somme de deux éléments d'un groupe n'appartient pas à ce groupe.)

On en déduit facilement (par l'absurde) que tous les nombres strictement inférieurs à 16384 peuvent se décomposer en facteurs premiers dont la somme des exposants est strictement inférieure à 14.
Si je place les nombres premiers dans le même groupe que le 2¹ (dans le groupe 1 dans mon exemple), je pourrai donc classer tous les nombres inférieurs à 16384 de la même manière que les puissances de 2 en assimilant chaque nombre premier à 2.
Par exemple A= 12726 = 2 * 3 * 3 * 7 * 101 pourra être classé dans le groupe 3, comme 2⁵.
Il est donc impossible de classer tous les nombres de 2 à 100001 puisque 2¹⁴=16384 n'est pas classable.
Le dernier jeton classable est le 16383 .

Posté par chaudrack chaudrack

bonjour et merci pour cette énigme assez corsée..

Même si je ne suis pas sur de savoir ce que veut dire



Ma réponse est oui, il est possible de classer les 100 000 jetons.

J'ai alors considéré que l'on devait placer les numeros dans l'ordre jusqu'a ce qu'on y arrive plus, changer de groupe puis continuer jusqu'a ce qu'on y arrive plus etc, etc..

J'obtiens ainsi les classements suivants:

les nombres de 2 à 5 (inclus) = groupe 1
Les nombres de 6 à 41 (inclus)= groupe 2
Les nombres de 42 à 83 (inclus)= groupe 1
Les nombres de 84 à 7139 (inclus)= groupe 3
Les nombres de 7140 à 14279 (inclus)= groupe 1
Les nombres de 14280 à 85679 (inclus)= groupe 2
Les nombres de 85680 à 100001 (inclus)= groupe 1

Pour récapituler, on a:

Groupe 1:

les nombres de 2 à 5 (inclus) + Les nombres de 42 à 83 (inclus) + Les nombres de 7140 à 14279 (inclus) + Les nombres de 85680 à 100001 (inclus)

Groupe 2:

Les nombres de 6 à 41 (inclus) + Les nombres de 14280 à 85679 (inclus)

Groupe 3:

Les nombres de 84 à 7139 (inclus)


Je ne pense pas m'être trompé..

Voili voilou

@ plus, Chaudrack

Posté par Fractal Fractal

Bonjour, je ne suis pas certain d'avoir vraiment compris l'énoncé mais bon... (c'est la première condition qui me gène ainsi que le "non nécessairement consécutifs")

Voici ma réponse trouvée à la main au bout d'une ou deux heures de tâtonnements :

C'est possible.

Groupe 1 : 2 3 4 5 7 9  48->62   tous les multiples de 6 ou de 8 entre 63 et 95   9312->18623
Groupe 2 : 6 8  10->47   tous les non multiples de 6 ou de 8 entre 63 et 95   18624->100001
Groupe 3 : 96->9311


Pour vérifier que ma réponse correspond bien à l'énoncé :

Groupe 1 :
On divise ce groupe en trois parties : (2 3 4 5 7 9)  (48->62   tous les multiples de 6 ou de 8 entre 63 et 95)   (9312->18623)
On vérifie facilement que le produit de deux nombres de la première partie n'est pas dans le groupe 1.
Le produit d'un nombre de la première partie avec un de la deuxième est dans [96,855], donc n'est pas dans le groupe.
Le produit d'un nombre de la première partie avec un de la troisième est supérieur ou égal à 18624, donc n'est pas dans le groupe.
Le produit de deux nombres de la deuxième partie est compris entre 2352 et 8930 donc n'est pas dans le groupe.
Enfin, le produit d'un nombre de la troisième partie avec un de la deuxième ou troisième partie est clairement bien trop grand.

Groupe 2 :
On divise ce groupe en trois parties : (6 8)  (10->47   tous les non multiples de 6 ou de 8 entre 63 et 95)   (18624->100001)
6*8=48 n'est pas dans le groupe.
Le produit d'un nombre de la première partie avec un de la deuxième est un multiple de 6 ou de 8 et est compris entre 60 et 760 donc il n'est pas dans le groupe.
Le produit d'un nombre de la première, deuxième ou troisième partie avec un de la troisième partie est supérieur à 111 744 donc n'est pas dans le groupe.
Le produit de deux nombres de la deuxième partie est compris entre 110 et 8930 donc n'est pas dans le groupe.

Groupe 3 :
Le produit de deux nombres du groupe 3 est supérieur à 9312 donc n'est pas dans le groupe.


Il suffit ensuite de vérifier que tous les nombres de 2 à 100001 apparaissent bien une fois chacun et le tour est joué.

En espérant ne pas avoir mal interprété l'énoncé...

Merci pour l'énigme

Fractal

Posté par plumemeteore plumemeteore

Dans le premier sac : tous les jetons de 316 à 100001 ainsi que les nombres premiers 2, 3, 5, 11, 13, 17.
Dans le deuxième sac : tous les jetons de 18 à 315.
Dans le troisième sac : le reste (4, 6, 8, 9, 10, 12, 14, 16).

Votre suggestion de grouper les nombres consécutifs a été le coup de pouce déisif pour moi.

Posté par savoie (invité)

Bonjour,

Ne visant pas le challege du mois, je tente une solution sans être sûr qu'elle est bonne.

Il ne me semble pas possible de classer en 3 groupes les jetons : le dernier jeton que j'ai réussi à classer est égal à 10^14-1 = 16383.

Merci pour cette belle énigme. Je posterai plus en détail ma méthode si nécessaire (et si elle est juste...)

Posté par Pr3dator (invité)

Bonjour, sans penser que c'est impossible, mais où la liste exhaustive des valeurs me parait bien trop complexe à afficher ici, je suis arrivé à tous les placer sauf 2. Aussi dans le cas où on peut prendre les jetons dans l'autre sens, je peux déjà proposer :
étape 1 :
- groupe 1 : 100001 à 316
- groupe 2 : 315 à 18
- groupe 3 : 17 à 4

restent 3 et 2.
étape 2 : En fonction de là où on les place, on doit changer les produits des valeurs avec 2 et 3 du groupe 1 pour les mettre dans le groupe 2.

Par contre, si on est obligé de les prendre dans l'ordre croissant, et qu'on fixe par souci de simplification,
"si groupe 1 impossible alors groupe 2, si groupe 2 impossible alors groupe 3" sans optimiser le processus, la valeur qui poserait problème en premier serait le produit des deux premiers nombre du groupe 3, ici 144 et 168, soit 24192.

Je n'ai pas résolu l'intégralité du problème, je peux avoir mon poisson, c'est vrai, mais il fallait que je réponde, pour ne plus en rêver la nuit ^^
Début de raisonnement juste au moins ? :p

Posté par gloubi gloubi

Bonjour,

On ne peut pas placer 100 000 jetons numérotés de 2 à 100 001 dans trois groupes. Le dernier jeton que l'on peut classer est le numéro 2 879.

La méthode:
- Tant qu'on peut mettre un jeton dans le premier groupe, on le fait.
- Sinon on procède de même pour le deuxième groupe.
- Si aucun des deux premier groupe ne convient, on teste le troisième.

En procédant ainsi, les plus petits jetons du premier groupe sont 2, 3, 4, 5
les plus petit du deuxième groupe sont 6, 8, 10 (2*3, 2*4 et 2*5),
les plus petit du troisième groupe sont 48, 60 (6*8 et 6*10).
Le premier jeton que l'on ne peut pas classer est le n° 2 880 (48*60).

Tout ceci est confirmé "par informatique", néanmoins je ne suis pas sûr de la répartition initiales des petits numéros. Faut-il mettre 2, 3, 4 et 5 dans le même groupe? Je pense que oui, mais sait-on jamais?

En tous cas, ce mois de juillet est riche en énigmes interessantes.
Merci minkus et puiséa.

A+,
gloubi

Posté par slaurent128 (invité)

Apparemment, on pourrait classer ces 100 000 jetons, mais peut-etre ai-je fait une erreur dans mon raisonnement.
Bon, j'me lance : (je donne pas mes explications, mais si qqn les veut, je les ai)


Notons A B C les 3 groupes, je trouve:
A = 2..5 ; 42..83 ; 7140..14279 ; 85680..100 001
B = 6..41 ; 14280..85679
C = 84..7139

Avec la notation x..y pour désigner tous les entiers entre x et y

Voila.
Merci pour cette énigme, un peu tordue, je trouve !

Posté par evariste evariste

Je pense qu'il est impossible de placer les 100 000 jetons.
Pour ma part , le dernier jeton que je peux poser est le 2879.

Posté par piepalm piepalm

Je pense qu'il est impossible de classer le jeton 24576=3*2^13; donc le dernier que l'on puisse classer serait 24575.
J'ai d'abord essayé avec les puissances de 2, mais c'est possible jusqu'à 2^23=8388608; j'ai ensuite essayé en y ajoutant les nombres de la forme 3*puissance de 2...
Mais la solution est peut-être à chercher sous la forme plus générale d'un produit d'une puissance de 2 par une puissance de 3...

Posté par lotfi lotfi

Bonjour
je sais que la réponse montre qu'elle est peut être fausse, car je ne peux pas l'ecrire toute complète mais je l'ai devant moi toute complète,comme vous allez le constaté il n'y a pas de nombre suivi pour mettre des groupes(intervalles de nombre).
J'ai mis les nombre premier dans un seul groupe et puis divisé les autres nombres tel que chaque foie que l'un des nombres ne peut pas être placé dans les deux groupes on le met dans le groupe des nombres premiers est celà n'a aucune influence sur ce groupe puisqu'il reste "légal" exemple de ces nombres il y a le nombre 6
pour les deux autres groupes voici un exp le 1er groupe contient:2-3-4-9-10-14-15-16-21-22-24-25-26-33-34-35-46-49-50-54-55-58-62-65-67-69-70-71-74-75-76-77-78-81-82-85-86-87-90-91-93-94-95-98-102....

Le deuxième groupe contient les nombres:8-12-18-20-28-30-32-36-38-40-42-44-45-48-52-56-60-63-64-66-68-72-80-84-88-92-96-99-100....

GRACIAS

Posté par veleda veleda

bonsoir,
je propose
G₁= l'union des  ensembles suivants{2,3,4,5},{42,43,.....83},{84x85......(84x85x2-1)},{84x85x12....100001}

G₂= l'union des ensembles suivants{6,7,.....41},{84x85x2,.........,(84x85x12-1)}

G₃= {84,..........(84x85-1)}.
ouf!je n'ose pas vérifier. bonne nuit

Posté par minkus minkus

Bonsoir,

Suite a un leger oubli dans l'enonce, j'ai decide d'accepter 2 types de reponses, celles qui ont considere p et q distincts (ce a quoi je m'attendais et alors le defi est possible) et les autres pour lesquelles le defi devient impossible.

Dans le premier cas il y avait plusieurs possibilites comme le montrent bien vos reponses.

Dans le 2e, certains semblent etre en desaccord et il m'est plus difficile cette fois de vous departager. D'un cote Piepalm tu affirmes pouvoir classer les puissances de 2 jusqu'a 2²³ sans donner la disposition alors que de l'autre cote Nofotur2 et Nobody disent ne pas pouvoir placer 2¹⁴ ??

Jusqu'a ce que ce litige soit eclairci, j'ai decide de ne pas vous noter car je ne parviens pas a demontrer qu'on ne peut pas placer 2¹⁴.

Pour les autres :

plumemeteore : tu sembles avoir mal compris quelque chose car les nombres 2, 316 et 2316 sont dans ton premier groupe.

gloubi et apparemment evariste : L'enonce ne dit pas qu'il faut remplir un groupe tant que cela est possible.

lotfi: 2, 49 et 98 sont dans ton premier groupe.

Concernant les bonnes reponses j'ai pris le temps de tout verifier mais il est possible que qque chose m'ait echappe. N'hesitez pas a le signaler.

minkus

PS : La condition 1 etait un moyen pour ceux qui n'arrivaient pas a placer tous les jetons de dire a partir duquel ca bloquait. Apres coup je me rends compte que le "non consecutifs" n'etait pas indispensable car sinon les nombres auraient ete p et p+1.

Posté par veleda veleda

bonjour,en essayant de placer les puissances de 2  j'avais réussi à placer toutes les puissances inférieures à 100001,(2²⁰>100001).
l'énigme était assez difficile mais intéressante,merci

Posté par piepalm piepalm


Si l'on considère que l'on peut avoir p=q, on ne peut effectivement pas classer 2^14, avec ci- dessous la répartition optimale des exposants
1 2 5
4 3 6
10 11 7
13 12 8
9
Si par contre on lit que p et q sont différents, ce qui a été mon cas (et le "non nécessairement consécutifs" ne me semblait laisser aucune ambiguité), la meilleure répartition des exposants de 2 est la suivante:
1 3 9
2 5 10
4 6 12
8 7 13
11 19 14
16 21 15
22 23 17
18
20
Mais comme elle va bien au delà des besoins, elle n'est pas unique, et c'est là mon erreur.
En fait, les quatre étoiles m'ont fait prendre le problème pour beaucoup plus compliqué qu'il n'est, et partir dans la mauvaise voie pour le résoudre, à savoir utiliser la décomposition en facteurs premiers, qui n'était ici d'aucune utilité

Posté par piepalm piepalm

Je m'aperçois que la lecture en colonne est difficile, voire erronnée: j'aurais du présenter en ligne mes deux tableaus ci dessus:
1 4 10 13
2 3 11 12
5 6 7 8 9
et
1 2 4 8 11 16 22
3 5 6 7 19 21 23
9 10 12 13 14 15 17 18 20
Avec mes excuses

Posté par savoie (invité)

Bonjour,

J'ai fait un raisonnement semblable à ceux de Nofutur et Nobody (d'ailleurs je donne le même résultat), et pourtant la remarque de Piepalm ne me semble pas fausse. Je m'explique (et je vais donc peut être embrouiller Minkus !)

Pour moi p et q sont forcément distinct (car il y a 100 000 jetons de 2 à 100 001 donc tous les jetons sont différents). On ne peut pas faire le calcul p x p.

Donc quand il s'agit des puissances de 2 (ou les puissances d'un nombre N premier), on peut obtenir la répartition suivante :
Groupe 1 : N puissance 1, 2, 4, 7, 10, 13, 16
Groupe 2 : N puissance 3, 5, 6, 12, 14
Groupe 3 : N puissance 8, 9, 11, 15
Dans ce cas, 2 ^ 14 est bon.

En revanche (c'est là où mon raisonnement mérite un poisson et, si je me trompe pas, ceux qui ont obtenu la même réponse que moi), j'ai fait un raisonnement qui n'est pas optimum.

J'ai considéré que chaque nombre devait être décomposé en facteur premier, et je fait la somme des exposants. Ma répartition en groupe est alors la suivante (semblable à celle de Nofutur) :
Groupe 1 : Somme des exposants égale à 1, 4, 10, 13
Groupe 2 : Somme des exposants égale à 2, 3, 11, 12
Groupe 3 : Somme des exposants égale à 5, 6, 7, 8, 9
En effet on ne peut plus utiliser la répartition d'avant, car le nombre 6, égal à 2x3, serait dans le même groupe que 2 et 3. Donc avec cette répartition, on n'arrive pas à placer 2^14, ce qui nous amène à dire que 16383 est le dernier que l'on peut placer. Mais comme je l'ai dit plus haut, ce n'est pas la répartition optimale donc j'ai droit à un poisson ! Minkus tu peux me retirer mon smiley... et bientôt je ne serai plus dans le top 25 !

Posté par chaudrack chaudrack

Bonjour!

D'après l'énoncé:



Est-il normal de considérer que P=Q?

Pour moi, l'énoncé stipule de manière claire que deux jetons ne peuvent avoir le même numéro puisqu'il y a 100000 jetons!

comment dans ce cas peut on considérer que P=Q?

Là je ne comprends pas! Peut-on me l'expliquer?

PS: je ne veux pas "descendre" ceux qui ont considérer l'énigme comme ça, mais cela fait plusieurs fois qu'un débat s'installe suite à une façon où une autre de considérer l'énoncé! Pour moi, il ne pouvait y avoir de confusion voilà tout!

à plus, Chaudrack

Posté par minkus minkus

Oui savoie je t'avais oublie dans le groupe de Nofutur2 et Nobody, donc je rectifie le tir et attribue donc un a tout le monde jusqu'a nouvel ordre. J'attends notamment le commentaire de Nofutur2. Pour nobody on fera sans car il est parti en vacances [b][/b]

Posté par minkus minkus

Il est vrai apres tout que l'on parle de jetons et pas seulement de nombres, c'est ce qui fait la difference et empeche le p*p.

Posté par Nofutur2 Nofutur2

Pour être clair et synthétique sur la correction de cette énigme, il faut uniquement savoir si tu acceptes la solution avec p=q. Comme cette hypothèse n'avait pas été interdite "explicitement", tu avais pourtant pris dans un premier temps la
décision de l'accepter.
Pour le reste, il me semble qu'il n'y a pas d'ambiguité : avec cette hypothèse, il n'est pas possible de classer 2^14.
Quant à la remarque de savoie, je pense que la fin de mon raisonnement n'est valable  que si on admet p=q. On ne peut, comme il le fait, constituer des groupes en supposant p différent  de q, puis utiliser la fin de mon raisonnement.

Posté par stokastik stokastik


Non seulement il y a un seul jeton par nombre et la condition 1 dit qu'on les prend dans l'ordre... celui qui considère les cas p=q a donc un peu oublié l'énoncé quand même.

Posté par stokastik stokastik



... ça ne fait pas longtemps que je m'intéresse (encore de loin) aux défis/énigmes, et il me semble que l'absence d'hypothèse explicite est un peu propre aux défis/énigmes non ? (c'est d'ailleurs un peu pour ça que j'aime pas trop)

Posté par gloubi gloubi

Bonjour,



Cela veut dire, me semble-t-il, que p et q désignent deux jetons, donc deux numéros différents par hypothèse, et non deux nombres entre 2 et 100 001, qui pourraient éventuellement être le même.

Je ne suis pas prof de lettres, mais bon...

A+,
gloubi