Friday Puzzler -- 40 coins

What's the goal?

Henry Higginbotham

Take the last coin? Make your opponent take the last coin? Something else?

The Goal

Alex Y

Thanks, Henry, for pointing out that I had admitted a key part of the puzzle! The goal is to end up with the most money. Or, if you had to buy into the game for 1/2 of the value of all the coins, make sure you don't lose money.

Hint

Alex Y

I stated this problem with some specifics because I knew exactly how, and how quickly, Larry would solve it if I stated the general problem of which this is an example.

Figure the answer to similar problems to discover the general solution.

Re: Hint

Larry Barrett

It seems that in theory you could examine all possible options, but with 40 coins it would become rather tedious.

I have been thinking about this problem, but starting with just two coins, then four coins, etc to see if some rule of thumb pops out that can be extrapolated.

With just two coins, the obvious answer is to go first and select the coin with highest value. For example, if the coins are 5 25, go first and select the 25.

With four coins the problem is more interesting. If you go first you now need to look at what your opponent will do. For example, suppoose the four coins are

5 25 10 1. If you select the 5, your opponent will see 25 10 1 and will select the 25. So your first move should be to select the 1, leaving your opponent with

5 25 10. No matter which coin he selects, you can then select the 25 and win.

I have not thought this through with different combinations, or with 6 coins, so don't have a good rule of thumb yet.

Re: Hint

Kent B

I'll take a shot....

The 40 is misdirection. Total number doesn't matter. Also, it doesn't say there is an even distribution of 25, 10, 5, and 1 [ie - doesn't say 8 of each - just "a mixture"].

I think I can win if we use ripe apples, green apples, and U of Mich hats. The ripe apples have the most value because they can be eaten today. The green apples are next because they will ripen. The U of Mich hats have no value because stupid helmets.

I'll go first. My strategy is to get half plus one of the goodies, which are quarters in this game. In the process of picking, I will accumulate enough non-quarters to win out.

I will pick whichever coin leaves quarter[s] next-plus-one in line - thereby forcing my opponent to uncover a quarter. That could mean giving him a quarter to pick up if it has another quarter beside it that I can grab. Trading rooks. That's fine. I don't have to get all the quarters, just more than him.

If there are no quarters within reach of play, then I will set up for a dime.

Re: Hint

Alex Y

The 40 is misdirection.

as I acknowledged.

Total number doesn't matter.

not true.

Also, it doesn't say there is an even distribution of 25, 10, 5, and 1 [ie - doesn't say 8 of each - just "a mixture"].

Correct

I think I can win if we use ripe apples, green apples, and U of Mich hats. The ripe apples have the most value because they can be eaten today. The green apples are next because they will ripen. The U of Mich hats have no value because stupid helmets.

Hey, them's fighting words. And you realize, don't you, that there is a school somewhere southeast of Ann Arbor that wants to register one word you used eight times as a trademark! ;-)

I'll go first. My strategy is to get half plus one of the goodies, which are quarters in this game. In the process of picking, I will accumulate enough non-quarters to win out.

I will pick whichever coin leaves quarter[s] next-plus-one in line - thereby forcing my opponent to uncover a quarter. That could mean giving him a quarter to pick up if it has another quarter beside it that I can grab. Trading rooks. That's fine. I don't have to get all the quarters, just more than him.

You said string length doesn't matter. How will your strategy work for penny-quarter-penny?

How about this string?

ppqdpdpdpdpd

The way I read the above, you will pick the penny on the left end, to make the quarter "next-plus-one in line". I will pick the dime at the right end of the string. you will pick the penny at the right end, to keep the quarter one away from the end of the line. This will continue until we get to pqd, at which point I will have to pick the dime to give you the quarter before I pick up the last penny. Result: you have 1 quarter and 5 pennies = $0.30, and I have 5 dimes and one penny - $0.51

The general case

Alex Y

As I originally saw this puzzle:

There are is even number of coins lined up in a row. Players take turns removing one coin from either end of the row until all the coins are taken. Do you want to go first or second, and what is your strategy to maximize the money you collect?

Note that this doesn't even mention the varying values of coins -- you just have to recognize that there is no game worth paying if they are all the same value.

Re: The general case

Kent B

I'm not really getting out of the ditch here yet.

Do I get a look at the lineup before I pick first or second?

Also:

> "...a school somewhere southeast of Ann Arbor..." Colloquially - "Go south until you smell it, then go east until you step in it."

> I'm happy to add a 4th item to my list. A buckeye goes below a green apple, but not below a U of Mich hat. Nothing goes below that because stupid helmet

> Pre-season trash-talk training

Re: The general case

Alex Y

Do I get a look at the lineup before I pick first or second?

Yes, but you don't need to before deciding whether to go first or second. However, you do need to see the whole lineup before making your first coin pick.

Clarification

Alex Y

What I posted is the way I have seen this puzzle stated. However most of the answers I have seen do NOT deliver the maximum, but rather assure you of not losing (and since there is very little chance for a tie with many coins, this will usually end up with you ahead.

That is the better goal for this puzzle -- don't lose.

The strategy for not losing may be able to be improved to increase winnings, but I suspect that is not the maximum, which is a computer algorithm problem that is well over my head.

Re: Clarification

Larry Barrett

One thing you can do before selecting a coin is to determine how much you need to avoid losing. Add the value of all coins, say N. You need N/2 + 1.

I still don’t have a good method to proceed, and not sure if it is useful to know what you need.

Hint 2

Alex Y

With the goal limited to winning (or not losing), I can tell you a priori exactly how much money I will have at the end of the game.

Last Hint -- 40 coins

Alex Y

Number the coins.

Solution -- 40 coins *LINK*

Alex Y

Looks like no activity on this one, so here is the answer:

To avoid losing (and almost certainly winning, since the chance of a tie is very small as long as there are a sizable number of coins, of multiple denomination):

1) Number the coins left to right (or vice-versa, with appropriate changes)

2) Determine the sums of the even numbered coins and the odd numbered coins

3) Choose all the even or odd coins, whichever is larger.

And you don't even need to keep up with which coins were even and which were odd. Let's say that the total of the even numbered coins was larger

Pick the far right coin (number 40)

Your opponent is left with a choice of two odd-numbered coins.

Whichever end your opponent chooses, he will "uncover" an even numbered coin. Continue this way, always picking from the same end of the row of coins that your opponent chose from, and you will end up with all the even numbered coins, and thus win.

Maximizing your winnings is a computer algorithms problem in something referred to as dynamic programming. Here's a link to begin to understand that if you so desire:


https://algorithms.tutorialhorizon.com/dynamic-pro