## Heads or tails

Posted by Zorglub on May 5, 2012 – 5:49 am

Infinitely many coins coins are aligned, with heads facing up.

1 – Then, all coins are flipped.

2- Then, the second, fourth, sixth, … are flipped.

3- Then, the third, sixth, ninth,… are flipped.

…

k- Then, coins numbered k, 2k, 3k, … are flipped.

…

After this infinite process is done, what is the proportion of the coins numbered p, p^2, p^3, p^4, … that will be facing heads (where p>1 is an integer) ?

May 6th, 2012 at 8:33 pm

I believe that none of the coins numbered p, p^2, p^3, etc. will be facing heads up.

coin 1: tails, flip 1

coin 2: heads, flips 1 and 2

coin 3: heads, flips 1 and 3

coin 4: tails, flips 1, 2, and 4

coin 5: heads, flips 1 and 5

coin 6: heads, flips 1, 2, 3, and 6

coin 7: heads, flips 1 and 7

coin 8: heads, flips 1, 2, 4, and 8

coin 9: tails, flips 1, 3, and 9

coin 10: heads, flips 1, 2, 5, and 10

From the pattern above, coins 1, 4, and 9 end up tails. These are the only three square numbers between 1 and 10.

The flipping pattern in this problem works out so that each coin is flipped once for each integer factor it has. To end up facing heads, a number needs to have an even number of factors, which most numbers do because factors come in pairs, i.e. 28 has factors 1×28, 2×14, 4×7. The only time a number will have an odd number of factors and therefore end up facing tails will be when it’s a square number, i.e. 64 has factors 1×64, 2×32, 4×16, 8×8. This coin would get flipped 7 times (only flipped once on the 8th flipping sequence, not twice).

May 6th, 2012 at 9:05 pm

If p is square, then p^n will be all be tails for all n. If p is non-square, but n is even, then p^n will be all tails. Otherwise they’re all heads.

I hope I’ve read the question properly.

May 6th, 2012 at 9:11 pm

for p^1,3,5,etc. 100% would be heads

for p^2,4,6, etc. 0% would be heads

May 7th, 2012 at 6:49 pm

Yes. In summary, the answer is 100% if p is square and 50% otherwise.

May 8th, 2012 at 6:44 am

I think that answer is the most exact, but it is a two-part answer. Is the probability of p>1 being sqaure 100%, 0%, or some other fraction?

May 9th, 2012 at 9:03 pm

Wow, I totally misunderstood what the question was asking. Please disregard my answer. Holy schnikes…

May 10th, 2012 at 6:01 am

For completeness: The first point was suggested by Slavy in a previous problem. If n is non-square, and it has a factor, a, such that n = a*a’, where a < a’, then we have two ways of factorising n i.e. a*a’ and a’*a. If there are other factors, b and b’ such that n = b*b’ = b’*b, we still have an even number of ways of factorising n. IFF n is a square, we have the special case of a = a’, giving an odd number of divisors of n.

Another, possibly more useful analysis is: any positive integer can be written uniquely as as the product of primes (q), to wit: n = Product q

_{i}^m_{i}. q^{m}has factors 1, q, q^{2}, q^{3}, …, q^{m}; that’s 1+m factors. It follows that, altogether, the number of divisors of n is Product (1 + m_{i}). If at least one m_{i}is odd, then 1+m_{i}is even and the number of divisors is even. But if (IFF) every m_{i}is even, then every 1+m_{i}is odd and so the number of divisors of n is odd.Either way, we end up with only the squares with tails showing, as only they get flipped an odd number of times.

Back to the problem. For the final part we have that p

^{n}is tails if p is a square. If p is non-square then p^{2}, p^{4}, p^{6}will be tails, and p^{1}, p^{3}, p^{5}.. will be heads, hence the 50% result.I’m sorry, that’s not as good as I’d like it to be, but I’ve been and am too busy to polish it up.