Inscription / Connexion Nouveau Sujet
Niveau 1 *
Partager :

Juin 2016, énigme 3

Posté par
littleguy
13-06-16 à 17:05

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.
Juin 2016, énigme 3

On se place maintenant dans le cas où n=2016.

Quel est alors le dernier survivant ?

Posté par
masab
re : Juin 2016, énigme 3 13-06-16 à 17:33

gagnéBonjour littleguy,

Le dernier survivant est le plot numéro 653.
Merci pour cette énigme lumineuse !

Posté par
Nofutur2
re : Juin 2016, énigme 3 13-06-16 à 19:00

gagnéIl me semble que c'est le 653 qui réussit à survivre !!!
Un nombre premier en plus !!
A moi le

Posté par
trapangle
re : Juin 2016, énigme 3 13-06-16 à 19:13

gagné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

Posté par
albatros44
re : Juin 2016, énigme 3 13-06-16 à 19:14

gagnéBonjour

Le dernier survivant est le 653


Bonne journée

Posté par
weierstrass
re : Juin 2016, énigme 3 13-06-16 à 19:57

gagnéBonjour,
Je répond le numéro 653

Posté par
Chatof
re : Juin 2016, énigme 3 13-06-16 à 20:47

gagné 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

Posté par
franz
re : Juin 2016, énigme 3 13-06-16 à 21:01

gagnéLe dernier survivant est le n° 653.
Merci pour l'énigme

Posté par
sbarre
re : Juin 2016, énigme 3 13-06-16 à 22:31

gagnéBonsoir,
je dirais que c'est 653 qui est le dernier survivant.

Merci et à la prochaine!

Posté par
torio
re : Juin 2016, énigme 3 13-06-16 à 23:41

gagnéReste  :  653
A+
Torio

Posté par
dpi
re : Juin 2016, énigme 3 14-06-16 à 08:20

perduBonjour

Plein de pièges .
Je tente 305

Posté par
LittleFox
re : Juin 2016, énigme 3 14-06-16 à 09:30

gagnéLe dernier survivant lorsque n=2016 est le plot numéro 653.

Posté par
pondy
re : Juin 2016, énigme 3 14-06-16 à 09:36

gagnébonjour
le dernier survivant est le plot numéro 653.
en programmant en python ....

Posté par
sarriette84
re : Juin 2016, énigme 3 14-06-16 à 14:17

perduBonjour,
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

Posté par
pythamede
re : Juin 2016, énigme 3 14-06-16 à 14:42

gagné653 est le numéro du dernier survivant.

Posté par
evariste
re : Juin 2016, énigme 3 14-06-16 à 17:20

perdu1884

Posté par
jonjon71
re : Juin 2016, énigme 3 14-06-16 à 20:25

gagné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.

Posté par
Achdeuzo
re : Juin 2016, énigme 3 14-06-16 à 20:29

gagnéBonsoir

Je pense que le dernier des 2016 plots à rester allumé est le plot numéro 653.

Merci pour cette énigme !

Posté par
rschoon
re : Juin 2016, énigme 3 14-06-16 à 20:36

gagnéBonjour à tous.

Je propose 653.

Merci pour l'énigme

Posté par
benmagnol
re : Juin 2016, énigme 3 14-06-16 à 21:29

gagné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

Posté par
LittleFox
re : Juin 2016, énigme 3 15-06-16 à 12:27

gagné
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 :

n57101522324871106159238356534800120017992698404760709104
u22233232233232322332
d11012021012020210120

On s'aperçoit que n suit presque une progression géométrique : n_{i+1} = \frac{3n_{i}+d_{i}}{2}. Avec d_{i} = 1 quand n_{i} est impair et d_{i} alterne entre 0 et 2 quand n_{i} est pair.

On s'aperçoit aussi que u_{i+1} = \left\{\begin{aligned}2&\mbox{ si } d_i=2\\3&\mbox{ si }d_i=0\\u_i&\mbox{ si }d_i=1\end{aligned}\right.

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  ).

Posté par
Raphi
re : Juin 2016, énigme 3 17-06-16 à 10:46

perduSalut, je trouve 1884

Posté par
GreenT
re : Juin 2016, énigme 3 19-06-16 à 01:29

gagné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

Posté par
LEGMATH
re : Juin 2016, énigme 3 19-06-16 à 13:34

perduBonjour  littleguy ,

n=2016 ,  le dernier survivant 662.

Merci.

Posté par
yasar
re : Juin 2016, énigme 3 21-06-16 à 14:27

perdu2015

Posté par
renno16
re : Juin 2016, énigme 3 22-06-16 à 15:59

perduRéponse: 507

Posté par
renno16
re : Juin 2016, énigme 3 22-06-16 à 16:03

perduTrouvé 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 !

Posté par
Frisco
re : Juin 2016, énigme 3 22-06-16 à 19:59

gagnéBonjour,

Merci pour l'enigme. Je dirai 653.

Posté par
totti1000
re : Juin 2016, énigme 3 27-06-16 à 00:27

gagnéBonsoir littleguy,

Je propose le nombre 653.

Merci pour l'énigme.

Posté par
saer
re : Juin 2016, énigme 3 29-06-16 à 17:24

perdusi 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

Posté par
royannais
re : Juin 2016, énigme 3 01-07-16 à 12:04

perdu1079

Posté par
littleguy
re : Juin 2016, énigme 3 04-07-16 à 18:27

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.

Posté par
weierstrass
re : Juin 2016, énigme 3 04-07-16 à 19:11

gagné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à...

Posté par
LittleFox
re : Juin 2016, énigme 3 05-07-16 à 10:30

gagné
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 .

Posté par
LittleFox
re : Juin 2016, énigme 3 06-07-16 à 09:40

gagné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)

Challenge (énigme mathématique) terminé .
Nombre de participations : 28
:)67,86 %32,14 %:(
19 9

Temps de réponse moyen : 84:32:55.
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 !