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