2 enigmes

[abel]

Bonjour à tous, j'ai 2 enigmes que je n'ai pas su résoudre :

- Peut-on trouver un ensemble E de 2000 nombres distincts entre 1 et 3000 tels qu'aucun de ces nombre de E ne soit le double d'un autre nombre de E ??
moi j'ai reusi à faire une liste de 1999 nombres mais ca ne prouve pas que c'est impossible.

-Soit un rectangle pavé (tous les pavés ont des cotés paralleles entre eux) en petits rectangles qui ont chacun pr côté un nombre entier et l'autre côté un nombre reel. Il s'agit de montrer que ce grand rectangle a pour côté un nombre entier et un nombre reel...(on m'a donné la réponse pr celui là et c'est qud meme tres tres difficile si on connait pas)

EDIT : j'ai une autre petite enigme tant que je suis là :

- Un roi qui va bientot mourir veut donner le trone à l'un des ses 3 fils :
pour cela il dispose de 5 boules : 2 blanches et 3 noires de meme aspect
Il réunit ses fils dans une salle leur montre les 5 boules et expose la règle :
- Celui qui affirmera avoir une boule noire sur la tete et qui aura raison aura le trone, sinon il sera décapité (dans le cas ou il se plante), puis il dispose les 3 boules noires sur la tete de chacun des ses fils (sans qu'ils le voient) et cache les 2 blanches puis il réunit les 3 fils.
30 minutes + tard l'un des fils affirme avc certitude avoir une boule noire sur la tête. Pourquoi peut-il en être sûr ?

J'en ai aussi une autre (mais je ne garantit pas la fiabilité de l'énoncé car ce pb me semble impossible à resoudre)
- Un homme meurt et se retrouve au purgatoire, il se trouve face à 2 portes : le paradis et l'enfer, et il y a 2 anges identiques, l'un dit toujours la vérité et l'autre ment toujours. Quelle unique question doit-il poser pour aller au paradis ??

[olivthill]

Pour le premier problème, je trouve aussi un maximum de 1999 éléments.

Avant d'expliquer ma méthode générale, voici une étude pour [1,30] :

Je garde les nombres impairs : 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29.
J'élimine les doubles des nombres impairs : 2,6,10,14,18,22,26,30.
Si je les avais gardés, il aurait fallu éliminer les nombres impairs dont ils ont les doubles, ce qui n'est pas plus intéressant.
Il reste les nombres pairs : 4,8,12,16,20,24,28.
On ne peut pas tous les garder, à cause des doublets {4,8}, {8,16}, et {12,24}.
Il n'est pas nécessaire d'enlever tous les éléments de ces doublets. Le nombre 8 étant commun a deux d'eux, et il suffit de l'enlever pour neutraliser deux doublets. On peut donc enlever 8 et 12 ou 8 et 24.
Il reste 1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,4,16,20,24,28.
J'ai donc 30/2 nombres impairs + floor(30/4) nombres pairs - 1 - 1 = 15+7-1-1=20.

Méthode générale

1. Soit D l'ensemble de départ (D est l'interval [1,3000] dans le cas initial).
Soit q la quantité d'entier dans D (q=3000 dans le cas initial).
Soit E l'ensemble d'arrivée.
2. Si D={1} alors E={1}, si D={1,2} E={1}, si D={1,2,3} E={1,3}, si D={1,2,3,4} E={1,3} et la solution est trouvée.
Sinon
3. Je garde les nombres impairs (2n+1) qui sont au nombre de floor(q/2)
4. Je retire les doubles des impairs (4n+2) qui sont au nombre de floor(floor(q/2)/2)
5. Je garde les autres nombres pairs (4n) qui sont au nombre de floor(q/2) - floor(floor(q/2)/2)
6. Je retire les nombres pairs de l'étape 5 qui sont des doubles d'autres nombres pairs de l'étape 5
en procédant à un changement de variable N=4n et Q=floor(q/4)
et en retournant à l'étape 1 de manière itérative.


Application informatique avec Excel

Je remplis la première colonne avec les nombres 1 à 3000.
J'utilise la macro VBA suivante pour retirer tous les éléments en trop

Code: Tout sélectionner

Sub remove_4n2_in_set()
row999 = 3000
sca1 = 4
Do
   For i = 1 To row999
      a = (i - 1) * sca1 + sca1 / 2
      If (a > row999) Then Exit For
      Cells(a, 1).Value = "x"
   Next i
   If (sca1 > row999) Then Exit Do
   sca1 = sca1 * 4
Loop
End Sub

Pour vérifier que le nouvel ensemble ne contient aucun élément qui est le double d'un autre, j'utilise le code suivant :

Code: Tout sélectionner

Function is_half_in_set(num, row0, row9, col) As Integer
is_half_in_set = 0 ' not found
For i = row0 To row9
   If (Not IsEmpty(Cells(i, col).Value) _
       And IsNumeric(Cells(i, col).Value)) Then
      If (num = Cells(i, col).Value * 2) Then
         is_half_in_set = i 'found
         Exit For
      End If
   End If
Next i
End Function

Function are_halves_in_set(row0, row9, col) As Integer
are_halves_in_set = 0 ' not found
For i = row0 To row9
   If (Not IsEmpty(Cells(i, col).Value) _
       And IsNumeric(Cells(i, col).Value)) Then
      num = Cells(i, col).Value
      If (is_half_in_set(num, row0, i - 1, col) > 0) Then
         are_halves_in_set = i 'found
         Exit For
      End If
   End If
Next i
End Function

Sub look_for_doubles_in_set()
   a = are_halves_in_set(1, 3000, 1)
   MsgBox (a)
End Sub

[abel]

Le truc c'est que rien ne prouve qu'on ne peut pas faire mieux, il faudrait montrer que c'est impossible d'en trouver 2000, moi aussi j'ai l'impression que ta methode (qui est la meme que la mienne est optimale mais bon ca prouve rien)...

[mystic]

salut,

pour celle du paradis : "Quelle porte me montrerait ton voisin si je lui demandais quelle est la porte de l'enfer ?" te donne la porte du paradis.

[olivthill]

Pour le problème de la succesion du roi, le fils qui affirme avoir une boule noire sur sa tête le fait parce qu'il voit que ses frères ne disent rien, et qu'il a confiance en leur jugement.

Le premier frère parlerait s'il voyait des boules blanches sur les têtes des deux autres, puisqu'alors il aurait automatiquement une boule noire sur sa tête. Il y a donc au moins l'un des deux autres qui à une boule noire sur sa tête. Idem pour le deuxième frère.

Le troisième frère qui est le prince qui se prononce voit deux boules noires, et pourrait en déduire qu'il a une boule blanche sur sa tête. Mais si c'était le cas, alors le deuxième frère aurait déduit du silence du premier frère que c'était lui (le deuxième frère) qui possèdait la boule noire. Mais comme le deuxième frère reste silencieux, cela veut dire que ce deuxième frère voit une boule noire sur la tête du troisième et craint d'avoir une boule blanche.

[abel]

Ok pr l'enigme des princes, et merci pour celle de l'histoire du paradis, je pensais que c'était irresolvable...

[scelerat]

Le truc c'est que rien ne prouve qu'on ne peut pas faire mieux, il faudrait montrer que c'est impossible d'en trouver 2000, moi aussi j'ai l'impression que ta methode (qui est la meme que la mienne est optimale mais bon ca prouve rien)...

Il est facile de voir que si la construction est optimale dans chacune des classes ou et est impair, elle est globalement optimale puisque l'inclusion d'elements d'une classe ne change rien pour toutes les autres classes. Dans une classe, le maximum d'elements est obtenu en prenant les valeurs paires de i jusqu'a ce qu'on depasse 3000.
On a donc
{ 1, 4, 16, 64, 256, 1024} (= 1 + 1 + 1 + 1 + 1 + 1 elements)
{ 3, 12, 48, 192, 784] (= 1 + 1 + 1 + 1 + 1 elements)
{ 5, 20, 80, 320,1280} (= 1 + 1 + 1 + 1 + 1 elements)
....
soit
1500+375+94+ 23+ 6+ 1 = 1999 elements maximum