Qué número sigue vivo?

Question

Hay $100$ personas de pie en un círculo numerado de$1$$100$. La primera persona está teniendo una espada y mata a la persona de pie junto a él hacia la derecha yo.e $1$ mata a $2$ y así sucesivamente. Cual es el último número para permanecer vivo? También si $1$ mata a la persona de pie junto a él. Cual es el último número de pie? Pueden ambos ser generalizado?

Answer 1

El primer caso es similar al Problema de Josefo y en general de la situación, podemos utilizar el siguiente código de MATLAB para obtener el número restante:

Primer Caso:

function RemainNum = JosephusProblem(n,m)
A = 1:n;
A = A';
for k = 1:n-1
  A = circshift(A,length(A)-mod(m+1,length(A)) + 1);
  A = A(1:(end-1));
RemainNum = A;

donde $n$ es el número total de persona en este círculo y de la persona #1, conteo de personas número uno por uno, desde 1 a $m$ circularmente y la persona que te dice el número de $m$ se mató y este proceso no termina hasta que sólo hay una persona a la izquierda, a continuación, devuelve la función de este tipo con suerte por $\text{RemainNum}$. Así que en este caso, $m=2$. Conteo de personas como $1,2,1,2,...$ y las personas que cuentan con 2 maten.

Segundo Caso:

Deje $f(n)$ ser el número de la suerte en este caso, entonces supongo que $$f(n) = \begin{cases} 1, &\text{if %#%#%}\\ n-1, & \text{if %#%#% is even} \\ n-2, & \text{if %#%#% is odd} \\ \end{casos}$$ Ya que cada vez en más de 2 personas muertas y 1 persona muere sólo cuando hay sólo 2 personas a la izquierda, así que cuando $n=1$ es incluso, finalmente, habrá sólo 2 personas a la izquierda después de $n$ los tiempos de la matanza y la persona $n$ obtiene la espada, por lo $n$ en este caso. Al $\frac{n-2}{2}$ es extraño, después de $n-1$ los tiempos de la matanza, habrá 3 persona de la izquierda, y la persona $f(n) = n-1$ obtiene la espada y luego mata a los otros dos, por lo $n$ en este caso.

Answer 2

Escribir en binario y shift (con rotación cíclica) un poco a la izquierda - ;-) El cerrado fórmula es: $$ f(n) = 2 \cdot ( n - 2^{\lfloor log_2n \rfloor}) + 1 $$

Más detalles pueden ser encontrados en Concreto de las Matemáticas por Donald Knuth, en el capítulo 1.3.

Answer 3

Primer caso : Si 1 mata a 2, luego 2 no se puede matar a 3 porque él está muerto. Así que estamos a cada número impar matar a la par de la persona. Así, Actualización después de @coffeemath comentario

Después de la 1ª ronda: $$1,3,5,7,9\cdots99$$ 2ª ronda:$$1,5,9,13\cdots97$$ 3ª vuelta:$$1,9,17,25\cdots97$$ 4ª ronda:$$9,25,41,57,73,89$$ 5ª ronda:$$9,41,73$$ 6ª ronda:$$9,73$$

Y 73 mata a 9 finalmente. :)

Para calcular he utilizado una hoja de excel y comenzó a marcar a la gente viva después de la 1ª ronda 2ª ronda y así sucesivamente.

Segundo Caso: 100 está de pie junto a 1, debido a que ellos están de pie en círculo. Así, 1 mata de 2 y 100 (ambos inclusive). 3 mata 1 y 4, cos 1 está vivo y junto a 3 ahora bien, y esto va en. Así, la secuencia de

$$\begin{align}\\ 1-100,2\\3-1,4\\5-3,6\\7-5,8\\9-7,10\\...\\...\\99-97 \end{align}$$

No hay nadie para matar 99. Por lo que el 99 está vivo. :)

Answer 4

Esto es para el primer caso, donde la matanza procede solamente de las agujas del reloj. Deje $f(n)$ ser la posición de la última persona viva. A continuación, podemos mostrar dos recursiva declaraciones para determinar el $f(n)$ (dado el nivel inicial de $f(1)=1$): $$f(2n)=2f(n)-1, \\ f(2n+1)=2f(n)+1.$$ Para el $f(2n)$ de los casos, el resto de números después de una ronda se $2\cdot 1-1,\cdots 2n-1.$ (y el $1$ está viva en la siguiente ronda) Esta es una lista de $n$ números de $2k-1,$$1 \le k \le n$, por Lo que si conocemos el valor de $f(n)$ podemos ajustar a donde está en esta lista, y obtener $2f(n)-1$ $f(2n).$

Para el $f(2n+1)$ de los casos, una ronda de nuevo, incluso mata a los valores indizados, pero la última posición $2n+1$ ahora sostiene la espada, y luego matar a $1$, lo que nos deja con los números de la lista $2\cdot 1+1, \cdots, 2n+1$ ($3$ vivo) que es de nuevo una lista de $n$ números, por lo que de manera similar a la anterior, si sabemos $f(n)$ se puede ajustar hacia donde está en esta lista para obtener $2f(n)+1$ para el valor de $f(2n+1).$

La aplicación de estos recursiones a $f(100)$ hemos $$f(100)=2f(50)-1,\\ f(50)=2f(25)-1,\\ f(25)=2f(12)+1,\\ f(12)=2f(6)-1,\\ f(6)=2f(3)-1,\\ f(3)=2f(1)+1.$$ Luego de conectar $f(1)=1$ y trabajando hacia arriba da $f(100)=73$ (como en el del Monje respuesta).

Estos recursiones daría $f(n)$ cualquier $n$, pero no en una forma cerrada, que sería más agradable.

Añadido: mirando a $n$ en base 2 y utilizando la anterior recursiones, uno puede obtener la siguiente "casi" forma cerrada. Si $2^k \le n < 2^{k+1}$ $$f(n)=2(n-2^k)+1.$$ En particular, $f(n)$ debe ser impar en todos los casos, algo inesperado (para mí). Este formulario es otra versión de la cita fex en su respuesta anterior, de Knuth.

Answer 5

bien porque la $1$ matar a $2$, $3$ matar a $4$,lo que significa que hemos de números impares, después de una ronda

1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99

ahora continuamos de nuevo o que ?después de otra ronda tenemos estos números

1

5

9

13

17

21

25

29

33

37

41

45

49

53

57

61

65

69

73

77

81

85

89

93

97

el resultado final es de 73