A pirate turned mathematician

Probability Level 3

Once, a fleet of $2018$ pirates were captured by an opposing fleet, who intended to kill them all. However, since they were in a good mood that day, they decided to let one of the $2018$ pirates go. The way they did it was as follows:

They sat the pirates in a circle on seats numbered $1,2,...,2018$ in clockwise order.
Then, starting from the pirate on seat $1$ and moving clockwise, they killed every second pirate that was still alive (in this case, they would kill the pirates sitting on seats $2,4,6,...,2018$ in that order, and then kill those in seats $3,7,11,$ etc.).
This was continued until only one pirate was still alive, who was then released.

Being the only mathematically adept pirate on the ship, Grigori was able to calculate which seat he needed to sit in (call this seat $n$ ), and thus managed to escape. He then decided to pursue a quiet life doing mathematics.

A long time later, as he was thinking about this day, he thought of an interesting problem: Let $f(x)$ (where $x$ is an integer greater than one) be equal to the seat where one would have to sit to save oneself if there were $x$ chairs arranged in the above fashion, and let $k$ be a positive integer, also greater than one.

Find all $k$ such that $\displaystyle\sum_{x=2}^{2^k-1} f(x)$ is a perfect square, and input your answer as $n$ multiplied by the sum of all possible $k.$

If you think the answer is infinity, give $-1$ as your answer.

The answer is 3978.

2 solutions

Uros Stojkovic
Aug 7, 2018

We will try to generate recurrence relation between functions with distinct inputs. For odd $x$ , after we get rid of even numbers and the first number, we are left with:

$\begin{aligned} 3,~5,~7,~&\cdots~,~x-2,~x.~~~~\bigg\}f\left ( x \right ) \\ &{\color{teal}\bigg\downarrow~~k:=\frac{k-1}{2}}\\1,~2,~3,~&\cdots~,~\frac{x-3}{2},~\frac{x-1}{2}.~~~\bigg\}f\left ( \frac{x-1}{2} \right )\\\implies f(x) &= 2f\left( \frac{x-1}{2}\right)+1 \end{aligned}$

Similarly, for even $x$ we have:

$\begin{aligned} 1,~3,~\cdots&~,~x-3,~x-1.~~~~\bigg\}f\left ( x \right ) \\ &{\color{teal} \bigg\downarrow~~k:=\frac{k+1}{2}}\\1,~2,~3,~&\cdots~,~\frac{x-2}{2},~\frac{x}{2}.~~~\bigg\}f\left ( \frac{x}{2} \right )\\\implies f(x) &= 2f\left ( \frac{x}{2} \right )-1. \end{aligned}$

Since $2018 = 2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot 3 + 1)+1)+1)+1))))+1)$ ,

then $f(2018) = 2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot(2\cdot 3 + 1)+1)+1)+1)-1)-1)-1)+1)-1= 1989.$

X X
Aug 7, 2018

$f(x)=2(x-a)+1,a=\text{"the biggest power of 2 not bigger than x"}$ (View this and @Satyen Nabar's solution)

I'll do the rest of the things.The value of $n$ is $2(2018-1024)+1=1989$

$\displaystyle\sum_{x=2}^{2^k-1} f(x)=4+4^2+...+4^{k-1}$ ,so only $k=2$ will get a perfect square $4$

Hence, $nk=3978$

A pirate turned mathematician

The answer is 3978.

2 solutions

0 pending reports