Friday puzzler -- a simple game

Re: Friday puzzler -- a simple game

David Weaver

Wow...nobody touching this one and I just noticed it.

It looks like a problem that a programmer could solve pretty easily with brute force. I'll take it up a little later if nobody else does, could be interesting - never done this type.

Re: Friday puzzler -- a simple game

Larry Barrett

I think the idea is to first determine all the combinations of two digits that are multiples of 5, e.g. 1,4 1,9, ... 2,3 2,8, ...12,13 ...

If you go first, your objective should be to erase numbers so that you maintain an odd number of combinations that are multiples of 5. If you go second, your objective should be to erase numbers so that you maintain an even number of combinations that are multiples of 5.

After a few trials it seems easier to win by going second, but so far it is not obvious to me that it is possible to guarantee a win starting either first or second.

Re: Friday puzzler -- a simple game

Alex Y

I think the idea is to first determine all the combinations of two digits that are multiples of 5, e.g. 1,4 1,9, ... 2,3 2,8, ...12,13 ...

Good start. Think about the numbers modulo 5.

so far it is not obvious to me that it is possible to guarantee a win starting either first or second.

It is, but that is the challenge

Re: Friday puzzler -- a simple game

David Weaver

I think it's easiest to start working backwards on this one and see if you can figure out a strategy as second to win. If you can't, then it must be possible to win as first.

If you're picking second, you pick removal of numbers 2, ...., 24

If you're first, you want to make sure that on pick 24, after pick 24 that is, that there are still at least two numbers that sum (n26 + n27) mod 5 = 0 (as you stated alex).

So, assuming #2 plays optimally, you want there to be (with four numbers left) at least two combinations where the mod 5 condition holds, where the combinations are not dependent on a single number (because #2 will remove that with pick 24 if it exists).

Then, if you can, you want there to be 3 pairs meeting that condition when there are 6 numbers left, 4 when there are 8, etc.

Ideally, you'd want to be able to remove the first number and have 13 pairs left where the (sum) modulo 5 is equal to zero.

...

Re: Friday puzzler -- a simple game

David Weaver

I believe that it is possible to guarantee a win as the second person because I can't figure out a way to guarantee, as the first, that there won't be three old-man-out (nothing to add to them to get the sum to be mod 5) numbers after pairing them off.

I don't have proof yet, but I think as the second person, you will always be able to guarantee three of those will remain.

My preliminary answer is:

David Weaver

I want to go second, and I want to remove something that is sum mod 5 with whatever the first person takes. there should be three oddballs left if I do that the entire game, those would be the three that would be left after I pick #24 as the second picker.

I'm not totally firm on that (thought I don't know why it would be wrong at this point), but that's my answer.

Well, let's try it

Alex Y

Using your algorithm for your responses:

I pick 1, you pick 4, I pick 6, you pick 9, ..., I pick 26, what do you do?

But you are on the right track in how you are thinking about the problem.

Re: Friday puzzler -- a simple game

Larry Barrett

Here's another way to look at this. Start with just three numbers, 1,2,3.

The first player erases the 1, leaving 2,3 which = 0 mod 5. Game over. This is a trivial case since the second player does not have a chance to play.

Now go to 4 numbers, 1,2,3,4.

The first player can erase any number, eliminating one combination. Say he erases 1, which eliminates the 1,4 combination. The second player erases either the 2 or 3 which eliminates the other combination. Second player wins.

Now go to 5 numbers, 1,2,3,4,5.

The first player can erase the 5 which is not part of any combination. The second player can erase any remaining number, eliminating one combination. The first player then erases the other part of the first combination, leaving two numbers that =0 mod 5. First player wins. (If the first player erases anything else, it eliminates one combination. Then the second can eliminate the other combination and the second player would win.)

Now go to 6 numbers, 1,2,3,4,5,6.

Here the combinations that = 0 mod 5 are 1,4 2,3 4,6. The first players best move is to erase 5, which is not part of any combination. The second player can erase 1,2,3, or 6, eliminating one combination, or can erase 4 which eliminates 2 combinations, which seems like his best move. At this point, the only combination that = 0 mod 5 is 2,3; 4 and 5 have been erased and 1,6 are now not part of any combination. No matter what the first player does, the second player can erase either 2 or 3, leaving no combinations. Second player wins.

My observation at this point is that there is at least one non-trivial game (5 numbers) where the first player can win. Also, once the number digits increases beyond 5 there are combinations where one number is part of several combinations (e.g. 1,4 4,6) and erasing that number (4 in this case) eliminates more than one other number. When there are multiple un-paired numbers, the first player can erase one at a time, but the second player can proceed to erase numbers that are part of combinations; it seems the second player can always win in these situations. So I agree with David.

Re: Friday puzzler -- a simple game

Alex Y

it seems the second player can always win in these situations. So I agree with David.

Do you have an algorithm expressing that strategy that we can try out? David's strategy of responding with the "mod five complement" of #1's play didn't provide a play for him after he had eliminated all five 4 mod 5 numbers and I eliminated the sixth 1 mod 5 number.

If you have an algorithm I can play against, let me know and I will play it. Or we can play a game here if we find a convenient time. I'll start by eliminating the 12.

This is close

Alex Y

I can't figure out a way to guarantee, as the first, that there won't be three old-man-out (nothing to add to them to get the sum to be mod 5) numbers after pairing them off.

David, you are very close with this "three odd-man-out" line of reasoning.

Re: Friday puzzler -- a simple game

Larry Barrett

I agree with David's end game strategy, on the 24th pick you want to eliminate the last combination that = 0 mod 5.

A possible strategy when going second is to maintain an even number of combinations, and when possible pick a number that will leave multiple numbers that do not pair with any other number.

I believe there are 69 combinations to start with, and when you erased 12 you eliminated 5 of the 69. So I will erase 25 (eliminating 4 more combinations.)

Re: Friday puzzler -- a simple game

Alex Y

Okay, I picked 12, then you picked 5.

Now I will pick 1.

At this point, what is left is 5 each of 1mod5, 2mod5,3mod5, and 4mod5, and four 0mod5s. From here until the end of the game, each time you pick, I will pick a number that is the negative of your pick, mod 5, assuring that at the end, there will be either 2 0mod5s or a 1 and a 4 mod5 or a 2 and a 3 mod5.

BTW. I come up with 70 combinations at the start of the game:

6x5=30 combinations of a 1mod5 with a 4mod5

6x5=30 combinations of a 2mod5 with a 3mod5

C(5,2)=10 combinations of two 0mod5s

Re: This is close

David Weaver

I'm taking the lazy man out strategy for the time being ( and hoping someone else solves it ) because I won't have time to fiddle with it for a bit.

(if I was going to continue on with it for now, I'd try to find the trouble numbers that don't have enough (x+y) mod 5 results in zero partners and plan to knock them out first. I just can't look right now (I do think I like to pick second and pick the second number to make the sum's second digit a zero better, but I am having trouble playing the game against myself because I'm too single-minded to play back and forth with two different goals).

I obviously want to get to the point where I can force three "oddballs" at the end of the game.

Solution

Alex Y

David got close when he identified the issue of having three extra numbers after pairing off numbers into pairs that added to multiple of five. There is one extra 1 mod 5, one extra 2 mod 5, and one extra multiple of 5.

But it is the first player who can always win this game with the correct strategy. Start by selecting one of the 1 mod 5 numbers. Then, when the second player plays either a multiple of 5 or a 2 mod 5, the first player plays the other "extra", creating a balanced situation, as occurred in the game Larry and I played. After reaching this balanced situation, as well as before the second player plays one of the "extras", the first player's strategy is to play a number that adds with the second player's number to get a multiple of 5.

It was not immediately obvious to me that the second player will eventually have to play one of the extras, giving the first player the opening needed, but a game illustrating #2's holding out as long as possible will help:

1 3

2 4

6 8

7 9

11 13

12 14

16 18

17 19

21 23

22 24

26 ??

At this point, all that is left is 5,10,15,20,25,and 27, so #2 will have to pick either a multiple of 5 or the remaining (extra) 2mod5, and I will pick the other, leaving four multiples of five after my next turn.

Thanks for playing. Now go out and win a bar bet with this!