El acertijo clásico del círculo suicida: ¿sobrevivirías?

 

 (Un texto de Raquel Marquez, el 21 de noviembre de 2016 en elconfidencial.com)

Un matemático ha resuelto satisfactoriamente este antiguo problema planteado por Flavio Josefo, historiador del siglo I d.C. y líder judío contra los romanos

Formas parte de un grupo de 41 rebeldes hebreos a principios de nuestra era. Habéis sido capturados por los romanos, que os han encerrado en una cueva, y tus compañeros se niegan a morir a manos del Imperio. Antes que dejaros matar, os suicidaréis.

Te muestras de acuerdo, valiente hasta las últimas consecuencias: formaréis un gran círculo humano. Todos están dispuestos a cumplir el acuerdo y no puedes decepcionarles. El primer voluntario matará al hombre situado a su izquierda. El siguiente en la misma dirección (el primero vivo a la izquierda) tendrá entonces el turno y matará al de su izquierda, y así sucesivamente. La luz se apagará para todos, sí, pero permanecerá vivo el espíritu de la rebelión. Esos puercos podrán ganar la batalla, pero no la guerra. O la guerra también, pero no irán al Cielo. Porque el Cielo existe seguro... ¿no?

Realidad y ficción

Veamos. Pensándolo bien, si los romanos fueran clementes, quizá tendrías alguna posibilidad. Después de todo, eres muy joven para morir. Quizá haya algún lugar de la mortífera rueda en el que podrías retrasar un poco el momento. ¿Y si resultaras el único superviviente? Libre de las miradas que te juzgarían (y del bulto) de los otros 39, quizá podrías esconderte, o negociar con el enemigo. A lo mejor no son tan infames, ¡hacen buenos acueductos!

Aunque hemos fantaseado un poco, el fondo de la cuestión sucedió más o menos así en el año 67 d.C. Realmente hubo un asedio romano en el territorio del actual estado de Israel, en la ciudad de Yodfat. Lo cuenta Flavio Josefo, hombre de acción e historiador, caudillo de las rebeliones judías. Explicó a la posteridad una situación similar que se dio entre él y otros 40 hombres. En la versión referida por él, echaron a suertes quién acabaría con quién y cuando quedaron, casualmente, él y otro más, convenció al otro, amigo suyo, para que se entregaran. Con esa base, muchos matemáticos se han acercado al problema a lo largo de la historia: ¿hay una forma de averiguar, sea cual sea el número de rebeldes, cuál es el lugar indicado para sobrevivir hasta el final?

El canal de Youtube 'Numberphile' ('Numerófilo') ha dado una solución en vídeo por boca de Daniel Erman, matemático de la Universidad de Wisconsin-Madison (https://www.youtube.com/watch?v=uCsD3ZGzMgE). Erman ha estado buscando patrones con diferentes cantidades de soldados y ha encontrado una solución que le permite salir vivo haya los que haya. La primera conclusión que ha encontrado a base de apuntar los resultados en un papel es sencilla: si asignamos al primero que mata 'la posición 1', estar situado en una posición impar es necesario para sobrevivir. Los rebeldes pares morirán seguro en la primera vuelta, porque, como hemos visto, el primero apuñala al segundo, el tercero al cuarto, el quinto al sexto... 

Si simplificamos con cantidades pequeñas pares; por ejemplo, si hay solo dos soldados en total, el primero mata al segundo y sobrevive. Si hay cuatro personas, sobreviven el primero y el tercero. No importa cuánto aumentemos el número de participantes, el que empieza cada ronda siempre queda vivo y puede empezar la siguiente vuelta, así que, si te ves en esta situación, preséntate voluntario sin dudar para empezar la matanza. En cambio, es mucho más complicado cuando el número total es impar, porque, tras la primera vuelta, ese orden tranquilizador se pierde. 

Te invitamos a hacerlo con lápiz y papel e ir aumentando la cantidad, siempre con números impares, igual que este matemático en el vídeo (tiene subtítulos en inglés*).

Con cinco soldados, por ejemplo, el primero mata al segundo, el tercero mata al cuarto... y el quinto mata al primero. Si te ves en estas, lo que te conviene es empezar tú a matar y también que, cuando acabe cada vuelta, sigas siendo el primero. Además, el número total debe seguir siendo par. Porque, si es impar, el último te va a matar a ti (porque quedará a tu derecha).

Si, por ejemplo, sois 6:

Vuelta 1) 1 mata a 2, 3 mata a 4, 5 mata a 6 y 7 mata a 8. Quedan 1, 3, 5 y 7.
Vuelta 2) 1 mata a 3, 5 mata a 7. Quedan 1 y 5.
Vuelta 3) 1 mata a 5. ¡Genial! Estás vivo.

Como en cada vuelta el número de gente se va a reducir a la mitad, la única forma de que el número siga siendo par en cada ronda es que sea potencia de 2 (que se pueda obtener multiplicando por 2). Es decir, te valen 2 personas, 4 personas, 8 personas, 16 personas, etc. Por suerte, las potencias de 2 no se acaban.

En cada vuelta volverás a matar, y volverá a quedar un número par de gente. Bueno, en la última será impar, claro. Quedará uno. Quedarás tú

Si has visto el vídeo de YouTube quizá tengas tentaciones de replicar: "Pero el número de gente en el vídeo eran 41. Y además el señor ha dicho que yo tenía que ser el 19, no el 1". Ya. Hay veces que no tenemos, de partida, la situación ideal, y entonces debemos crearla. En otras palabras, tenemos que aplicar matemáticas.

Tú quieres (porque hemos explicado que quieres) ser el primero en un grupo de gente que sea potencia de dos. Pero no hace falta que lo seas desde el principio, basta con que lo seas en algún momento. Piensa que, como estás hablando en un círculo, cualquier momento puede ser "el principio" para ti. Menos si estás muerta. Entonces no.

Es decir, lo que tenemos que hacer es conseguir que llegue un momento en que:

1. Te toque matar a ti.
2. El número total de gente que quede sea potencia de 2.

En este caso tenemos 41 personas. Pero queremos que haya 32 cuando llegue tu turno. Porque 32 es potencia de 2 y es un número muy bonito (de hecho, es la potencia de 2 más grande menor que 41). Así que necesitamos que, cuanto te toque matar a ti, hayan muerto 9 personas.

Y, como solo van a morir los impares, necesitas que haya 18 personas antes que tú. Cuando llegue tu turno, quedarán 9. De hecho estarán, vivas:

• 9 personas con el cuchillo ensangrentado que iban "antes que tú".
• Tú.
• 22 personas que van después de ti.

Pero como esto es un círculo, esto es lo mismo que decir que estás:

• Tú.
• 31 personas que van después de ti.

Y has conseguido tu objetivo. En cada vuelta (o sea, cada vez que llegue hasta a ti otra vez el turno) volverás a matar, y en cada vuelta volverá a quedar un número par de gente. Bueno, en la última vuelta quedará un número impar, claro. Quedará uno. Quedarás tú.  

***

(*) Los subtítulos del vídeo. Merece la pena verlo.

So it's called the Josephus Problem. It's based on something from history.
There was a group of Jewish soldiers who were surrounded by the Roman army and they didn't want to get captured, so they decided to come up with a system-
- to avoid getting captured or suicide.
So they'd sit in a circle, and the first man would kill the guy to the left of him.
The next remaining living person would kill the next remaining living person with their sword.
And they'd go around like this, till there's only one person left,
and the last person would have to commit suicide of course, rather than get captured.
And the story - at least the story I was told, I'm not sure if this is historically accurate - Was that Josephus preferred captured to suicide,
but he worried that if he said this, the other soldiers would turn on him.
And so he wanted to figure out: WHERE should he sit within the circle- in order to be the last man living.
And then he would surrender, rather than kill himself.
That was the problem

It's a little tricky, so let's do a smaller example.
Let's say there are seven people.
And so just to be clear, the way it works is: person number one kills number two.
Person number three kills four,
Five kills six,
But now things gets a little of harder to kind of see in advance
Because seven, there is no eight, so seven kills one,
Three kills five,
Seven kills three.
So seven's the winner; seven is the last one left over.
For Josephus, there were 41 people. He needed to figure out where to sit.

The mathematical problem is if there were n people.
Where's the winning seat?
When I learned this problem I was in high school,
And it was one of the first problems that got me to understand how you approach-
- difficult and- and...
Math problems where you don't know the answer in advance, or someone hasn't shown it to you in advance.
And it was a professor of mine
his name was Phil Hanlon
who played a big role in, kind of, leading me to math.
And he suggested: what we should do is we should gather data.
Just...
Take various values of n and just do it by hand
and start looking for a pattern.
I don't know, maybe we should just do that?
n is the number of seats, and w of n will be the winning seat.
And what we know so far is that: n is seven, w of n it turns out is also seven.
And so what I would do is I'd start doing some other values
So, I don't know, why don't I do five?
One kills two,
three kills four,
five kills one,
three kills five.
The winner is three.
I guess there was no reason for me to skip six, so why don't we fill in six.
One kills two, three kills four, five kills six...
... one kills three and five kills one.
The winner is five.
So
If you're watching you might already start to notice some patterns.
For instance, they're always odd. I mean, that's maybe the first thing you notice
And you can start asking "why are they always odd?" And maybe you can already see that-
- in the first loop around, all the even people get killed.

So you can - even with a tiny amount of experiment - start to see some patterns.
- *Brady* So you DON'T want to sit in an even seat? - Don't sit in an even seat, no no no.
And maybe we're even getting some glimmers of other patterns
But before I really try to phrase those, I'd like to fill in the table a little bit more.
So let's do some.
So if there's only one person...
well...
That person's the winner, so that one was easy.
If there's two people: one kills two. One is the winner
If there's three people: one kills two, three kills one. Three is the winner
If there's four people: one kills two, three kills four, one kills three.
If there's eight people: one kills two, three kills four, five kills six, seven kills eight,
one kills three, five kills seven, one kills five.
The winner is one.
Alright so it was one, one, three, one, three, five, seven.
One, three, five, seven, nine.
And you could keep going, but maybe you can see the pattern now?
- *Brady* Is thirteen a one? - NO! Good guess actually!
But it is not a one. So let's do thirteen.
*Brady* This is good, I don't know then, I can't see the pattern.
So as you see it's jumping by two each time, but then it resets at some point
and
And I want to go back to this, so we'll see what thirteen is quickly
So we didn't reset that, and I claim we won't reset it the next one either.
Fourteen will be thirteen
and here, by the way, we're be starting to make predictions.
It's worth noting we've-
Even though we maybe can't say exactly what like 178 would be-
- we're starting to see well enough so we can make a prediction.

so you could guess. Is it really true that fourteen is going to give you thirteen?
We could do it out, and you'll see in fact that's what you'll get
So we're getting some understanding...
But I want to go back to this point you had, you asked if it's going to reset and go back to one there
And the answer was no, and it's worth looking.
Because this is the next thing I was going to do.
Where do we get the ones?
So if you look for a sec, there's something very special about the numbers that give you ones.
It's the powers of two.
And so maybe you can now guess that if i put in a sixteen, I would get a one back.
And that'll be right, and that's actually going to be a real key in unlocking this.
The professor I was learning this from made a really big point out of this.
And I thought, you know, well
I don't know what the general answer is yet!
And he made a big point: If you know something...
Prove it, and make sure you really understand that one thing, and that often unlocks the rest.

So he really pushed us when I was first doing this, to try to state a conjecture and then prove a theorem-
based on what we just saw here.
And so that's what I want to do, so here's the conjecture:
If n is a pure power of two, then the winning seat is one.
I want to think about this for a second and maybe see why this might be true.
So let's do the next biggest power of two, maybe the biggest one I can bother writing down.
So let's do sixteen
So I want to do one pass through the circle.
- *Brady* Take out all the evens. - Take out all the evens.
And now, fifteen has just killed sixteen.
So I'll put a little dot here so we'll remember it's number one's turn again.
And it's number one's turn again, and we've removed all the evens.
And what's left is therefore exactly half as many.
So if i relabel at this point
You can see that there's a power of two to start with.
I pass through the circle once, I get rid of all the evens, I have half as many.
And I'm back at number one's turn.
So now if I do this again, the same thing ought to happen.
Right? I should kill all the evens on the new labeling
And now there are four people left, and it's STILL number one's turn
So you go through again...
Kill those guys, there's two people left, it's still number one's turn-
- and that one kills that, and it's still number one's turn and that chair wins.

So let's say we believe that. We know what happens to two to the n.
So how do we explain what happens between the pure powers of two?
If you see the pattern, you know- we know what happens at eight, and we know what happens at four...
... but between them it goes up by twos until at this point, if I added two to seven, I'd have a nine
Which would be too big anyway, so that's our reset
But we knew it was going to reset because it's a pure power of two.
So how do we explain this jumping by two phenomena inbetween?
So what I'm going to do- I'm gonna just mention that:
For any number-
- you can write it as a big power of two plus something else
Take the biggest power of two you can subtract from a number-
And then what's left should be smaller than that.
When you express a number in binary notation-
- ou choose zeroes or ones, and that gives it out as a sum of a bunch of powers of two...

... and you just choose the biggest one.
So 77. The biggest power of two I can get is 64.
And then, what is it, it's 64 + 13.
So then for 13, the biggest power of two is 8 + 4 + 1. Did I do this right?
72... 77, there you go. And these are all powers of two!
And this is unique. This is the unique way to write 77 as a sum of powers of two.
Where no powers repeated, that's a key point.
So if you wanted to take a general number, take the biggest power of two - 64 - and then the remaining part.
*Mumble* Twelve... Thirteen.
I'm going to call this part two to the a, and the remaining part I'm going to call l
And I claim that this l is going to tell us which of those odd number between are going to show up.
So let's see how. How about we do thirteen.
n is thirteen.
This is the binary expansion, but using our new method the eight will be the two to the a-
- and the five (which is the four plus one) that'll be the l.

And here's the thing that's going to happen with the l:
I'm going to do five steps.
So 1 kills 2, 3 kills 4, 5 kills 6, 7 kills 8, 9 kills 10.
So now I've dropped...
l people.
And it's number eleven's turn.
Now watch what happens, how many people are left? Well what's left is a power of two.
And we know who wins in a power of two, it's whoever starts!
*Brady* The first killer.
The first killer! So now, if we go from here I claim that eleven is going to win.
And just watch, it's going to be.
11 kills 12, 13 kills 1, 3 kills 5, 7 kills 9
Back to eleven, and now there's only four people left.
11 kills 13, 3 kills 7...
Back to eleven, two people... Eleven wins.
And so this is really the key to the final answer.
Which is
If you've written your number as two to the a plus l-
- after l steps, whosever turn it is is going to win.

Because it's going to be their turn and there'll be a power of two left.
And so the winning seat will be two l plus one.
If you write it in this way, because that's whose turn it is after l steps.
The theorem or the claim, is that if you've written n in this way...
So if n is two to the a plus l, where l is less than two to the a.
It has to be strictly smaller
So in other words: two to the a is the biggest power that sat inside of n.
Then the winning seat is going to be 2 l plus one.
So we've already seen it was true here, right?
l was five and the winning seat was eleven, which is two times five plus one.
And if you start going back through you'll see it's the same thing for all the answers.
We've already illustrated the mechanisms, which is after l steps-
It's the turn of person 2 l plus one, and after l steps, there are a power of two number of people left.
and...
Everyone knows that the power of two people, the first person who kills, that's who's going to be the winner

*Brady* - I think I follow. Now in the Josephus problem...
- Yep!
- ... There was Josephus and 40 soldiers.
- That's right. Oh yeah! We got to go back and do that!
- Alright so we got 41 people...
- So n is 41
- Alright, now I think - expressing that in the way you told me to - it's going to be 32 + 9?
- There you go, 32 + 9
- So... Two lots of nine... plus one...
- Mhm
- ... is nineteen
- There we go
- So we want to sit in position nineteen.
- There you go. You want to sit in the nineteenth chair.
So here we go we're going to do n = 41
- Alright. Put them in, in the cave, waiting their fate.
- Not a very good circle but...
- It's getting smaller now...
- I know.

Okay so let's do it. So one kills two...
- We're losing our even numbers.
- Yep.
Okay now... 41 kills 1.
three kills five...
And 19 kills 35 and there we go!
- Alright.
I was right!
- There we go, nineteen!

Oh and one other thing in this problem which is kind of fun...
So this formula I wrote can be interpreted in binary notation.
When we wrote a number as a sum of powers of two...
This can be re-expressed in binary notation.
So what was this... 32 + 8 + 1
So that's...
2⁵ + 2³ + 2⁰
And binary notation...
The digits correspond to the various powers of two, and all the digits are either zero or one.
So 41 in binary notation would be one copy of 2⁵,
zero of 2⁴,
one of 2³,
zero 2², zero 2¹ and one 2⁰
101001
Here's the trick for the Josephus problem.
Which I won't justify but it's super cool, and you can try it own your own.
The way to find the winning solution if this is n-
- the winning solution in binary is you take the leading digit-
- and you put it at the end.
So in other words I claim that if I write
101001
So I take this part and then I add the first digit to the end.
010011
That number in binary code is... Well let's see...
It's 2⁰ + 2¹ + (I skipped 2² and I skipped 2³) and I add 2⁴
So it's 2⁴ + 2¹ + 2⁰
Which is
16 + 2 + 1
Which is nineteen, which is exactly what the winning seat was.
and...
And so there's this super efficient way in binary code to jump straight from the number n-
- to the winning number w(n)
So if you're writing you numbers in binary code, the pattern would've been even more quickly apparent.