bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

I think there might be a typo; the 'R' in the third row, sixth column, should be a '12', I think.

The method behind the code is as follows:

Mattcrampy
Level: Smitemaster

Rank Points: 2388
Registered: 05-29-2003
IP: Logged

Yeah, that's it.

At least it took longer than an hour.

You're up!

Matt

____________________________
What do you call an elephant at the North Pole?

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Mattcrampy wrote:
At least it took longer than an hour.

The first thing I did when I saw the solution was to look at the time difference, to see if it took under an hour to solve. That would have been the funniest thing I've seen in a long time.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Alice and Bob play the following game. There is a pile of n stones, and Alice and Bob alternate turns, with Alice going first. On any player's turn, they split into two piles every pile that contains at least two stones. (So if there were piles of sizes 1, 1, 4, 10, a possible legal move would be to leave piles of sizes 1, 1, 1, 3, 5, 5.) The person who cannot move (because all the piles contain exactly one stone) loses. Sometimes Alice has a winning strategy (for example, if n=2), and sometimes Bob does (e.g., if n=3). For which n does each player win, and what is his/her strategy?

Avon
Level: Delver
Rank Points: 47
Registered: 12-06-2003
IP: Logged

Alice wins if n is even and Bob wins if n is odd.

Suppose n=2k. On her first turn, Alice can move to k,k which we shall write as k|k. From now on, whenever Bob makes a move on one side of the |, Alice can copy this move on the other side, so the piles on either side of the | will always be the same and Alice will always be able to move. Eventually Alice will move to 1,1,...,1|1,1,...1 and Bob will be unable to move.

Supose n is odd. If n=1 then clearly Bob wins. Suppose n>1 and Bob wins for all odd piles <n. On her first move, Alice must split the pile into an odd and an even pile, say m,2k where m is odd and m<n. Bob should move to m,k,k. Now Bob imagines this as two separate games, m and k,k. m is odd and <n so Bob has a winning strategy in m. Also Bob can use Alice's strategy from the previous paragraph to win k,k. Whichever game Alice moves in, Bob should make the reply from his winning strategy in that game. Thus Bob can always move. Eventually Alice will "lose" both games, and thus lose the game.

____________________________
"Les hommes ne sont jamais plus ingénieux que dans l'invention des jeux." -- Gottfried Wilhelm Leibniz

eytanz
Level: Smitemaster

Rank Points: 2708
Registered: 02-05-2003
IP: Logged

That's what I thought at first - but note that Alice will win with 5 stones:

A - splits the five stone pile to a 2 stone pile and a 3 stone pile.
B - splits the two stone pile to two 1 stone piles, and the three stone pile to one 2 stone, and one 1 stone pile. (note that he has no choice)
A - splites the remaining two stone pile to two singles.

Bob now has no moves, and he loses.

-----

Your mistake, and my initial mistake, was taking the rule to allow for a player to split only some of the piles. Since the rules force each player to split ALL the greater than 1 piles, the game is more complex.

____________________________
I got my avatar back! Yay!

Avon
Level: Delver
Rank Points: 47
Registered: 12-06-2003
IP: Logged

Sorry, I misread the puzzle. Oh well, back to the drawing board.

____________________________
"Les hommes ne sont jamais plus ingénieux que dans l'invention des jeux." -- Gottfried Wilhelm Leibniz

eytanz
Level: Smitemaster

Rank Points: 2708
Registered: 02-05-2003
IP: Logged

Ok, here's my solution:

Bill wins for n = 1, or for all n such that m is also a winning number from bob and n = 2m+1.

Note first that it's only the largest pile that you have that will determine if you win or lose, assuming both players play optimally. Proof: Imagine that there was some pile size x that you would always lose if you have it, no matter what other piles you have. But if you have a pile larger than x, you could give x to your opponent, and he would therefore lose - a contradiction. Similarly, for winning piles. The only way a pile x could determine your victory or loss is if you have no larger piles.

Now, it's easy to see that any player loses if his or her largest pile is 1, wins if it is 2, and loses if it is 3.

Now, for any pile size that Alice starts with, she can ensure that Bob loses if she manages to ensure that his largest pile size is 3. If n<=6, she can do this easily - but if she has 7 stones, she has to give him a pile of size 4-6, which means he wins. Therefore, whoever has 7 loses. So for piles for size 8-14, Alice can win by giving Bill a 7-stone pile. But for 15, she must give him a pile of size 8-14; and so forth - for each losing pile size, Alice can ensure that Bill has it if she has up to twice the amount of stones in that pile; but if she has exactly twice that number plus one, she loses.

I hope that was clear.

____________________________
I got my avatar back! Yay!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

eytanz wrote:
Bill wins for n = 1, or for all n such that m is also a winning number from bob and n = 2m+1.

This translates to: Bob wins if n+1 is a power of two, otherwise Alice wins.

The argument you made wasn't all that clear (partly because Bob's name kept changing), but it has the right gist, so I'll let you take it.

The strategy is to split any x into y,z, where y+1 is the largest power of two at most x, unless x+1 is a power of two, in which case it doesn't matter how the pile is split. The reason that only the big piles matter is that the smaller piles will become single piles in fewer moves. If n+1 is a power of two, then she must give Bob a position where the largest pile isn't one less than a power of two (after splitting 2^k-1, one pile must contain at least 2^(k-1)). If n+1 isn't a power of two, then if Alice follows this strategy, you can check that Bob has to return to Alice a position where the largest pile isn't one less than a power of two. The largest pile gets smaller every turn by about a factor of two. Since a player loses if the largest pile is one (one less than a power of two) and wins if the largest pile is two, this basically gives us what we want. (Hmm, that wasn't too clear either...)

Anyway, go ahead eytanz.

eytanz
Level: Smitemaster

Rank Points: 2708
Registered: 02-05-2003
IP: Logged

By the way, I know I'm supposed to post a puzzle next, I'm just looking for a good one and am rather busy today so it will probably have to wait until tomorrow evening. Sorry.

____________________________
I got my avatar back! Yay!

eytanz
Level: Smitemaster

Rank Points: 2708
Registered: 02-05-2003
IP: Logged

Ok, here's my puzzle (Originally posted by Carl G. to rec.puzzles) -

Using only five straight cuts, dissect a circle into pieces that can be reassembled to form two complete semicircles. Additionally, none of the five straight cuts are allowed to pass through the circle's center point.

(note - this will be a bit difficult to draw in ASCII (though possible), so I'll accept a description of the solution provided that it's clear; but it may be best to draw a simple drawing in paint or something and attach it)

[Edited by eytanz on 02-11-2004 at 04:18 PM GMT]

____________________________
I got my avatar back! Yay!

The_Red_Hawk
Level: Smitemaster
Rank Points: 783
Registered: 09-02-2003
IP: Logged

Hey - did you notice that's our 700th post on this thread?

Well, it sounds interesting, and I'll work on it when I have time.

____________________________
Slashing, whirling, diving, twirling,
Snapping, turning, rising, swirling,
Screeching, flipping, gliding, sliding,
The red hawk's dance of death.

.....the king of the skies.....

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

File: circle.JPG (7.9 KB)
Downloaded 142 times.
License: Other
From: Unspecified

How about this (attached)? The reconstruction is obvious.

[Edited by bibelot on 02-11-2004 at 11:30 PM GMT]

eytanz
Level: Smitemaster

Rank Points: 2708
Registered: 02-05-2003
IP: Logged

Yup - that's the solution I was after.

Your turn again

____________________________
I got my avatar back! Yay!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Well then, how about another one with a dissection?

Does there exist a nonright triangle that can be dissected into five triangles, each of which is similar to the original?

TripleM
Level: Smitemaster
Rank Points: 1379
Registered: 02-05-2003
IP: Logged

File: triangle.JPG (7.2 KB)
Downloaded 93 times.
License: Other
From: Unspecified

OK, this is going to be very hard to explain..



[Edited by TripleM on 02-11-2004 at 10:34 PM GMT]

[Edited by TripleM on 02-11-2004 at 10:40 PM GMT: sorry about this editing, trying to make picture smaller.]

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Didn't Oneiromancer put a condition on these puzzles a while ago that straight math puzzles like proofs were disallowed?

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

DiMono wrote:
Didn't Oneiromancer put a condition on these puzzles a while ago that straight math puzzles like proofs were disallowed?

Yes. But luckily TripleM has made a mistake...

Oneiromancer
Level: Legendary Smitemaster

Rank Points: 2936
Registered: 03-29-2003
IP: Logged

I'd say that a puzzle where it is not required to solve it mathematically is okay. This puzzle could be solved via proofs or via imagination, it seems to me.

Game on,

____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

Alright, I'm going to take a guess, and then propose that we put an end to this puzzle since nobody's said anything in a week.

No. The standard way to divide a triangle in to smaller versions of itself is to draw a 180 degree rotation of it such that the corners of the rotation touch the sides of the original triangle. This gives four smaller versions. In order to divide the triangle in to five smaller versions, you would need to find a line you could draw from a vertex of one of the smaller triangles to its opposite side. The only way for such a line to exist is in a right angled triangle, therefore there is no non-right angled triangle that can be evenly divided in to five smaller versions of itself.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Oh, hmm. Maybe I should rephrase the question.

Find a (in fact, the) nonright triangle that can be dissected into five smaller triangles, each similar to the original.

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

File: triangle.png (12.1 KB)
Downloaded 137 times.
License: Other
From: Unspecified

I didn't even try until you mentioned there definitely is one. It's not that hard - picture attached.

Basically, it's a triangle with angles 120, 30, and 30 degrees.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

bibelot
Level: Smiter
Rank Points: 322
Registered: 07-11-2003
IP: Logged

Indeed, that is the one. It really is the only one (up to similarity), but the proof of that is long and messy and not at all interesting. You can almost convince yourself on paper that a triangle with angles 180/7, 360/7, 720/7 can also work (with four triangles sharing an interior vertex), but it doesn't.

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

I forgot I'd have to post one, so I don't have a good one prepared. Here's an easy one:

Two trains travel toward each other on the same track, beginning 250 miles apart. One train travels at 40 miles per hour; the other travels at 60 miles an hour. A bird starts flight at the same location as the faster train, flying at a speed of 90 miles per hour. When it reaches the slower train, it instantaneously turns around, flying the other direction at the same speed. When it reaches the faster train again, it turns around -- and so on. When the trains collide, how far will the bird have flown?

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Nillo
Level: Smitemaster

Rank Points: 548
Registered: 01-04-2004
IP: Logged

Is'nt there a rule against purely mathematical puzzles?

[Edited by Nillo on 02-18-2004 at 10:44 AM GMT]

____________________________
“Folks say that if you listen real close at the height of the full moon, when the wind is blowin' off Nantucket Sound from the nor' east and the dogs are howlin' for no earthly reason, you can hear the awful screams of the crew of the 'Ellie May,' a sturdy whaler Captained by John McTavish; for it was on just such a night when the rum was flowin' and, Davey Jones be damned, big John brought his men on deck for the first of several screaming contests.”

DiMono
Level: Smitemaster

Rank Points: 1181
Registered: 09-13-2003
IP: Logged

I'd say the phrase When the trains collide exempts this one from that rule. I mean, seriously, people die in this puzzle!

That said, the trains never collide. When they are half way to each other, they then need to get half way of what's left, then half of what's left, and so on. Similarly, before the trains can get half way to each other, they need to get half of that, and so on. Since the trains never start moving, the bird flies nowhere.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

Nillo wrote:
Is'nt there a rule against purely mathematical puzzles?

I'll defend this one since the only math needed is arithmetic. The puzzle part is figuring out the easy way to calculate the answer. It's really quite simple.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

I gotta say...that's one damn fast bird.

____________________________

RoboBob3000
Level: Smitemaster

Rank Points: 1982
Registered: 10-23-2003
IP: Logged

DiMono wrote:
I'd say the phrase When the trains collide exempts this one from that rule. I mean, seriously, people die in this puzzle!

That said, the trains never collide. When they are half way to each other, they then need to get half way of what's left, then half of what's left, and so on. Similarly, before the trains can get half way to each other, they need to get half of that, and so on. Since the trains never start moving, the bird flies nowhere.

That's like the tortise and the hare paradox, which says something along the lines that a tortise, when given a head start in a race, will always stay ahead of the hare because the hare always has to cover half the distance. Since we know that isn't what's going to happen (the hare will overcome the tortise) we need to take the limit of the sums to find the point where they'd meet.

I just don't feel like working out the numbers right now.

____________________________
http://beepsandbloops.wordpress.com/

Schik
Level: Legendary Smitemaster

Rank Points: 5453
Registered: 02-04-2003
IP: Logged

RoboBob3000 wrote:
Since we know that isn't what's going to happen (the hare will overcome the tortise) we need to take the limit of the sums to find the point where they'd meet.

I just don't feel like working out the numbers right now.

Anyone with decent arithmetic skills should be able to do this in a few seconds in their head.


____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi