Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2006-04-16 02:32:38

dynamitedan
Novice

Offline

Can you solve this?

Some children are going to play a game, but before they start, they need to decide who is to be "it". In order to find "it", they stand in a circle and say "in, out, in, out......." pointing at each child around the circle, and any child who is "out" leaves the circle. This continues until only 1 child is left, and they are "it".

What is the formula which will predict who will be it?

And if the children change to "in, in, out........." what would the formula then be?

#2 2006-04-16 02:53:32

mathsyperson
Moderator

Offline

Re: Can you solve this?

With the in-out-in-out form, this shows the first few results, if it always starts with the 1st child:

   Number of children playing            |            Child who is it   
-----------------------------------------------------------------------------------
                    1                                |                      1
                    2                                |                      1
                    3                                |                      3
                    4                                |                      1
                    5                                |                      3
                    6                                |                      5
                    7                                |                      7
                    8                                |                      1
                    9                                |                      3
                    10                              |                      5

From that, it looks like the pattern is that it starts at 1 and counts up odd numbers until it reaches the point where the number is the same as the number of children playing and at that point it goes back to 1 and starts again.

So there's the pattern, but I can't think of how you'd make that into a formula.

For the in-in-out format, you get this for the first few:

Number of children playing              |            Child who is it   
-----------------------------------------------------------------------------------
                    1                                |                      1
                    2                                |                      2
                    3                                |                      2
                    4                                |                      1
                    5                                |                      4
                    6                                |                      1
                    7                                |                      4
                    8                                |                      7
                    9                                |                      1
                    10                              |                      4

And I can't even see a pattern in that one. It seems to be something to do with 1, 1 4, 1 4 7... but the 2's at the start ruin that theory. I'll try to dig into this more later on. I hope I've helped you a bit though.


Why did the vector cross the road?
It wanted to be normal.

#3 2006-04-17 05:35:15

yonski
Full Member

Offline

Re: Can you solve this?

Hmm that's a tough one. You could code it recursively using something like:

function INOUT(x){
if(x == 1) then
{
    return 1
}
else
{
    if (INOUT(x-1) + 2 ≤ x) then
    {
          return (INOUT(x-1) + 2)
    }
    else
    {
          return 1
    }
    }
}
}

I can't figure out a general formula though. It's gonna bug me now.


Student: "What's a corollary?"
Lecturer: "What's a corollary? It's like when a theorem has a child. And names it corollary."

#4 2006-04-22 04:32:04

Pi Man
Guest

Re: Can you solve this?

For the first problem... it's a power of 2 thing.   Assign each player a number.   Obviously, even-numbered players won't ever win.   Below is the player number and when he wins....

Player           Wins if # of players is...
    1               1, 2, 4, 8, 16
    3               3, 5, 9, 17
    5               6, 10, 18
    7               7, 11, 19
    9               12, 20
   11              13, 21
   13              14, 22
   15              15, 23
   17              24
   19              25
   21              26

Some patterns develop....
The last player wins whenever the number of players is a power of 2 minus 1 (3, 7, 15, 31).
Player 1  wins whenever the number of players is a power of 2 (2, 4, 8)
Player 3 wins whenever the number of players is a power of 2 plus 1 (3, 5, 9)
player 5 wins whenever the number of players is a power of 2 plus 2 (6, 10)
Player 7 wins whenever the number of players is a power of 2 plus 3 (7, 11)
... and so on. 

So for N players, the winner will be 2 * [N mod 2**X] + 1, where 2**X is the greatest power of 2 that is less than N.

For example, if there are 63 players the answer should be 63 (since 63 is 2**6 - 1).  Double checking our formular... 32 is the greatest power of 2 that is less than 63
          2 * [N mod 2**X] + 1 = 2 * [63 mod 32] + 1
                                           = 2 * 31 + 1
                                           = 63

For N = 100, it would be 2 * [100 mod 64] + 1 = 2 * 36 + 1 = 73

I haven't look at the 2nd problem yet but I wouldn't be surprised if it's based on the powers of 3.

Board footer

Powered by FluxBB