Bsrgvty

Sum of all digits in a string

Where does the upgrade to macOS Catalina move root "/" directory files?

Did Terry Pratchett ever explain the inspiration behind the Luggage?

Rent a car for a day and leave it in another city in Italy

Is it poor workplace etiquette to display signs of relative "wealth" at work when others are struggling financially?

Why is my paper "under review" if it contains no results?

Do half-elves or half-orcs count as humans for the ranger's Favored Enemy class feature?

How can I communicate feelings to players without impacting their agency?

Conveying the idea of "tricky"

What is Ferb's name short for?

Enlightend beings don't make more good or neutral karma?

Is it unusual that English uses possessive for past tense?

How to check if a trigger fires on INSERT, UPDATE or DELETE statements?

How to increment the value of a (decimal) variable (with leading zero) by +1?

Could an American state survive nuclear war?

First author doesn't want a co-author to read the whole paper

What is the "5th Edition Adventures" book series?

How much does freezing grapes longer sweeten them more?

Does code obfuscation give any measurable security benefit?

What is gerrymandering called if it's not the result of redrawing districts?

Is the tap water in France safe to drink?

How does a ball bearing door hinge work?

Is there any research on the development of attacks against artificial intelligence systems?

Why do baby boomers have to sell 5% of their retirement accounts by the end of the year?

How many moves will it take to turn $100$ coins to the heads side up? [closed]

Flipping coins - Counting in two waysHexaglide Game - Combinatorics ProblemHow many ways to take presents to schoolSuppose a coin in tossed $12$ times and there are $3$ heads and $9$ tails. How many sequences…Probability of reaching net 4 heads when tossing coin 8 timesCombinatorics question involving assigning students from high schools to collegesA family of 8 people seated in a rectangular with two opposing headsOptimizing a winning strategy for a quick tabletop gameHow many different patterns of heads and tails can we obtain after a number of moves?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;

.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;

0

$begingroup$

You have 100 coins on the table, all tails up. One move is turning any 93 coins over.How many moves will it take to get all the coins on heads?

It's question that I found in mathematical "olimpics" for high school and I found it interesting.

In the brackets there was a hint that I should use method of counting two ways(or double counting).

combinatorics combinatorial-game-theory

share|cite|improve this question

edited May 20 at 7:52

KarmaL

asked May 19 at 15:43

KarmaLKarmaL

3477 bronze badges

$endgroup$

closed as off-topic by TheSimpliFire, Ernie060, Xander Henderson, max_zorn, YuiTo Cheng May 20 at 6:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – TheSimpliFire, Ernie060, Xander Henderson, max_zorn, YuiTo Cheng

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  This question could be a good deal better if you explained why the question was of interest to you and any efforts you have already made to try to solve it.
  $endgroup$
  – Mark Bennet
  May 19 at 16:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Checking that the words in the question are actually the words you meant would help too. ("Headset"? "More" instead of "move"?) It shouldn't require someone else to fix those things for you. (And what if they "fix" them to something that wasn't what you actually meant?)
  $endgroup$
  – David K
  May 19 at 16:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It's question that I found in mathematical "olimpics" for high school and I was just interested how to solve it because although I already study university I didn't have any idea.
  $endgroup$
  – KarmaL
  May 20 at 7:44
  

  
  
  
  

add a comment
 | 

0

$begingroup$

You have 100 coins on the table, all tails up. One move is turning any 93 coins over.How many moves will it take to get all the coins on heads?

It's question that I found in mathematical "olimpics" for high school and I found it interesting.

In the brackets there was a hint that I should use method of counting two ways(or double counting).

combinatorics combinatorial-game-theory

share|cite|improve this question

edited May 20 at 7:52

KarmaL

asked May 19 at 15:43

KarmaLKarmaL

3477 bronze badges

$endgroup$

closed as off-topic by TheSimpliFire, Ernie060, Xander Henderson, max_zorn, YuiTo Cheng May 20 at 6:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – TheSimpliFire, Ernie060, Xander Henderson, max_zorn, YuiTo Cheng

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  This question could be a good deal better if you explained why the question was of interest to you and any efforts you have already made to try to solve it.
  $endgroup$
  – Mark Bennet
  May 19 at 16:01
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Checking that the words in the question are actually the words you meant would help too. ("Headset"? "More" instead of "move"?) It shouldn't require someone else to fix those things for you. (And what if they "fix" them to something that wasn't what you actually meant?)
  $endgroup$
  – David K
  May 19 at 16:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It's question that I found in mathematical "olimpics" for high school and I was just interested how to solve it because although I already study university I didn't have any idea.
  $endgroup$
  – KarmaL
  May 20 at 7:44
  

  
  
  
  

add a comment
 | 

$begingroup$

You have 100 coins on the table, all tails up. One move is turning any 93 coins over.How many moves will it take to get all the coins on heads?

It's question that I found in mathematical "olimpics" for high school and I found it interesting.

In the brackets there was a hint that I should use method of counting two ways(or double counting).

combinatorics combinatorial-game-theory

share|cite|improve this question

edited May 20 at 7:52

KarmaL

asked May 19 at 15:43

KarmaLKarmaL

3477 bronze badges

$endgroup$

share|cite|improve this question

edited May 20 at 7:52

KarmaL

asked May 19 at 15:43

KarmaLKarmaL

3477 bronze badges

share|cite|improve this question

edited May 20 at 7:52

KarmaL

asked May 19 at 15:43

KarmaLKarmaL

3477 bronze badges

asked May 19 at 15:43

KarmaLKarmaL

3477 bronze badges

asked May 19 at 15:43

KarmaLKarmaL

3477 bronze badges

2 Answers
2

active

oldest

votes

6

$begingroup$

As each move changes the parity of the number of heads, it is clear that we need an even number of moves.
Consider the effect of two consecutive moves: The two sets of $93$ turned coins must largely overlap: They must have at least $86$ coins in common. Hence their combined effect is to turn an even number $le 14$ of coins.
Hence $14$ moves can at most turn $98$ coins, i.e., we need at least $16$ moves.

On the other hand, we can turn any even number $2mle14$ of coins with two moves: Partition these in two sets of $m$ coins, pick $93-m$ coins from the rest (possible because $2m+93-mle 100$) and turn these and the first/suecond subset in the first/second move. It follows that the lower bound of $16$ moves is achievable.

share|cite|improve this answer

answered May 19 at 16:04

Hagen von EitzenHagen von Eitzen

299k2525 gold badges289289 silver badges532532 bronze badges

$endgroup$

add a comment
 | 

3

$begingroup$

The answer is: 16.

Consider any solution. Each turn we are flipping 93 coins, and overall we are flipping each coin an odd number of times. This there are 100 coins, the total number of coin flips is even. Since 93 is odd, it follows that the number of moves must be even.

Since the number of moves is even, instead of flipping 93 coins each time, we can flip the the remaining 7 coins each time - the end result will be the same, since there is an even number of moves.

In 14 moves we can touch at most 98 coins, so since the number of moves is even, we need at least 16 moves. In the first 12 moves, we can flip the first 84 coins. We flip the other 16 coins in 4 moves as follows:

$$
1111111000000000 \
1111110100000000 \
1111110010000000 \
0000000001111111
$$

share|cite|improve this answer

answered May 19 at 16:08

Yuval FilmusYuval Filmus

50.4k44 gold badges7676 silver badges149149 bronze badges

$endgroup$

add a comment
 | 

6

$begingroup$

As each move changes the parity of the number of heads, it is clear that we need an even number of moves.
Consider the effect of two consecutive moves: The two sets of $93$ turned coins must largely overlap: They must have at least $86$ coins in common. Hence their combined effect is to turn an even number $le 14$ of coins.
Hence $14$ moves can at most turn $98$ coins, i.e., we need at least $16$ moves.

On the other hand, we can turn any even number $2mle14$ of coins with two moves: Partition these in two sets of $m$ coins, pick $93-m$ coins from the rest (possible because $2m+93-mle 100$) and turn these and the first/suecond subset in the first/second move. It follows that the lower bound of $16$ moves is achievable.

share|cite|improve this answer

answered May 19 at 16:04

Hagen von EitzenHagen von Eitzen

299k2525 gold badges289289 silver badges532532 bronze badges

$endgroup$

add a comment
 | 

6

$begingroup$

As each move changes the parity of the number of heads, it is clear that we need an even number of moves.
Consider the effect of two consecutive moves: The two sets of $93$ turned coins must largely overlap: They must have at least $86$ coins in common. Hence their combined effect is to turn an even number $le 14$ of coins.
Hence $14$ moves can at most turn $98$ coins, i.e., we need at least $16$ moves.

On the other hand, we can turn any even number $2mle14$ of coins with two moves: Partition these in two sets of $m$ coins, pick $93-m$ coins from the rest (possible because $2m+93-mle 100$) and turn these and the first/suecond subset in the first/second move. It follows that the lower bound of $16$ moves is achievable.

share|cite|improve this answer

answered May 19 at 16:04

Hagen von EitzenHagen von Eitzen

299k2525 gold badges289289 silver badges532532 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

As each move changes the parity of the number of heads, it is clear that we need an even number of moves.
Consider the effect of two consecutive moves: The two sets of $93$ turned coins must largely overlap: They must have at least $86$ coins in common. Hence their combined effect is to turn an even number $le 14$ of coins.
Hence $14$ moves can at most turn $98$ coins, i.e., we need at least $16$ moves.

On the other hand, we can turn any even number $2mle14$ of coins with two moves: Partition these in two sets of $m$ coins, pick $93-m$ coins from the rest (possible because $2m+93-mle 100$) and turn these and the first/suecond subset in the first/second move. It follows that the lower bound of $16$ moves is achievable.

share|cite|improve this answer

answered May 19 at 16:04

Hagen von EitzenHagen von Eitzen

299k2525 gold badges289289 silver badges532532 bronze badges

$endgroup$

share|cite|improve this answer

answered May 19 at 16:04

Hagen von EitzenHagen von Eitzen

299k2525 gold badges289289 silver badges532532 bronze badges

answered May 19 at 16:04

Hagen von EitzenHagen von Eitzen

299k2525 gold badges289289 silver badges532532 bronze badges

answered May 19 at 16:04

Hagen von EitzenHagen von Eitzen

299k2525 gold badges289289 silver badges532532 bronze badges

3

$begingroup$

The answer is: 16.

Consider any solution. Each turn we are flipping 93 coins, and overall we are flipping each coin an odd number of times. This there are 100 coins, the total number of coin flips is even. Since 93 is odd, it follows that the number of moves must be even.

Since the number of moves is even, instead of flipping 93 coins each time, we can flip the the remaining 7 coins each time - the end result will be the same, since there is an even number of moves.

In 14 moves we can touch at most 98 coins, so since the number of moves is even, we need at least 16 moves. In the first 12 moves, we can flip the first 84 coins. We flip the other 16 coins in 4 moves as follows:

$$
1111111000000000 \
1111110100000000 \
1111110010000000 \
0000000001111111
$$

share|cite|improve this answer

answered May 19 at 16:08

Yuval FilmusYuval Filmus

50.4k44 gold badges7676 silver badges149149 bronze badges

$endgroup$

add a comment
 | 

3

$begingroup$

The answer is: 16.

Consider any solution. Each turn we are flipping 93 coins, and overall we are flipping each coin an odd number of times. This there are 100 coins, the total number of coin flips is even. Since 93 is odd, it follows that the number of moves must be even.

Since the number of moves is even, instead of flipping 93 coins each time, we can flip the the remaining 7 coins each time - the end result will be the same, since there is an even number of moves.

In 14 moves we can touch at most 98 coins, so since the number of moves is even, we need at least 16 moves. In the first 12 moves, we can flip the first 84 coins. We flip the other 16 coins in 4 moves as follows:

$$
1111111000000000 \
1111110100000000 \
1111110010000000 \
0000000001111111
$$

share|cite|improve this answer

answered May 19 at 16:08

Yuval FilmusYuval Filmus

50.4k44 gold badges7676 silver badges149149 bronze badges

$endgroup$

add a comment
 | 

$begingroup$

The answer is: 16.

Consider any solution. Each turn we are flipping 93 coins, and overall we are flipping each coin an odd number of times. This there are 100 coins, the total number of coin flips is even. Since 93 is odd, it follows that the number of moves must be even.

Since the number of moves is even, instead of flipping 93 coins each time, we can flip the the remaining 7 coins each time - the end result will be the same, since there is an even number of moves.

In 14 moves we can touch at most 98 coins, so since the number of moves is even, we need at least 16 moves. In the first 12 moves, we can flip the first 84 coins. We flip the other 16 coins in 4 moves as follows:

$$
1111111000000000 \
1111110100000000 \
1111110010000000 \
0000000001111111
$$

share|cite|improve this answer

answered May 19 at 16:08

Yuval FilmusYuval Filmus

50.4k44 gold badges7676 silver badges149149 bronze badges

$endgroup$

share|cite|improve this answer

answered May 19 at 16:08

Yuval FilmusYuval Filmus

50.4k44 gold badges7676 silver badges149149 bronze badges

answered May 19 at 16:08

Yuval FilmusYuval Filmus

50.4k44 gold badges7676 silver badges149149 bronze badges

answered May 19 at 16:08

Yuval FilmusYuval Filmus

50.4k44 gold badges7676 silver badges149149 bronze badges