We're going to play a game called Puppies and Kittens. It's a variation of Nim. These are the rules:
- There is a pet store with a bunch of puppies and kittens.
- Two players take turns buying puppies and/or kittens.
- During your turn, you may either buy as many puppies as you like, as many kittens as you like, or an equal number of puppies and kittens. You must buy at least one of either.
- Whoever buys the last puppy/kitten wins.
Game 1: 5 puppies, 6 kittens
Game 2: 10 puppies, 7 kittens
Game 3: 25 puppies, 16 kittens
The first player has the winning strategy in each game, so you, the reader, take the first move.
If you play, please do not use the name "Anonymous". If you wish to remain anonymous, select the "Name/url" option and just make up a name. This will make it less confusing for me. Also, don't bother saying how many puppies and kittens you buy, just say how many are left afterwards. Feel free to play as many times as you like until you've figured out how to win.
18 comments:
Sounds good! I'll start with Game 1, since I think I've figured out the winning strategy in that case. I'll buy four of each, so there are 1 puppy and two kittens remaining.
Okay, I buy one kitten, leaving 1 puppy and 1 kitten. It seems you've won Game 1!
There is one other good starting move in Game 1, if anyone cares to find it.
You missed a rule: Each player must choose at least one animal per turn.
Thanks for the correction.
game 1: 3p 4k left
game 2: 8p 7k left
game 3: 15p 16k left
Playing all three games at once! I like your style.
Game 1: 1 puppy, 2 kittens
Game 2: 2 puppies, 1 kitten
Game 3: 15 puppies, 9 kittens
Okay, I have seen now.
Winning positions are:
0-0
1-2
3-5
4-7
6-10
8-13
9-15
11-18
12-20
14-23
16-26
17-28
...
and symmetrics
I worked with a sieve.
Hmm, yes, that works, doesn't it. If you'd like a harder challenge, I could give you a much larger game.
I declare Game 4: 100 puppies, 150 kittens.
80-130
Save positions:
0 0
1 2
3 5
4 7
6 10
8 13
9 15
11 18
12 20
14 23
16 26
17 28
19 31
21 34
22 36
24 39
25 41
27 44
29 47
30 49
32 52
33 54
35 57
37 60
38 62
40 65
42 68
43 70
45 73
46 75
48 78
50 81
51 83
53 86
55 89
56 91
58 94
59 96
61 99
63 102
64 104
66 107
67 109
69 112
71 115
72 117
74 120
76 123
77 125
79 128
80 130
82 133
84 136
85 138
87 141
88 143
90 146
92 149
93 151
95 154
97 157
98 159
100 162
101 164
103 167
105 170
106 172
108 175
110 178
111 180
113 183
114 185
116 188
118 191
119 193
121 196
122 198
I use an excel macro. Do you have a formula?
Yeah, I have a general formula. Has to do with fibonacci numbers.
Game 1 was trivial (presumably as intended). The others took a little longer because I wanted to find a general method that I could use while actually playing the game, given any starting position. I phinally worked it out! ;-)
1: 1 puppy 2 kittens remain
2: 4 p 7 k OR 7 p + 4 k
3: 23 p 14 k
Yep, those are all winning positions. If you've got a general method, you're welcome to describe it.
It's a bit clunky.
If the lower starting number (of p, k) is equal to or greater than Φ * the (positive) diff between p & k (rounded down) then
x = Int (Φ * |p-k|) and y = x + |p-k|, which can always be obtained by subracting the same number of p as k (you don't actually need to know this number).
It's a bit trickier if the starting pos'n is such that the lower starting number is less than
Φ * |p-k| , then you have to take away only either p or k, to reach a winning pos'n.
I hope that's clear, I'm a bit rushed (leaving for work now...)
I think it might be a good idea to reveal my own strategy now, so we might compare.
My strategy involves expressing the numbers in base fibonacci. In base fibonacci, the rightmost digit represents 1, then next represents 2, then 3, 5, 8, 13, 21, etc. For example, 25 would be represented by 1000101.
The idea is that for any winning position, the larger number is equal to the smaller number, except shifted by a single digit, in base fibonacci. Also, the last 1 in the smaller number must be in an odd digit (ie 1, 3, 8, 21, 55, etc.)
From there, it's just a matter of looking for an accessible winning condition (which may be harder than it sounds).
Ooh, that's a nice way of coming at it. Of course, some numbers can be expessed more than one way in base fibonacci; eg 29 could be 1010000 or 1001100 or 1001011. However, because each fib is the sum of the 2 preceding, the last 1 will always be in a pos'n of the same parity. Here, 29 must be a lower number, so the higher will be 10100000 / 10011000 / 10010110 = 47.
I think that's a less clunky explanation than mine but I'm wondering how you would actually go about applying it when playing the game (say with someone at a table). If we were playing a timed game where you could lose by running out of time (we'd each have our own clock), how quickly could you come up with a winning move, say, from 169p and 212k?
With my method I calc the diff as 43 and then multiply that by 1.6 dropping any fractional component (in my head that's 43 + (6 * 4.3)
= 43 + 25 = 69); that's my x (p in this case), and y is simply 69 + 43 = 112. So I would say "69p and 112k" and the game would be mine even if you didn't run out of time!
Well, I'm not going to pretend my algorithm was particularly efficient. You certainly need some paper to use it. However, I was able to find the other solution, 131p and 212k. :)
Excellent. I picked the numbers so the other target position was beyond the list compiled by Eduard but I was hoping you'd go looking for it.
I don't know if there is any more to play with here so I'll just have to wait patiently for your next puzzle post.
Post a Comment