1

There are 128 numbers 1, 2, . . . , 128 which are arranged in a circular pattern in clockwise order. We start deleting numbers from this set in a clockwise fashion as follows. First delete the number 2, then skip the next available number (which is 3) and delete 4. Continue in this manner, that is, after deleting a number, skip the next available number clockwise and delete the number available after that, till only one number remains. What is the last number left ? Source

Some examples I've calculated by considering shorter number strings: $$ 1,2 \to 1$$ $$ 1,2,3 \to 3$$ $$ 1,2,3,4 \to 1$$ $$ 1,2,3,4,5 \to 3$$ $$ 1,2,3,4,5,6 \to 5$$ $$ 1,2,3,4,5,6,7 \to 7$$

$$ 1,2,3,4,5,6,7,8 \to 1 $$ $$ 1,2,3,4,5,6,7,8,9 \to 3 $$

I can't see any pattern in the number the string gets shot down to. Any how I tried a brute-forcish approach by doing the deletion in cycles (everytime I look back to the beginning numbers, I put an arrow):

$$ 1,2,3,4....,(128) \to 1,3,5,7....(127) \to 1,7,11 ..(??)$$

Quickly I figured that this is NOT the approach.

A bit later on, I thought of a more 'generating functionish' approach:

I thought of considering the number as a polynomial $p(x) = x^1 + x^2...+x^{128}$ then I thought maybe if I could find an operation which captures the 'deletion' process as described by the question onto this polynomial, then I would have solved the question. However, I could find only find such a process for the 'first sieve' i.e: the first time we delete till the end and reach back at the starting numbers. It is given as:

$$p_1(x) = \frac{p(x)+p(-x)}{2}$$

Annnnnd I am out of ideas

Bill Dubuque
  • 272,048
tryst with freedom
  • 11,538
  • @Burian, would you mind narrating how that cycle goes in an exemplar set of numbers? Like you take a set of numbers and demonstrate the working of your algorithm.... – Spectre Jul 06 '21 at 01:35
  • Oh ok.. no need, I guess.. I seem to have understood it. Thanks! – Spectre Jul 06 '21 at 01:37
  • Hi @Spectre I didn't see the comment since I was asleep at the time. It is Buraian by the way. Still, I appreciate the interest you had in my question. – tryst with freedom Jul 06 '21 at 15:03

1 Answers1

2

Let $f(n)$ be the last value left when starting with $1,\dots,n.$

Then $f(2n)=2f(n)-1.$

This is because the first loop removes the even numbers, and we are left with $1,3,5,\dots,2n-1.$ But that is the same as starting with $1,2,3,\dots,n,$ but if the result is $k=f(n)$ the usual way, it is $2k-1$ with the odd numbers.

We can get a similar formula for $f(2n+1)$ but we don’t need it for $f(128).$

$f(2^0)=1,$ so $f(2^k)=1$ for all $k.$

The recursion for $n$ odd is:

$$f(2n+1)=2f(n)+1$$

This is because after the first $n+1$ are removed, you have left the values $3,5,7,\dots,2n+1,$ in that order.

You can prove using the induction that:

$$f(2^m+k)=1+2k\tag1$$ for $0\leq k<2^m.$

If $k$ is even, $$\begin{align}f(2^m+k)&=2f(2^{m-1}+k/2)-1\\&=2(1+2(k/2))-1\\&=1+2k.\end{align}$$

If $k$ is odd,

$$\begin{align}f(2^m+k)&=2f(2^{m-1}+(k-1)/2)+1\\&=2(1+2(k-1)/2)+1\\&=1+2k.\end{align}$$

You can get a simple recursion:

$$f(n)=(f(n-1)+2)\bmod n$$

where you need $n\bmod n=n,$ not the usual value $0.$ I suppose you can use the standard $\bmod$ Operation with the slightly uglier formula:

$$f(n)=\left((f(n-1)+1)\bmod n\right)+1$$

This is because $k\mapsto ((k+1)\bmod n)+1$ maps $1,2,3,\dots,n-2,n-1$ to $3,4,5,\dots,n,1,$ respectively.

Thomas Andrews
  • 177,126
  • How is 1,3,5...,2n-1 give the same last number as 1,2,3...,n? I think you would have to prove this.

    " but if the result is k=f(n) the usual way, it is 2k−1 with the odd numbers." This part is not clear to me , could you explain how you arrived at 2k-1 if it is an odd number

     – tryst with freedom Jul 06 '21 at 15:00
  • Technically, yes, everything should be proved. But this is a basic bijection argument. Applying the process to two different sequences of distinct objects of length $n,$ $(a_1,\dots,a_n)$ and $(b_1,\dots,b_n)$ if the ending object is $a_k$ in the first, it is $b_k$ in the second. This is because only the position matters in the process, not the value. @Buraian – Thomas Andrews Jul 06 '21 at 15:23
  • And I did not say $1,3,5,\dots,2n-1$ gives the same number as $1,2,\dots,n.$ I said if $1,2,\dots,n$ gives $k$ then the odd numbers give $2k-1.$ It just so happens that when $k=1,$ $2k-1=k,$ which is all you need for $f(128)=1.$ – Thomas Andrews Jul 06 '21 at 15:27
  • If you play this game with a sequence of $n$ cards, it doesn’t matter what is written on the cards, only the original order of the cards. If the cards are labeled with $1$ to $n$ in order, and the card $k$ is the final card, then for any starting configuration of $n$ cards, the final card with be the $k$th card from the starting configuration. But writing that out mathematically is tedious, requiring a more formal definition of the process, and a lot of fiddly but trivial math. – Thomas Andrews Jul 06 '21 at 15:49
  • I'm having a hard time thinking about what you are saying, I'll reread it a few more times and in time and comment again if I can pin down what I don't get. Now I understood the the same last number thin but I am confused about f(2n) = 2f(n)-1 – tryst with freedom Jul 06 '21 at 17:01
  • 1
    Holy ** I finally understood after staring at it for sooo long. This was truly a genius answer 10/10 – tryst with freedom Jul 06 '21 at 17:45
  • $3,5,7,...,2n+1 \to 1,2,3...,n$ in the first sequence, the term is 2j+1 , starting from j=1, so find that j lands on the second sequence and multiply it by 2 and add one – tryst with freedom Jul 06 '21 at 17:45
  • 1
    Technically, the arrow should go the other way: $1,2,\dots,n\to 3,5,\dots,2n+1$ via $j\to 2j+1.$ – Thomas Andrews Jul 06 '21 at 17:51