Flipping Coins

Probability Level 5

Your math professor shows you 100 coins placed on his desk with their heads up.

He says to you, "Each time, you choose exactly 93 coins and flip them, turning heads to tails or vice versa."

What is the least number of times that you need to do this in order to get all 100 coins tails up?

Image credit: Wikipedia KamTANGO

The answer is 16.

5 solutions

Discussions for this problem are now closed

Satyen Nabar
Apr 16, 2014

First flip - Flip 93 coins to give 93 Tails and 7 heads up ( 7H, 93T)

Second flip - Flip 86 Tails to give 86 heads leaving 7 tails and flip the 7 heads to give total of 14 tails up ( 86 H, 14 T)

Third flip - Flip 79 heads to give 79 tails leaving 7 heads and flip over the 14 tails to give total of 21 Heads up ( 21H, 79T)

Fourth flip - Flip 72 tails to give 72 heads leaving 7 tails and flip over the 21 heads to give total of 28 Tails up (72H, 28T)

Now the pattern is clear.... multiples of 7

14th Flip -- 98 tails up and 2 Heads

15th Flip -- On this crucial flip, turn over 1 of the 2 coins that`s heads up and 92 coins that are tails up to give 93 heads leaving 7 tails up

16th Flip -- Turn over 93 heads to give 100 tails up.

Instead of flipping 93 coins at a time, look at it as "not flipping" 7 coins at a time. Now look at it as flipping 7 coins at a time. Obviously, one has to perform an even number of flips (as 93 is odd, 100 is even)

One can flip 7 consecutive coins, 13 times, to get 91 Tails. (13) Now flip 86-91 and 92nd coins to get 86 Tails. (1) Now flip 86-91 and 93, and then 94-100 to get all Tails (2)

Hence 16 tries.

Anurag Poddar - 7 years, 1 month ago

You have to explain the 15th flip clearer. (Edit: Explained, thanks!)

Also, how do you show that this is the minimum?

Calvin Lin Staff - 7 years, 1 month ago

Also, how do you show that this is the minimum?

To see that it cannot be done in less than 16 flips ( there are many ways, I'm sure, but this is how I proved it ) define $X(n)$ as:

$\bullet$ the number of tails after $n$ flips, $n$ even

$\bullet$ the number of heads after $n$ flips, $n$ odd

Then it is impossible (by parity) to have $X(n)=0$ after an odd number of flips, so we need $X(n)=100$ after an even number of flips. But this cannot be done in $14$ or fewer flips, since each flip changes $X(n)$ by, at most, $7$ .

Peter Byers - 7 years, 1 month ago

Dear Calvin I have clarified the 15th flip. Thanks. If you consider 10 coins heads up and you must flip 9 at a time, the pattern shows that it will need 10 times to turn the coins to 10 tails up and one must leave 1 coin unflipped each time. I extended the problem to 100 coins. I am afraid I cannot provide mathematical proof that this is the minimum.

Satyen Nabar - 7 years, 1 month ago

I really enjoyed this problem. Did you come up with it yourself?

Here's a proof that 16 is the minimum.

Construct the incidence matrix where the rows are the turns of the flips, and the columns are the coins. Place a 1 when the coin is flipped during the turn, and 0 otherwise. The conditions state that
1) the sum of each row is 93,
2) the sum of each column is odd.

Since there are 100 columns, the total sum of 1's is even, which implies that the number of rows is even (so we need an even number of flips).
Since the sum of each column is odd, and there are even number of rows, hence the number of 0's in each column is odd.
Now, each column needs at least one 0, hence there are at least 100 0's. In each row, there are exactly 7 0's. Hence, we need to have at least $\lceil \frac{100}{7} \rceil = 15$ rows.
But since the number of rows is even, there are at least 16 rows.

It remains to show that we can accomplish this in 16 flips, which is what you have done.

Calvin Lin Staff - 7 years, 1 month ago

@Calvin Lin – Can u please explain how is the sum of each column odd??

Sayan Dutta - 7 years, 1 month ago

@Sayan Dutta – How many flips does it take if a coin starts of as heads and ends as tails?

Calvin Lin Staff - 7 years, 1 month ago

@Calvin Lin – Simply brilliant! Thanks for the explanation Calvin :) The original problem was with 10 coins. I merely extended it. (Like walkway 2, magical prayers 2, super strong eggs 3 for eg)

Satyen Nabar - 7 years, 1 month ago

can any one help me in doing the problem this way

let give us give every coin a number from 1 - 100 to avoid confusion, now we start

frist look - [H........93 HEAD'S .......H]HHHHHHH

look after 1 flip - [(T.........93 TAIL'S.........T)]HHHHHHH ....{fliping the coins that are numbered 1-93}

look after 2 flip - T[(H......92HEAD'S........H)T]HHHHHH ....{fliping the coins numbered 2-94}

look after 3 flip - TH[(T......91TAIL'S.........T)HT]HHHHH ...{fliping the coins numbered 3-95}

look after 4 flip - THT[(H......90 HEAD'S....H)THT]HHHH ...{fliping the coins numbered 4-96}

look after 5 flip - THTH[(T.....89TAIL'S......T)HTHT]HHH ...{fliping the coins numbered 5-97}

look after 6 flip - THTHT[(H....88HEAD'S...H)THTHT]HH ...{fliping the coins numbered 6-98}

look after 7 flip- (TTTT..........99TAIL'S..........TTTTTTT)H ...{fliping the coins numbered 2,4,(6-93),95,97.99}

SO I GOT 99 TAILS AFTER JUST SEVEN FLIPS AND SO I THINK THE ANSWER MUST BE A BIT LESS NUMBER THAN 16 OR IT MAY BE 16 BUT CAN ANYONE HELP ME IN CHOOSING ANY OTHER NUMBERED COIN IN ANY NUMBERED FLIP SO THAT WE CAN GET A NUMBER LESS THAN 16....

Kunal Mandil - 7 years, 1 month ago

Then question asked is should flip 93 coins at a time na???????

vishnu reddy - 7 years, 1 month ago

fantastic answer

Rachit Goel - 7 years, 1 month ago

Andrea Marino
Apr 26, 2014

A less practical approach. We want to choose each coin $a_1, \ldots, a_{100}$ times such that: <ol> <li>1. Each coin is chosen an odd number of times; </li> <li>2. It holds $a_1 + \ldots + a_{100} = 93n$ because we choose 93 coins per time; </li> <li>3. Let $m$ be the maximum of the $a_i$ . It must hold that $m \le n$ , because we choose no more than $n$ groups of coins. </li> <li>4. We want $n$ to be minimum. </li> </ol> We notice that $n$ must be even because 100 odd numbers sum up to $93n$ . This means $n \neq m$ because of parity. The fundamental information is given by: $\displaystyle \frac{93n}{100} = \frac{a_1 + \ldots + a_{100} }{100} \le m < n$ So we must have $n-1 \ge 93n /100$ which implies $n \ge 15$ . Recalling that $n$ is even, the minimum $n$ is 16. This can be realized by choosing $a_1 = \ldots = a_{94} = 15, \ \ a_{95} = \ldots = a_{100} = 13$ . It is clear that the proof would be the same with $2n$ total coins and $2k+1$ coins in a group. The result would be the least even integer greater or equal to $\dfrac{2n}{2(n-k)-1}$

Lutfar Milu
May 8, 2014

$100H => (93T,7H) => (92H,8T) => 6 Step =>(50T,50H) \\ Reversely, (50T,50H) => 8 step => 100T$

Aaaaaa Bbbbbb
Apr 27, 2014

Call n is number of time to flip 93 coins. Call x, y are the number of tail coins and head coins after each flip of the set of 93 coins. It is seen that: $(x+y)=93, \sum_{i=1..n}(x-y)=100$ At first tails coins / head coins is 0/100: to flip the coins: 93/ 7, 8/ 92, 85/ 15, 22/ 78, ... 50/ 50, 43/ 57, 64/ 36, ... 100/ 0 The number of flips is $\boxed{16}$

Anand Shah
Apr 23, 2014

first flip shows 7 tails ...second shows 14...thus 14th shows 98 tails and ..15 flip shows 99 and the hundred is shown by 16.....

Can you explain how does 15 flips show 99 (I'm assuming tails)? Which coins are you flipping?

Can you explain how does 16 flips show 100? which coins are you flipping? If you have 99 tails, and you have to flip 93 coins, how do you get 100 tails?

Calvin Lin Staff - 7 years, 1 month ago

Hmm... In further detail, if your 15th flip shows 99 Heads (or Tails), then the only possibilities I can think of for the 16th flip are either 8 Heads (or Tails) or 6 Heads (or Tails). Hence, getting 100 Tails in the 16th flip from your 15th flip seems impossible. Did I miss anything?

Arga Saragih - 7 years, 1 month ago

Flipping Coins

Image credit: Wikipedia KamTANGO

The answer is 16.

5 solutions

Discussions for this problem are now closed

0 pending reports