Need formula or equation to solve simple puzzle

[touch]

Need formula or algorithm to solve simple puzzle

Problem: You have 100 balls with their numbers written on them. You throw away the first ball, skip the second, throw away the third, skip the fourth, etc. When you get to the end you loop back to the beginning of the remaining balls. So after the first pass through you'll end up with the even numbered balls (2, 4, 6, ... 100). Because on the first pass you kept 100, on the second pass through you'll throw away 2, keep 4, throw away 6, etc. You keep throwing away a ball and skipping one until there's one ball left. Which numbered ball is left?

I know the answer by just going through it manually, but I was wondering if there's a way to do this with a formula/Algorithm/some math way. I'll be translating the answer into computer code.

Thank you.

 

[daon2]

Maybe this will be of help

http://www.freemathhelp.com/forum/threads/79929-Discrete-math-recurrence-relations

 

[touch]

Thank you daon2. I'm sure there's an answer there but it's as foreign to me as the Greek language is. I don't understand f(2n)=g(N)=2f(n)−1 or or how to translate that into computer code. And mine would eat the mice (throw the ball away) starting from number 1 and not number 2.

 

[daon2]

Thank you daon2. I'm sure there's an answer there but it's as foreign to me as the Greek language is. I don't understand f(2n)=g(N)=2f(n)−1 or or how to translate that into computer code. And mine would eat the mice (throw the ball away) starting from number 1 and not number 2.

It was not an answer to your specific question. I felt it would aid in your thoughts about it, as a similar relationship will no doubt hold true here. Let f(N) be the ball you end up on, where N is the number you start with. If you can write a formula for f(2N) in terms of f(N), then you need only the answer for the the 25 ball question, since you can divide 100 by 2 twice to get f(100) in terms of f(25).

In any case, have you looked for a pattern? f(1), f(2), f(3), ... etc.

 

[touch]

Thanks for trying but I just not going to get it. I know the the ball numbers that stay are doubled in each pass through (e.g. 2, 4, 8, 16, 32, 64). But I can't figure out how to calculate it in a math way. Oh, well.

 

[touch]

Thanks. The answer is 72 and not 64. I can do it in a similar way to what you have, but I remove or destroy the array element. I create 1 to 100 array element with those values. I loop through and remove every other one and you end up with 72. I would like to get the same answer using a one line mathematical algorithm.

 

[touch]

You're welcome to disagree, however, when you start with throwing away the first ball (and not the second) then you end up with 72. If you start with skipping/saving the first ball and throw the second, then the answer becomes 73. The 64th ball is dropped on the fourth pass, and it takes seven passes to get to the final ball (72).

You may be loosing track of the last skip or throw at the end. When you rap around again you got to continue with where you left off. For instance, at the end of the third pass 100 is thrown away, and looping to the beginning of the fourth pass means we keep 8, throw away 16, keep 24, throw away 32, keep 40, throw away 48, keep 56, throw away 64, keep 72, throw away 80, keep 88, throw away 96, and that's the end of the fourth pass/loop. The start of the fifth pass/loop, we keep 8, throw away 24, etc.

With only 10, I get # 4 left and it takes three passes (starting with throwing away number 1).

 

[daon2]

You were asking for a simpler way to do this problem. I will try to explain in more detail how to do this.

Again, let f(N) be the value we land on when playing with N balls. As you have managed to find that f(100) = 72. Let us see if we can make it simpler. Assume N=2K is even.

At the start we have balls 1,...,2K and throw away the first, third, etc. We are left with only the evens.

\(\displaystyle \begin{array}
\,\,\,\,\,\,\text{Start (100 Balls): } & B_1 & B_2 & B_3 & \cdots & B_{2K-1} & B_{2K}\\
\text{ After Step 1 (50 Balls): } & B_2 & B_4 & B_6 & \cdots & B_{2(K-1)} & B_{2K}
\end{array}\)

Let \(\displaystyle A_i = B_{2i}\) so that the above becomes:

\(\displaystyle \begin{array}
\,\,\,\,\,\,\text{Start (100 Balls): } & B_1 & B_2 & B_3 & \cdots & B_{2K-1} & B_{2K}\\
\text{ After Step 1 (50 Balls): } & A_1 & A_2 & A_3 & \cdots & A_{K-1} & A_{K}
\end{array}\)

Now, forget the original problem for a second, and suppose we play the game with the relabeled balls \(\displaystyle A_1, A_2, ..., A_K\). Say \(\displaystyle f(K) = A_x\), the ball we land on is the \(\displaystyle x^{th}\) from the second list. Remember that is just \(\displaystyle B_{2x}\). Since step 1 is part of the algorithm to obtain the solution, this ball is the one we land on playing the game with the original set of balls.

So, we have \(\displaystyle f(2K) = B_{2x}\). What this says is that if we land on the \(\displaystyle (2x)^{th}\) playing the \(\displaystyle N=2K\) game, then we land on the \(\displaystyle x^{th}\) ball playing the \(\displaystyle N/2=K\) ball game. i.e. \(\displaystyle f(2K) = 2f(K)\).

How does this help simplify your problem? \(\displaystyle f(100) = f(2\cdot 50) = 2f(50) = 2f(2\cdot 25) = 4f(25)\). So if you find the answer for the 25-ball game (18 in this case), you can multiply your answer by 4 to get the solution to the 100 ball game.