Inscription / Connexion Nouveau Sujet
Juin 2016, énigme 3
Bonjour,
Voici donc la troisième énigme de ce mois :
Sur un cercle sont placés des plots éclairés numérotés de 1 à n. On tourne sur ce cercle, toujours dans le sens des aiguilles d'une montre, en partant du plot 1 que l'on éteint. On franchit deux plots allumés, puis on éteint le plot allumé suivant, et on reconduit le même processus jusqu'à ce qu'il ne reste qu'un seul plot allumé.
Par exemple sur la figure ci-dessous on s'est placé dans le cas où n=9. On éteint successivement les plots 1-4-7-2-6-3-9-5 et le dernier « survivant » est le plot numéro 8.
On se place maintenant dans le cas où n=2016.
Quel est alors le dernier survivant ?
Bonjour,
En supposant que les plots sont aussi placés dans le sens des aiguilles d'une montre, comme dans l'exemple, je propose comme dernier plot survivant :
653
Merci pour l'énigme et bonne soirée
dernier survivant = 653
Merci Littleguy
Programme en Python (http://www.python.org)
nb=input("n?")
n=int(nb)
lamp=[True]*n #on crée une liste de n
p=0 #plot N°1 a indice 0
sol=""
for j in range(1,n): #donc n-1 tours de boucle, on éteint n-1 plots
lamp[p]=False #on éteint un plot
sol=sol+str(p+1)+" "
while not(lamp[p]): #on cherche un plot allumé
p=(p+1)%n #+1 congru n
p=(p+1)%n #on passe un premier plot allumé
while not(lamp[p]): #on cherche un plot allumé
p=(p+1)%n
p=(p+1)%n #on passe un second plot allumé
while not(lamp[p]): #on cherche un plot allumé
p=(p+1)%n
#fin de boucle
print(sol) #liste des plots éteints
print("dernier=",p+1) #plot N°p+1 a indice p
Bonjour,
Je propose 1836
J'aimerais dire que j'ai utilisé les propriétés des modulos ... la vérité c'est que j'ai utilisé excel, j'espère ne pas m'être trompée ...
Bonne journée et merci pour l'énigme
Bonjour,
Voici ma réponse :
Dans le cas où n=2016, le dernier survivant est 653.
Merci à Scratch, en espérant ne pas m'être planté dans le programme. Niveau efficacité, ce fût très long...
Merci pour l'énigme.
Bonsoir
Je pense que le dernier des 2016 plots à rester allumé est le plot numéro 653.
Merci pour cette énigme ! 
Bonjour
Je propose
653
J'ai écrit ce petit prog Python :
fin=2016
a=range(1,fin+1)
print a
while len(a)>2:
a=a[1:len(a)]
b=a[0:2]
a=a[2:len(a)]+b
print a
Merci pour l'Enigme
Est qu'il y a une manière plus efficace d'obtenir le dernier plot allumé que de créer tout les plots et de les éteindres les uns après les autres (implémenté avec une liste chainée circulaire contenant les plots allumés)? La réponse est oui mais bon sang ce n'est pas simple 
.
J'ai obtenu une méthode empiriquement mais j'aurai bien du mal à la démontrer.
Voici la série des derniers plots pour n = 1,2,...
1, 2, 3, 3, 2, 5, 2, 5, 8, 2, 5, 8, 11, 14, 3, 6, 9, 12, 15, 18, 21, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 2, 5, 8, ...
On s'aperçoit que la série à partir de n=5 est la concaténation de suites arithmétiques de raison 3 et démarrant avec 2 ou 3. Il suffit donc de déterminer pour quels n la suite recommence et quand elle recommence si c'est avec u=2 ou u=3.
Excluant n < 5, voici les n et u pour les premières suites :
| n | 5 | 7 | 10 | 15 | 22 | 32 | 48 | 71 | 106 | 159 | 238 | 356 | 534 | 800 | 1200 | 1799 | 2698 | 4047 | 6070 | 9104 |
| u | 2 | 2 | 2 | 3 | 3 | 2 | 3 | 2 | 2 | 3 | 3 | 2 | 3 | 2 | 3 | 2 | 2 | 3 | 3 | 2 |
| d | 1 | 1 | 0 | 1 | 2 | 0 | 2 | 1 | 0 | 1 | 2 | 0 | 2 | 0 | 2 | 1 | 0 | 1 | 2 | 0 |
On s'aperçoit que n suit presque une progression géométrique :
On s'aperçoit aussi que
Ce qui donne la méthode suivante :
def dernier(N) :
if N < 5 :
return 3 if N == 4 else N
n,d,u = 5,2,2
while True :
if (n % 2) == 0 :
d = 2-d
n_ = (3*n-d)//2
u_ = 3 if d == 0 else 2
else :
n_ = (3*n-1)//2
u_ = u
if n_ > N :
return u + (N-n)*3
n,u = n_,u_
Ça a l'air simple comme ça mais ce n'était pas facile à trouver
.
Ceci n'est qu'une conjecture (mais elle marche bien ^^), si quelqu'un veut s'attaquer à la démonstration j'en serais ravi
.
Que se passe-t-il lorsqu'on saute non pas 2 mais 3,4,... plots?
Le numéro du dernier plot allumé quand il y a 20162016 plots est un nombre de 6662 chiffres congru à 770 modulo 2016 (pas la place pour l'écrire
).Je ne sais pas s'il y avait une "méthode mathématique simple" pour résoudre l'énigme, en tous cas s'il y en avait une , je ne l'ai pas trouvée.
Avec un petit code , je trouve que le dernier survivant est le plot numéro 653
Merci pour l'énigme
Trouvé grâce à excel utilisant des couleurs, enfin j'aurai du faire un programme qui donne le résultat, mais je ne maîtrise pas beaucoup le langage des logiciels calculatrice, macro, etc...
p.s. j'ai d'abord, voulu trouver toutes les suites récurrentes qui se défilent, mais finalement j'ai préféré m'amuser avec les couleurs sur le open office calc, soit excel et la fin de la série des nombres est: 743, 1796, 507 !
si n egale a 9 le dernier c est 8 donc n-1 si n egale a 2016 alors je pense que c'est une suite arithmetrique de raison -1 alors c 2015 le dernier survivant
Bonjour,
Et voilà la troisième étape terminée.
Encore une fois beaucoup de bonnes réponses, félicitations à tous. 
Je dois vous informer que je serai par monts et par vaux les semaines à venir, avec des connections internet souvent très aléatoires, aussi je ne proposerai pas de nouvelles énigmes dans l'immédiat. Je ferai tout de même en sorte que les résultats des énigmes en cours vous parviennent.
J'en profite pour renouveler un appel à ceux qui hésitent encore à se lancer dans l'aventure. Si vous vous sentez l'âme d'un poseur d'énigmes, l'île a besoin de vous !
Merci.
Pour ceux qui s'intéressent à la résolution mathématiques du problème, il est connu sous le nom du problème de josèphe.
On trouve une démonstration pour le cas ou on saute de deux en deux. On doit pouvoir l'adapter pour ce cas là...
Je vois que pas mal de monde utilise le python
Par contre les codes donnés utilises une simple liste. Les listes ne sont pas faites pour le décalage (comme l'utilise benmagnol), chaque décalage se faisant en O(n). On peut éviter les copies de listes et les décalages comme l'a fait Chatof en ne modifiant pas la structure de la liste. Il faut néanmoins parcourir toutes les lampes éteintes et on se retrouve dans les deux cas avec un algorithme en O(nlog(n)).
On peut faire du O(n) en utilisant une structure adaptée, la liste chaînée (deque en python). Ce qui donne ceci :
from collections import deque
def derniereLampe(n) :
lampes = deque(range(1,n+1))
while len(lampes) > 1 :
lampes.popleft()
lampes.rotate(-2)
return lampes[0]Plutôt simple non? Et efficace
.
Pour ceux qui veulent une méthode encore plus efficace O(log(n)), il y a la méthode dernier(n) que j'ai présentée dans mon post précédent. Mais elle est beaucoup moins simple
.En suivant l'indication de weierstrass, on trouve sur wikipedia un algorithme générique en O(n) en temps et O(1) en espace. Il est indiqué aussi qu'une solution en O(k log(n)) est possible mais sans donner cette solution.
Après réflexion voici une solution générique en O(k log(n)) :
def g(n,k) :
if n == 1 :
return 0
if n < k :
return (g(n-1,k) + k) % n
n_ = n-n//k
g_ = (g(n_,k)-n%k) % n_
return g_ + g_//(k-1)
Où g(n,k) est le numéro de la dernière place restante quand on élimine une place toutes les k places (0 est gardé, k-1 est éliminé) parmis n places numérotées de 0 à n-1.
La solution de notre problème est donnée par g(2016-1,3)+2. g(n-1,k)+1 parce qu'on élimine la première place et encore +1 car la première place est numérotée 1 et pas 0.
J'en ai profité pour faire ma première contribution à wikipédia (en anglais)
Nombre de participations : 28
67,86 %32,14 %
9Temps de réponse moyen : 84:32:55.
Annuler
connectez vous