Inscription / Connexion Nouveau Sujet

1 2 +


Niveau 3 *
Partager :

Joute n°103 : Ali Baba et les 40 valeurs

Posté par
godefroy_lehardi Posteur d'énigmes
11-03-13 à 11:06

Bonjour à tous,

Tout le monde croit qu'il a suffi au célèbre Ali Baba de prononcer « Sésame, ouvre toi ! » pour accéder au trésor des 40 voleurs. Mais la vérité est moins simple (et c'est pour ça qu'on la cache aux enfants ).

En réalité, le trésor était réparti dans 40 coffres numérotés de 1 à 40. Au cas où l'un d'entre eux perdrait sa clé, les voleurs avaient prévu un système permettant d'ouvrir les coffres un par un, mais à certaines conditions.

L'ouverture successive des coffres ayant pour numéros p et q permet l'accès à tous les coffres portant un numéro multiple de |p-q| (la valeur absolue de p-q).
Seule exception : si |p-q| = 1 alors on ne peut plus ouvrir d'autre coffre.
Par exemple, si on ouvre le coffre 15 puis le coffre 23, on aura accès aux coffres 8, 16, 24, 32 et 40.

Ali Baba possède la clé du coffre n°1, ainsi qu'un passe-partout qu'il ne peut malheureusement utiliser qu'une seule fois.
Il doit donc commencer par ouvrir le coffre n°1 puis un coffre de son choix (appelons-le X).
Ensuite, il aura accès à tous les coffres multiples de X-1 mais il ne pourra en ouvrir qu'un seul (appelons-le Y).
Le coup d'après, il aura accès à tous les coffres multiples de |Y-X|, et ainsi de suite.

Evidemment, on ne peut plus utiliser un coffre déjà ouvert.

Question : Dans quel ordre Ali Baba doit-il parcourir les coffres pour pouvoir en ouvrir au moins 30 ?
Donnez la liste des coffres ouverts dans l'ordre et en commençant par 1.
Si vous pensez qu'il est impossible de trouver une telle suite, précisez-le.

Joute n°103 : Ali Baba et les 40 valeurs

Posté par
masab
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 11:42

gagnéBonjour,

Ordre Ali Baba doit-il parcourir les coffres pour pouvoir en ouvrir au moins 30 :

[1, 3, 8, 5, 9, 4, 15, 11, 16, 25, 18, 7, 33, 26, 21, 40, 38, 2, 36, 34, 6, 28, 22, 12, 10, 24, 14, 30, 32, 20]

Merci pour cette belle énigme !

Posté par
Nofutur2
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 13:14

perduSi je comprends l'énoncé,
- il faut trouver une suite qui permette de "pouvoir" ouvrir en cumulé au moins 30 coffres.
- on ne compte pas les deux premiers coffres n°1 et n°X ouverts

Si j'ouvre le n°1 et le n°4, je peux ouvrir les 13 multiples de 3 : 3-6-9-12-15-18-21-24-27-30-33-36-39
Si j'ouvre le n°9 de la liste précédente, je peux ouvrir les 6 multiples de 5 non cités : 5-10-20-25-35-40
Si j'ouvre le n°20 de la liste précédente, je peux ouvrir les 2 multiples de 11 non cités : 11-22
Si j'ouvre le n°22 de la liste précédente, je peux ouvrir les 9 multiples de 2 non cités : 2-8-14-16-26-28-32-34-38

13+6+2+9 =30

J'ouvre donc dans l'ordre 1-4-9-20-22.

En espérant que j'ai bien compris l'énoncé et les contraintes du problème.

Posté par
panda_adnap
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 13:33

gagnéAli baba peut prendre tous les coffres
1
3
10
7
9
14
5
36
31
35
16
19
21
8
13
15
2
39
37
20
17
6
11
40
29
33
28
25
27
4
23
38
30
32
34
26
24
22
18
12

Posté par
ksad
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 13:37

gagnéBonjour
Joute difficile !
Mais je propose néanmoins la séquence suivante :

1 11 40 29 22  7 30 23 28 15 13  2 33 31  6 25 19 36 17 38 21 34 26  8 18 10 24 14 20 12 16 32

qui permet, sauf erreur, d'ouvrir 32 coffres, soit au moins les 30 demandés.
merci pour la joute et à bientôt!

Posté par
Chatof
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 14:23

gagné1 ; 3 ; 34 ; 31 ; 33 ; 28 ; 25 ; 9 ; 32 ; 23 ; 27 ; 20 ; 7 ; 26 ; 19 ; 21 ; 16 ; 5 ; 22 ; 17 ; 15 ; 2 ; 13 ; 11 ; 14 ; 6 ; 8 ; 10 ; 12 ; 4


Bonjour,
et merci Godefroy_lehardi

Posté par
manpower
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 14:36

gagnéBonjour,

après quelques essais, j'ai d'abord tenter de démontrer que c'était impossible... (27 multiples, cycles pairs et autres considérations)
le tout sans succès. Et pour cause...

Voici une solution, permettant d'ouvrir 31 coffres, obtenue par tâtonnement en utilisant le fruit de mes premières réflexions.

1-19-36-17-38-21-34-39-35-24-11-13-2-33-31-28-3-25-22-15-7-16-9-14-10-4-6-8-12-20-32 (ou même 40 pour le dernier coffre!)

A noter que, de toute façon, Ali Baba ne pourra pas ouvrir tous les coffres (par exemple le 37 ne sera jamais ouvert dans une solution maximale).
En revanche, je suis curieux de voir quel est le maximum possible! (par démonstration ou programmation)

Merci pour cette énigme très intéressante à chercher.

Posté par
dpi
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 16:09

perduBonjour,

Je   présume que l'on peut faire le choix des mulitiples à écarter sinon...

soit 1 puis 3
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34
31
9 15 21 27 33 36
5 25 35 40

Posté par
Chatof
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 16:11

gagné[1,3,34,31,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,6,8,10,12,4],[1,3,34,31,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,4,6,8],[1,3,34,31,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,6,4,8],[1,3,34,31,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,6,8,4],[1,3,34,31,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,8,6,4],[1,3,38,35,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,6,8,10,12,4],[1,3,38,35,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,4,6,8],[1,3,38,35,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,6,4,8],[1,3,38,35,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,6,8,4],[1,3,38,35,33,28,25,9,32,23,27,20,7,26,19,21,16,5,22,17,15,2,13,11,14,12,10,8,6,4]
10 solutions à 30  et aucune à 31

Posté par
fontaine6140
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 22:16

gagnéBonjour Godefroy,
Sauf erreur(s) et étant un peu pingre ...
01,03,10,07,09,14,05,36,31,35,
16,19,21,08,13,15,02,39,37,20,
17,06,11,40,29,33,28,25,27,04,
23,38,30,32,34,26,24,22,18,12

Merci pour la joute

Posté par
geo3
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 22:36

gagnéBonsoir
Voici une liste de 38 coffres :
1, 3, 8, 5, 9, 4, 15, 11, 24, 13, 22, 27, 20, 7, 39, 32, 35, 6, 29, 23, 18, 25, 28, 33, 40, 21, 19, 2, 17, 30, | 26, 12, 14, 16, 34, 36, 38, 10
Il manque le 31 et le 37
Merci pour cette joute
A+

Posté par
rschoon
re : Joute n°103 : Ali Baba et les 40 valeurs 11-03-13 à 23:21

gagnéBonjour à tous.

Ma réponse : 1 3 8 5 9 4 15 11 16 25 18 7 33 26 21 40 38 2 36 34 6 28 22 12 10 24 14 30 32 20

Merci pour l'énigme.

Posté par
Kidam
re : Joute n°103 : Ali Baba et les 40 valeurs 12-03-13 à 10:13

gagnéBonjour,

Une énigme qui une fois de plus m'a semblé bien difficile de résoudre à tâtons.
Je dois avouer que l'énoncé n'était pas facile à comprendre, car j'ai eu un doute sur le fait qu'en ouvrant le coffre |p-q|, nous avions le droit d'ouvrir TOUS les coffres multiples de |p-q| ou bien uniquement UN SEUL parmi ceux-là. Cependant, l'exemple du début semble bien indiquer qu'il s'agit d'un seul. De plus, dans le cas contraire, ce serait trop facile et l'énigme n'aurait pas trop d'intérêt.

J'ai fini par trouver une suite de 33 termes qui convient :

1 - 14 - 39 - 25 - 28 - 15 - 13 - 2 - 33 - 31 - 12 - 19 - 7 - 24 - 17 - 21 - 16 - 5 - 11 - 6 - 35 - 29 - 18 - 22 - 20 - 26 - 30 - 32 - 34 - 36 - 38 - 40 - 10

Merci !

Posté par
brubru777
re : Joute n°103 : Ali Baba et les 40 valeurs 12-03-13 à 11:08

gagnéBonjour,

Ali Baba peut ouvrir les 40 coffres. Il y a plusieurs solutions, en voici une :
1 19 36 17 38 21 34 39 25 14 11 27 32 35 33 2 31 29 22 7 30 23 28 15 13 4 9 5 8 3 40 37 24 26 20 18 16 10 12 6

Merci pour l'énigme.

Posté par
pdiophante
joute n°103 12-03-13 à 17:07

gagnéBonjour

Le tableau ci-après comporte quatre colonnes:
1) indice n variant de 1 à 30
1) numéros un des coffres dans l'ordre de leur ouverture
2) valeur absolue de (un - un-1)
3) ratio un/valeur absolue de (un-1 - un-2). Ce ratio doit être entier

Une solution possible figure donc en colonne 2.

joute n°103

Posté par
torio
re : Joute n°103 : Ali Baba et les 40 valeurs 12-03-13 à 18:42

perduPour 30 coffres :
                   Coffre : 1
              puis coffre : 11   donne les multiples de 10
              puis coffre : 20   donne les multiples de 9
              puis coffre : 27   donne les multiples de 7
              puis coffre : 35   donne les multiples de 8
              puis coffre : 32   donne les multiples de 3
              puis coffre : 39   donne les multiples de 7
              puis coffre : 28   donne les multiples de 11
              puis coffre : 33   donne les multiples de 5
              puis coffre : 40   donne les multiples de 7
              puis coffre : 21   donne les multiples de 19
              puis coffre : 19   donne les multiples de 2
              puis coffre : 2    donne les multiples de 17
              puis coffre : 17   donne les multiples de 15
              puis coffre : 15   donne les multiples de 2
              puis coffre : 38   donne les multiples de 23
              puis coffre : 23   donne les multiples de 15
              puis coffre : 18   donne les multiples de 5
              puis coffre : 5    donne les multiples de 13
              puis coffre : 13   donne les multiples de 8
              puis coffre : 24   donne les multiples de 11
              puis coffre : 22   donne les multiples de 2
              puis coffre : 26   donne les multiples de 4
              puis coffre : 12   donne les multiples de 14
              puis coffre : 14   donne les multiples de 2
              puis coffre : 16   donne les multiples de 2
              puis coffre : 34   donne les multiples de 18
              puis coffre : 36   donne les multiples de 2
              puis coffre : 30   donne les multiples de 6
              puis coffre : 6    donne les multiples de 24

Posté par
Diablow
re : Joute n°103 : Ali Baba et les 40 valeurs 16-03-13 à 20:49

gagnéBonjour,

Sans trop réfléchir, je suis parti sur une exploration systématique de l'arbre des possibilités. Mon Pc a tourné quelques heures pour sortir 569 solutions avec tous les coffres ouverts.

Voici la première de la série. Merci pour cette énigme.

Ouverture coffre n°1
Ouverture coffre n°3, |x-y|=2
Ouverture coffre n°10 (5x2), |x-y|=7
Ouverture coffre n°7 (1x7), |x-y|=3
Ouverture coffre n°9 (3x3), |x-y|=2
Ouverture coffre n°14 (7x2), |x-y|=5
Ouverture coffre n°5 (1x5), |x-y|=9
Ouverture coffre n°36 (4x9), |x-y|=31
Ouverture coffre n°31 (1x31), |x-y|=5
Ouverture coffre n°35 (7x5), |x-y|=4
Ouverture coffre n°16 (4x4), |x-y|=19
Ouverture coffre n°19 (1x19), |x-y|=3
Ouverture coffre n°21 (7x3), |x-y|=2
Ouverture coffre n°8 (4x2), |x-y|=13
Ouverture coffre n°13 (1x13), |x-y|=5
Ouverture coffre n°15 (3x5), |x-y|=2
Ouverture coffre n°2 (1x2), |x-y|=13
Ouverture coffre n°39 (3x13), |x-y|=37
Ouverture coffre n°37 (1x37), |x-y|=2
Ouverture coffre n°20 (10x2), |x-y|=17
Ouverture coffre n°17 (1x17), |x-y|=3
Ouverture coffre n°6 (2x3), |x-y|=11
Ouverture coffre n°11 (1x11), |x-y|=5
Ouverture coffre n°40 (8x5), |x-y|=29
Ouverture coffre n°29 (1x29), |x-y|=11
Ouverture coffre n°33 (3x11), |x-y|=4
Ouverture coffre n°28 (7x4), |x-y|=5
Ouverture coffre n°25 (5x5), |x-y|=3
Ouverture coffre n°27 (9x3), |x-y|=2
Ouverture coffre n°4 (2x2), |x-y|=23
Ouverture coffre n°23 (1x23), |x-y|=19
Ouverture coffre n°38 (2x19), |x-y|=15
Ouverture coffre n°30 (2x15), |x-y|=8
Ouverture coffre n°32 (4x8), |x-y|=2
Ouverture coffre n°34 (17x2), |x-y|=2
Ouverture coffre n°26 (13x2), |x-y|=8
Ouverture coffre n°24 (3x8), |x-y|=2
Ouverture coffre n°22 (11x2), |x-y|=2
Ouverture coffre n°18 (9x2), |x-y|=4
Ouverture coffre n°12 (3x4), |x-y|=6

Posté par
LeDino
re : Joute n°103 : Ali Baba et les 40 valeurs 18-03-13 à 01:38

gagnéMon Ali Baba ouvre 32 coffres :
1 - 5 - 8 - 15 - 7 - 40 - 33 - 35 - 12 - 23 - 11 - 24 - 13 - 22 - 27 - 25 - 6 - 19 - 39 - 20 - 38 - 36 - 34 - 32 - 30 - 28 - 26 - 18 - 16 - 14 - 10 - 4

Merci pour ce rude casse- tête .

Posté par
rogerd
Ali Baba 20-03-13 à 12:13

gagnéBonjour et merci à godefroy_lehardi.

Je propose la suite de 38 coffres:

1 3 8 5 9 4 15 11 24 13 22 27 20 7 39 32 35 6 29 23 18
25 28 33 40 21 19 2 17 30 26 12 14 16 34 36 38 10

Posté par
seb_dji
j'en ai 33 20-03-13 à 12:47

gagnéje propose 1 4 9 5 8 3 10 7 12 25 13 24 11 26 15 22 35 39 16 23 21 2
19 17 20 18 28 30 32 34 36 38 40

Posté par
rogerd
Ali Baba 20-03-13 à 14:18

gagnéIl  est même possible de parcourir les 40 coffres, et de plusieurs façons.
Par exemple, dans l'ordre:

  1, 3, 10, 7, 9, 14, 5, 36, 31, 35, 16, 19, 21, 8, 13, 15, 2, 39, 37,

  20, 17, 6, 11, 40, 29, 33, 28, 25, 27, 4, 23, 38, 30, 32, 34,

  26, 24, 22, 18, 12

En espérant avoir bien compris l'énoncé...

Posté par
Alishisap
re : Joute n°103 : Ali Baba et les 40 valeurs 20-03-13 à 22:33

gagnéBonjour et merci beaucoup pour l'énigme !

Si Ali Baba parcourt les coffres dans l'ordre suivant, alors il pourra ouvrir exactement 30 coffres :

1 4 27 23 20 3 17 28 33 35 32 39 14 25 22 9 13 16 18 10 8 6 2 40 38 36 34 30 24 12

En espérant ne pas avoir fait d'erreurs d'étourderies (je l'ai résolu par tâtonnements),
À bientôt !

Posté par
sbarre
re : Joute n°103 : Ali Baba et les 40 valeurs 23-03-13 à 08:54

gagnéBonjour,

le premier de la (très longue) liste trouvée avec Algobox:
1 | 3 | 8 | 5 | 9 | 4 | 15 | 11 | 16 | 25 | 18 | 7 | 33 | 26 | 21 | 40 | 38 | 2 | 36 | 34 | 6 | 28 | 22 | 12 | 10 | 24 | 14 | 30 | 32 | 20

Merci et à bientot

Posté par
Alishisap
re : Joute n°103 : Ali Baba et les 40 valeurs 24-03-13 à 15:21

gagnéBonjour,
Rapidement j'explique ma démarche.

Au départ je voulais faire un programme qui teste par le pseudo-aléatoire énormément de combinaisons dans l'espoir d'en trouver une qui permette d'ouvrir au moins 30 coffres. Mais le nombre de cas est tellement important que j'ai rapidement abandonné. Encore une fois, les permutations m'auraient sauvé la vie si j'avais su comme les gérer. Quelle plaie !

Du coup j'ai été contraint de faire ça "à l'ancienne", au papier et au crayon (ou plutôt au Word et au clavier en l'occurrence ) et honnêtement je ne pensais pas parvenir à trouver une combinaison valide.
Il est très facile de faire suivre des coffres pairs (du fait qu'ils ont un diviseur commun : 2), en revanche ça l'est beaucoup moins pour les coffres impairs.
L'idée, c'est donc dans un premier temps ouvrir le plus de coffres impairs puis de s'occuper des pairs. Il y a une autre raison à cela, capital : deux coffres impairs sont obligatoirement séparés par 1 ou aucun coffre. Autrement dit, si jamais on ouvre 2 coffres pairs successivement, il ne sera plus possible d'ouvrir des coffres impairs par la suite.

Sur ma suite, c'est très visible :

1 4 27 23 20 3 17 28 33 35 32 39 14 25 22 9 13 16 18 10 8 6 2 40 38 36 34 30 24 12

Dans la première partie en gras, j'ai réussi à ouvrir 11 coffres impairs, puis dans la partie soulignée, ce ne sont que des coffres pairs.
C'était difficile et frustrant : le nombre de fois où j'ai stagné à 28 ou 29 coffres ! Il faut alors supprimer toute une partie de la suite et recommencer... Ça met les nerfs à vif !
Mais j'y suis quand même arrivé et je dois avouer que pour le coup j'en suis assez fier : ça fait longtemps que je n'ai pas résolu une énigme sans l'aide d'un logiciel ou d'un programme.
Finalement le programme que j'ai réalisé au début n'aura pas servi à rien : il a confirmé que ma suite est valide.

Il y a tout de même une question que je me pose : est-il possible d'ouvrir les 40 coffres ? Peut-être qu'un membre a réussi, et dans ce cas je lui tire mon chapeau !

Posté par
Luc1408
re : Joute n°103 : Ali Baba et les 40 valeurs 24-03-13 à 16:07

perduBonjour,
après de longues recherches, voilà ma proposition
il est intéressant de remarquer que, si deux nombres de la suite sont multiples de leur différence, alors tous les autres nombres seront des multiples de cette différence.
Il en vient que deux nombres pairs ne donneront que des nombres pairs.
Ainsi en est il de 3 et 6 (136912 etc... ou 136121824etc...)
J ai don essayé d'alterner nombres pairs et impairs, et je trouve :

1;3;8;15;28;39;22;17;10;7;12;25;13;24;33;36;27;18;9;(passe partout);2;21;19;4;30;26;20;6;14;16;40

Pour un total de 30 coffres !

Merci pour l'énigme !

Posté par
totti1000
re : Joute n°103 : Ali Baba et les 40 valeurs 24-03-13 à 21:34

gagnéSalut Godefroy,

Je propose : 1-4-9-5-8-3-40-37-27-10-17-7-30-23-28-15-13-2-33-31-12-19-21-34-39-25-14-11-6-35-29-18-22-24-26-38-36-16-20-32.

Merci.

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 12:06

Clôture de l'énigme :

On pouvait bien ouvrir les 40 coffres. Bravo à ceux qui ont trouvé (personnellement, je n'y étais pas arrivé).

J'en profite pour vous annoncer une petite nouveauté sur le forum des énigmes.
La joute n°100 ayant montré que vous étiez capables d'inventer des énigmes très intéressantes, il serait dommage de laisser perdre ce potentiel.
Donc désormais, afin de soulager un peu les posteurs officiels, le vainqueur du mois deviendra posteur honoraire pendant le mois suivant l'annonce de sa victoire et devra donc proposer au moins une énigme (il ne pourra évidemment pas participer aux énigmes pendant cette période).
Cette disposition prend effet à partir du mois de mars. Du fait des délais de correction, le vainqueur de mars sera donc posteur pendant le mois de mai, celui d'avril officiera en juin, etc…

Posté par
totti1000
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 13:25

gagnéBonjour godefroy,

j'aimerai juste faire une petite remarque qui n'engage que moi. En effet je trouve un peu dommage que ces derniers temps les réponses demandées aux énigmes soient un peu "larges". Je m'explique, par exemple pour l'énigme des coffres tu demandes un "au moins 30" alors qu'il aurait été super intéressant de demander une réponse maximale. C'est surement pour qu'un maximum de joueurs participe, et je comprends très bien, mais au moins une fois dans le mois demander une réponse plus précise et donc avoir une énigme un peu plus complexe pourrait être sympa.
Voilà ce n'est pas un reproche mais juste une suggestion.

Et encore merci aux posteurs pour leur travail !

Posté par
panda_adnap
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 13:47

gagnéBonjour,

Je suis d'accord avec Totti1000, surtout sur le fait que vous faites un super boulot !

Pour ma part, je me suis attaché à chercher une solution optimale à cette énigme, même si cela n'était pas demandé. J'ai été étonné de pouvoir ouvrir tous les coffres ! Après, il est vrai que je résous (presque) toutes les énigmes par l'informatique et que j'ai donc un avantage certains sur ceux qui cherchent à la main. C'est peut être pour ca qu'on demande toujours une solution trouvable "à la main".

Les 2 prochaines énigmes n'ont pas ce souci, puisqu'elles demandent toutes deux une solution optimale (je les ai d'ailleurs particulièrement appréciées).

Bonne idée la proposition de faire poster les gagnants... Dommage de l'annoncer un 1er avril

Posté par
sbarre
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 14:17

gagnébonjour àtous

Citation :
il est vrai que je résous (presque) toutes les énigmes par l'informatique et que j'ai donc un avantage certains sur ceux qui cherchent à la main
là, il n'y  a pas de doute...
J'ai donc essayé de m'y mettre aussi et j'ai attaqué algobox (vu qu'il y a sans arret des questions là dessus dans le forum, ca faisait coup double. Malheureusement pour cette énigme, j'ai fait un truc archi compliqué (quelques centaines de lignes ...) ce qui fait que pour 30 clés ca passait, mais pour les 40 cles j'étais obligé de faire tourner avec des solutions pour les premières cles tirées des résultats initiaux à 30 cles!

En un mot est ce que certains d'entre vous voudraient bien m'aider à m'améliorer dans le domaine.  En particulier pour les 39 cles j'attribuais avec des boucles toutes les valeurs de 2 à 40 (donc 39 puissance 39 combinaisons)  puis je faisais pour chacune un test pour verifier que c'était différent de toutes les cles précédemment choisie.
un enfer à écrire et pas cool pour le calculateur (même si je sais qu'il n'a pas de sentiments )

Posté par
panda_adnap
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 15:16

gagnéPour ma part, j'ai fait un brute force en C.
Mais tu n'as pas besoin de tester tous les cas...
Je ne sais pas comment marche algobox, mais en C, tu peux ne tester que les cas "plausibles".
Du coup, ca ne fait que 10s pour trouver le cas ou on ouvre tous les coffres...

Citation :

#include <stdio.h>
#include <stdlib.h>


char ouverts[41];
char ordre[40];
int max = 0;

int play(int nb, int last, int diff) {
    if (nb > max) {
        max = nb;
        printf("%d : ", nb);
        for (int i = 0; i < max; i++) {
            printf("%d ", ordre[i]);
        }
        printf("\n");

    }
    if (nb == 40) exit(0);
    if (nb > 1 && diff == 1) return;
    for (int i = diff; i <= 40; i+=diff) {
        if (ouverts[i]) continue;
        if (i%diff) continue;
        ordre[nb] = i;
        ouverts[i] = 1;
        play(nb+1, i, i>last?i-last:last-i);
        ouverts[i] = 0;
    }
}

int main() {
    for (int i = 1; i <= 40; i++) {
        ouverts[i] = 0;
    }
    ordre[0] = 1;
    ouverts[1] = 1;
    play(1, 1, 1);
}


Posté par
sbarre
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 15:48

gagnéok merci; je vais essayer de comprendre tout ca!

Posté par
rogerd
Ali Baba 01-04-13 à 15:53

gagnéBonjour à tous

Citation :
  
Il est vrai que je résous (presque) toutes les énigmes par l'informatique et que j'ai donc un avantage certains sur ceux qui cherchent à la main

Il ne faudrait pas laisser croire qu'utiliser l'informatique permet d'avoir la solution en appuyant simplement sur un bouton.
Pour moi, cela nécessite autant de réflexion préalable que la recherche avec un papier et un crayon.

A l'attention de sbarre:

j'ai utilisé un langage rudimentaire (une vieille version de Maple) en imbriquant 4 boucles (pour trouver une solution avec 4 coffres), chacune dressant la liste des numéros de coffres encore disponibles. Avec un copier-coller j'ai incrusté une 4eme puis une 5eme boucle etc... J'ai constaté que cela n'allongeait pas trop le temps de calcul (du fait des contraintes, la liste des disponibles diminue vite) Je suis allé ainsi jusqu'à 30 boucles imbriquées. C'est évidemment un  programme très long et laid , mais vite écrit grâce au copier-coller .
L'objectif était atteint mais j'ai quand même poussé jusqu'à 40 boucles (dans mon souvenir: quelques minutes) pour avoir la solution optimale.

Personnellement, je trouve plus de plaisir dans la conception d'un programme qui tourne en un temps raisonnable que dans une recherche en tâtonnant avec un papier et un crayon.

Posté par
rogerd
Ali Baba 01-04-13 à 15:59

gagnéJe viens seulement de lire le courrier de panda-adnap..

Posté par
geo3
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 16:05

gagnéBonjour
Pour ma part je ne suis pas d'accord avec panda_adnap et sbarre
Moi je sais programmer un peu en basic mais je suis loin d'être un expert
*
S'il faut être un programmeur chevronné pour résoudre les énigmes pourquoi ne pas faire des énigmes " spécial programmeur " et des autres  "spécial mathématiciens "  c'est pour rire "
une que j'ai bien aimé c'est celle de Jamo l'arc de 115°5 engmo 292
(je préfère la géométrie)
En encore merci pours ces énigmes
A+

Posté par
sbarre
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 16:13

gagnéat rogerd  en gros c'est ce que j'avais fini par faire avec le probleme que algobox limite le nombre de boucles ou d'opérations entraînant l'incapacité à faire tourner jusqu'au bout...

quant au programme de panda, je ne comprends absolument pas le langage.
je vais essayer de trouver un manuel pour le C afin de décrypter la chose.

Posté par
rogerd
Ali Baba 01-04-13 à 17:31

gagné>geo3
Assez d'accord avec toi: la programmation ne doit pas étouffer les énigmes.
Il n'empêche qu'on peut être intéressé, pour une énigme donnée , par le dilemme:  réfléchir sur l'énigme elle même ou réfléchir à sa programmation. La conclusion dépend de l'énigme. Si une idée de programme se fait jour et semble rentable , l'outil de programmation doit rester simple, sous peine de dénaturer l'esprit du jeu. Donc, a priori, pas de langage C. J'aime bien aussi utiliser l'outil (Maple, pour moi) de manière interactive en raffinant au fur et à mesure le programme.

Posté par
fontaine6140
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 18:01

gagnéBonjour,

Sans utiliser diverses boucles mais en les remplaçant par une récursivité:
ce qui donne 569 solutions pour 40 coffres.


CONST Faux = (0 = 1)
CONST Vrai = NOT (Faux)
CONST MAX = 40
CONST MIN = 29
CONST Alpha = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcde"

DIM SHARED sMin AS INTEGER
sMin = 0
CLS
OPEN "c:\_joute\103\103.sol" FOR OUTPUT AS #1
PRINT #1, "0000000001000000000200000000030000000004"
PRINT #1, "1234567890123456789012345678901234567890"
PRINT #1, Alpha
PRINT #1, "----------------------------------------"

CALL Traiter0
CLOSE #1
END

SUB Traiter0
DIM s AS STRING * MAX, i AS INTEGER
s = "1" + SPACE$(MAX - 1)
FOR i = 2 TO MAX
    MID$(s, 2, 1) = MID$(Alpha, i, 1)
    CALL Traiter(s, 2)
NEXT i
END SUB

FUNCTION Net$ (p AS INTEGER, p1 AS INTEGER)
Net$ = RIGHT$(STRING$(p1, "0") + LTRIM$(STR$(p)), p1)
END FUNCTION

FUNCTION Joli$ (w AS STRING)
DIM ret AS STRING, i AS INTEGER, s AS STRING
s = RTRIM$(w)
ret = ""
FOR i = 1 TO LEN(s)
    ret = ret + Net$(INSTR(Alpha, MID$(s, i, 1)), 2) + ","
NEXT i
Joli$ = ret
END FUNCTION

SUB Traiter (p AS STRING * MAX, niv AS INTEGER)
DIM x AS INTEGER, s AS STRING * MAX, k AS INTEGER, n AS INTEGER, f AS STRING
CALL Pause
x = ABS(INSTR(Alpha, MID$(p, niv, 1)) - INSTR(Alpha, MID$(p, niv - 1, 1)))
s = p
IF niv >= sMin THEN
    sMin = niv
    f = STR$(sMin) + "<" + Joli$(s) + ">"
    PRINT #1, f
    LOCATE 4, 1: PRINT f
END IF

IF x = 1 THEN
    EXIT SUB
ELSE
    FOR i = x TO MAX STEP x
        IF INSTR(p, MID$(Alpha, i, 1)) = 0 THEN
            n = niv + 1
            MID$(s, n, 1) = MID$(Alpha, i, 1)
            LOCATE 3, 1: PRINT LEN(RTRIM$(s)); "<"; s; "> niv="; niv
            CALL Traiter(s, n)
            'PRINT "retour: "; p
        END IF
    NEXT i
END IF
END SUB

SUB Pause
y$ = INKEY$
IF LEN(y$) > 0 THEN
    END
END IF
END SUB

Posté par
sbarre
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 18:35

gagnéBonjour fontaine
c'est du C ca aussi?

maple est payant non?
quelqu'un ayant utilisé maple pour l'arc 115,5° m'avait motivé (du fait de la simplicité apparente) pour essayer, mais je ne suis tombé que sur un essai de 30 jours.
Existe-t-il une version basique gratuite  (et peut être même portable...) ?

Posté par
panda_adnap
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 19:08

gagné

Citation :
Si une idée de programme se fait jour et semble rentable , l'outil de programmation doit rester simple, sous peine de dénaturer l'esprit du jeu. Donc, a priori, pas de langage C. J'aime bien aussi utiliser l'outil (Maple, pour moi) de manière interactive en raffinant au fur et à mesure le programme.


C'est bizarre de considérer que Maple est plus simple que le C...

Après, je suis d'accord avec vous sur le fait que chacun peut utiliser les outils qu'il souhaite pour résoudre une énigme, c'est d'ailleurs pour ca que je considère qu'accepter une solution trouvable à la main a du sens. Pour ma part, j'ai une culture informatique et mathématique et je me retrouve plus en essayant d'utiliser les mathématiques pour optimiser mon algorithme. C'est comme ca que je m'amuse le plus, et c'est donc ce que je recherche dans ces énigmes. Je ne cherche absolument pas à étouffer quoi ou qui que ce soit.

J'ai également apprécié l'énigme sur l'arc de 115° beaucoup plus mathématique, même si j'ai eu faux... Je l'ai fait avec un papier et un crayon, et elle m'a semblé très intéressante aussi.

Posté par
rogerd
Ali Baba 01-04-13 à 19:51

gagnésbarre>
Effectivement, je crois qu'il n'y a jamais eu de version gratuite de Maple (j'utilise quant à moi la version que j'utilisais avec mes élèves avant de prendre ma retraite, il y a plus de 10 ans..).
Mais il doit bien exister des logiciels gratuits équivalents?

panda_adnap>
Je me suis remis au C récemment pour un assez gros travail combinatoire, qui ferait exploser Maple, mais qui est assez long à mettre en branle (écriture, corrections, mise au point etc) quand on part de zéro. C'est en ce sens là que je trouve que Maple est plus simple.

Posté par
brubru777
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 21:34

gagnéPour moi, il y a 3 sortes d'énigmes.

- celles qui peuvent se résoudre "à la main"
- celles qui ne peuvent pas se résoudre qu'avec l'informatique
- celles qui nécessitent un peu des deux

Dans quelle catégorie placer une énigme ?

Tout dépend des capacités de chacun. Parfois, par manque de temps ou d'inspiration, je fais un programme pour résoudre une énigme pour m'apercevoir, en lisant les autres réponses, qu'il existait une solution "à la main". C'est le cas pour les instants pythagoriciens par exemple.

Pour l'arc, j'ai fait les calculs à la main jusqu'à la dernière équation trop compliquée que j'ai résolue grâce à un programme.

Parfois, je trouve des solutions à la main mais je fais quand même un programme pour les vérifier. (ex : trouver un trajet minimal)

Dans tout les cas, la conception d'un programme (simple ou complexe) est un processus de réflexion à part entière. La programmation est un outil au même titre que les maths ou la logique ou la créativité. Et on peut aussi se tromper en faisant un programme.

Labelliser des énigmes "programmeur" ou "mathématiciens", ça n'a pas vraiment de sens. Chacun les résout avec ses outils. Si certaines énigmes sont trop complexes pour les outils dont on dispose, c'est dommage mais ça fait partie du jeu.

Personnellement, j'ai beaucoup de mal avec les énigmes "créatives" comme Bonne année 2013 qui semblent apparemment très faciles pour certains.

Posté par
Kidam
re : Joute n°103 : Ali Baba et les 40 valeurs 01-04-13 à 22:05

gagnéC'est intéressant de lire les commentaires de tous. On se rend compte qu'on est tous différents.

J'avais repris le C il y a quelques temps pour résoudre certaines énigmes, mais j'ai arrêté car je trouvais ça frustrant, je n'avais pas de plaisir à trouver la solution.

Je préfère réfléchir et tâtonner (ça ne veut pas dire "au hasard") pour réussir les énigmes. J'y trouve plus de satisfaction.
Je ne veux surtout pas dire qu'il ne faut pas réfléchir pour faire un programme, mais la démarche est différente, plus mécanique, moins mathématique.
C'est sûr qu'il est nécessaire de passer par des outils pour parfois se faciliter le travail, mais le minimum me satisfait.

Je ne peux pas terminer ce message sans remercier nos posteurs permanents qui, étant donnée la date, risquent de rester deux malgré leurs dires

Posté par
dpi
re : Joute n°103 : Ali Baba et les 40 valeurs 02-04-13 à 08:25

perduBonjour,

Comme mes raisonnements sont parfois étonnants,voici
ce que j'ai compris...

*Ayant ouvert 1 et 3 j'ai accès à tous les multiples de 2
(sauf, ceux que je veux exclure)
donc 2 4 6 8 10 12 14 16 18 20 22 24 26 28 32 34
*A ce stade le dernier ouvert étant le 34 et le dernier
m'ayant donné accès à cette série étant le 3,j'ai donc
accès aux multiples de (34-3)=31
*Je ne garde que 31
*j'ai donc accès à (34-31)=3,à tous les multiples de 3
que je désire retenir soit 9 15 21 27 33 36.

Enfin et toujours avec la même "logique"
*36-31=5 me donne accès aux multiples de 5 choisis
5 25 35 40

Posté par
Kidam
re : Joute n°103 : Ali Baba et les 40 valeurs 02-04-13 à 08:57

gagnésalut dpi,

Si tu as lu ma réponse, tu verras que comme toi, j'ai eu du mal à comprendre l'énoncé. Mais comme souvent, c'est l'exemple qui nous permettait de bien saisir :

En ouvrant un coffre, tu avais chaque fois la possibilité d'ouvrir n'importe quel coffre multiple de la différence des deux précédents, mais tu devais en choisir UN SEUL parmis tous ceux là ! Il s'agissait d'une énigme Joute n°103 : Ali Baba et les 40 valeurs , or ta compréhension de l'énigme en faisait une énigme vraiment trèèèès simple. Personnellement, c'est ce qui m'a mis la puce à l'oreille. J'ai relu plusieurs fois l'énoncé et étudié le début fourni par Godefroy_Lehardy pour bien comprendre ce qu'il attendait de nous.

Posté par
sbarre
re : Joute n°103 : Ali Baba et les 40 valeurs 02-04-13 à 10:10

gagnérebonjour
j'ai une question subsidiaire pour le correcteur! Comment fait-il pour corriger? a la main ? (et dans ce cas chapeau car il m'a fallu du temps pour trouver pourquoi torio avait eu un poisson...) ou avec une petite moulinette, ou il rentre les solutions proposees, pour les tester (avec les risques d'erreur de saisie...).

Quoi qu'il en soit cela represente bien du boulot, et ce pour notre plaisir a tous! Qu 'il en soit une nouvelle fois remercie.  

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°103 : Ali Baba et les 40 valeurs 02-04-13 à 10:36

Bonjour à tous,

Il y a eu pas mal de discussions et il serait temps que je réponde.

> totti1000 : c'est vrai que chercher une solution optimale est plus stimulant. Cependant, outre le fait que je n'ai pas pris le temps de chercher la solution à 40 coffres, je me suis dit qu'il fallait aussi encourager la participation.
Ne t'inquiète pas, il y en aura d'autres plus "sélectives"

> panda_adnap, sbarre, rogerd, geo3, brubru777, Kidam : la méthode de résolution des énigmes dépendent des goûts et des capacités de chacun. Et il faut, à mon humble avis, autant de matière grise pour trouver le bon programme qui marche que pour trouver une méthode purement mathématique.
N'étant moi-même pas du tout programmeur (j'en suis resté au Basic des années 80), toutes mes joutes sont trouvables sans programmation.
Personnellement, mon seul outil mathématico-informatique, c'est un tableur.
Pour cette joute (et la correction), j'ai utilisé les fonctions d'Excel pour déterminer à chaque étape quels nombres pouvaient être utilisés au coup d'après.

> dpi : je reconnais un petit flou dans l'énoncé mais l'exemple était explicite. Comme le dit Kidam, l'énigme aurait été vraiment trop simple sinon.

Enfin, l'annonce du posteur honoraire était effectivement un . Mais si quelqu'un veut devenir posteur officiel pour de vrai, il est le bienvenu !

Posté par
dpi
re : Joute n°103 : Ali Baba et les 40 valeurs 02-04-13 à 10:44

perdu>kidam
Merçi

>godefroy_lehardi
Si seulement les virgules séparant les multiples de 8
avaient été remplaçées par des "ou" dans ton énoncé,je
serais dans le top

Posté par
godefroy_lehardi Posteur d'énigmes
re : Joute n°103 : Ali Baba et les 40 valeurs 02-04-13 à 10:48

Tu as raison. Le "et" n'est pas pertinent. J'aurais dû mettre "ou" à la place.

Toutes mes excuses à ceux qui ont été perturbés par cette imprécision.

Posté par
dpi
re : Joute n°103 : Ali Baba et les 40 valeurs 02-04-13 à 14:47

perduCa me console

1 2 +


Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 92:40:48.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


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 !