Abbyzzmal
Level: Smiter
Rank Points: 348
Registered: 07-03-2004
IP: Logged

While there might be no overlap, I think you end up having duplicates, at least in the even numbered cases. Also, each year/genre will accompany only n/2 genres/years.

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

Well, since you aren't requiring a proof, I may as well just go ahead and say that the answer is ..

Mattcrampy
Level: Smitemaster

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

You got it, buddy.

Well, you got the square root of it, but I get what you mean.

So, what happened to that other puzzle?

Matt

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

Watcher
Level: Smitemaster

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

There wasn't another puzzle yet, because I was waiting for discussion on this one to finish. But here it is:

A number of knights are placed on an ordinary chessboard. None of them are able to attack any of the others with a single move. What's the maximum possible number of knights on the board?

____________________________
Today the refrigerator, tomorrow the world!

jdyer
Level: Smiter
Rank Points: 331
Registered: 03-19-2003
IP: Logged

Watcher wrote:
There wasn't another puzzle yet, because I was waiting for discussion on this one to finish. But here it is:

A number of knights are placed on an ordinary chessboard. None of them are able to attack any of the others with a single move. What's the maximum possible number of knights on the board?

My gut reaction says...

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

Yeah, thats right - if you want a quick proof:


Unless, of course, when Watcher said "None of them are able to attack any of the others with a single move", that means that you can't move a knight into a position where it will attack another one..

KevG
Level: Smiter

Rank Points: 333
Registered: 08-16-2004
IP: Logged

Assuming the second interpretation, I can get eight fairly easily. Easily enough that I won't even provide a spoiler yet. I'm not prepared to say that eight is the max, but more than that seems problematic.

Watcher
Level: Smitemaster

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

Jdyer has interpreted the riddle correctly, and his answer is correct. 32 is indeed the maximum.

Your turn, jdyer.

____________________________
Today the refrigerator, tomorrow the world!

Maurog
Level: Smitemaster

Rank Points: 1501
Registered: 09-16-2004
IP: Logged

KevG wrote:
Assuming the second interpretation, I can get eight fairly easily. Easily enough that I won't even provide a spoiler yet. I'm not prepared to say that eight is the max, but more than that seems problematic.

I thought about the second interpretation, and I can get twelve fairly easily

OO....OO
.O....O.
........
........
........
........
.O....O.
OO....OO

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!

jdyer
Level: Smiter
Rank Points: 331
Registered: 03-19-2003
IP: Logged

This is a two parter I invented a while back. I'll consider #1 the warm up and #2 the real puzzle.

You have a row of 8 coins. You can flip coins over with certain moves, by either:
A.) Flipping over three consecutive coins OR
B.) Flipping over two consecutive coins where one is heads and the other tails.

1.) With the first four coins starting on heads and the second four starting on tails, switch the layout to all heads in four moves.

2.) With all coins starting on heads, switch to all tails in five moves.

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

Part A:


Part B:

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

Right, lets see..
We have a Rubik's cube. Lets call a 'move' turning the front face clockwise by 90 degrees followed by turning the right face clockwise by 90 degrees. How many times do we have to do this move (and only this move) to get back to the starting position?

Fafnir
Level: Smiter

Rank Points: 315
Registered: 11-05-2004
IP: Logged

Urk... I'm too sleepy for this sort of thing! I'll write a program to solve it tomorrow.

____________________________
Stupidity kills.
Absolute stupidity
Kills absolutely.

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

[Edited by stigant at Local Time:12-29-2004 at 09:37 PM]

____________________________
Progress Quest Progress

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

Nope.

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

oops, you're right... I went different directions.


____________________________
Progress Quest Progress

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

Thats better You're up.

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Start with a regular hexagon with side of length 1. Choose two consecutive vertices, and construct an ellipse which has these vertices as focci, and which passes through the center of the hexagon. Find the intersection of the ellipse and one side of the hexagon. How far is this intersection from the endpoints of the side?

____________________________
Progress Quest Progress

wackhead_uk
Level: Smiter

Rank Points: 352
Registered: 06-21-2004
IP: Logged

I think.

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

nope

____________________________
Progress Quest Progress

Hix
Level: Master Delver

Rank Points: 106
Registered: 12-31-2004
IP: Logged

Hmmm.... Well the center of the hexagon is distance 1 from the verticies (disect the hexagon into 6 triangles to see this easily), so all points on the ellipse must have distances to the focii which add to 2. Draw a few extra lines, and do some a^2+b^2=c^2. I got that the intersection is 3/5=.6 from the closest focus (and 7/5=1.4 from the other).

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Yes, that's correct.

____________________________
Progress Quest Progress

Hix
Level: Master Delver

Rank Points: 106
Registered: 12-31-2004
IP: Logged

A group of 200 pirates discovers a legendary treasure, and they must decide who gets to keep it (it cannot be divided in any way -- only one pirate gets the treasure). They all want the treasure, but they are honorable pirates, so instead of fighting over it, they consult the Pirate Code, which tells how to deal with the situation.

Now all of the pirates have a rank on their ship: the captain is #1, his first mate is #2, etc. down to the lowliest crew member at #200. According to the Code, the _lowest_ ranking pirate must nominate one pirate (he may choose himself) to recieve the treasure. Then all pirates (including the lowest ranking one) vote on his proposal: "Aye" or "Arrrgh." If at least half vote "Aye" then the proposal is accepted, and the nominee gets the treasure. But, if there are more "Arrrgh" votes than "Aye" votes, the pirate who made the nomination must walk the plank (in which case he will be eaten by sharks), and the _next lowest_ ranking pirate must now nominate someone. The voting process repeats until a proposal passes by getting enough "Aye" votes.

Each pirate's top priority is to stay alive: He will not do anything which increases his risk of death. His next priority is to get the treasure. And lastly, even though they are honorable, they are all bloodthirsty pirates. This means that they prefer that other pirates walk the plank, if that does not hurt their chances at the top two priorities.

The problem is to determine the fate of the pirates. How many (if any) walk the plank? Which pirate gets the treasure?

Assume the pirates are logical and rational, of course.

Fafnir
Level: Smiter

Rank Points: 315
Registered: 11-05-2004
IP: Logged

OK - my thoughts:

1) The pirate who is nominated will always vote 'Aye' to increase his chances of getting the treasure. Ergo, to maximise the 'Aye' votes and thereby his chances of survival, the nominator will never nominate himself unless he is the first mate or captain, in which case his own 'Aye' vote will suffice for the treasure and his survival.

2) The captain and first mate will always vote 'Arrgh' unless they are nominated, as they cannot be forced to walk the plank by the rules of the game.

3) Therefore, to maximise his chances of survival, the nominator will always nominate the captain or first mate.

4) Allowing the lowest-ranked pirate to walk the plank decreases everyone's chance of survival (by increasing the chance that they will be forced to choose a name), so everyone except the captain and first mate will vote 'Aye' regardless of who is nominated.

Therefore, no-one walks the plank, as everyone says 'Aye' to the first nominator. This pirate nominates the captain or first mate (logically, there is no distinction), as they have the most reason to vote 'Arrgh', so either the captain or the first mate gets the treasure.

Or alternatively, the pirate ranked #200 realises this and nominates himself, getting the treasure.

____________________________
Stupidity kills.
Absolute stupidity
Kills absolutely.

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

Well, I think you have to reduce this to the base case and recur back up....

If there's only one pirate (ie the captain) then the captain gets the treasure
If there's 2 pirates (captain and first mate) then the mate nominates himself since he only needs one vote (his own), and he gets the treasure
If there's 3 pirates, the 3rd pirate needs to get one vote to stay dry. He can't buy the 2nd pirate's vote since if 3 walks the plank, 2 gets the treasure (and a water show to boot). So he nominates the captain who would rather have the treasure than see 3 get wet.
If there's 4 pirates, the 4th pirate needs to get one vote to stay dry. He can't buy the captains vote (since if 4 walks the plank, the captain gets the treasure), so he buys the first mate's vote by nominating him.
If there's 5 pirates, the 5th pirate is screwed since he needs to buy 2 votes. He can't buy the first mate's vote since 1st mate wins with 4 pirates. He could buy the captain's vote (Or the 3rd or 4th pirate's votes) but only one since they all lose unless they are nominated.
Here's where it starts to get interesting.
If there are 6 pirates, the 6th pirate needs 2 votes, but he can count on the 5th pirate's vote since the 5th pirate wants to stay dry. So he can nominate anybody he likes. (other than himself of course)
Unfortunatly, my mother-in-law has come in and needs her computer... back in a few minutes.

[Edited by stigant at Local Time:12-31-2004 at 03:38 PM]

[Edited by stigant at Local Time:12-31-2004 at 03:38 PM]

____________________________
Progress Quest Progress

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

oh, and the 6th pirate can't nominate the 1st mate since the 1st mate will win anyway if 6 walks the plank.

which leaves the captain, the 3rd, and the 4th pirates. They each have a 1/3 chance of getting the treasure.

Ok, onto 7 pirates...
7 needs 3 votes. Everybody has a 0 chance of walking the plank, so he can only buy one vote. So he's screwed, but the captain, 3 and 4 have 1/3 chance of getting the treasure.

8 needs 3 votes. He'll get 7's vote, and the vote of whoever he nominates, but everybody else will vote against him.

9 needs 4 votes... he'll get 7 and 8, and the nominee's, but nobody else's

10 needs 4 votes... he'll get 7, 8 and 9, and the nominee's. So who does he nominate? Anybody but 7-10. So 1-6 all have 1/6 chance at getting the treasure.

11 needs 5 votes. he'll can only buy one, he's screwed
12 needs 5, he'll get 11 and buy one, he's wet.
13 needs 6, he'll 11, 12 and buy one, but he's wet.
14 needs 6: 11, 12, 13, nominee... kerplunk
15 needs 7: 11, 12, 13, 14, nominee... kerplunk.
16 needs 7: 11, 12, 13, 14, 15, nominee... kerplunk.
17 needs 8: 11-16, nominee... kerplunk
18 needs 8: 11-17, nominee... approved, so 1-10 have a 1/10 chance of getting the treasure.

Things continue this way... 6 is ok, 10 is ok, 18 is ok, 34 is ok(19-33 are wet, so he'll get their votes, his own vote and the nominee's vote) giving 1-18 a chance at the treasure. 66 is ok, 130 is ok, and 258 is ok.

So the solution is that pirates 131-200 walk the plank and 1-65 have an equal shot at the treasure.

____________________________
Progress Quest Progress

Hix
Level: Master Delver

Rank Points: 106
Registered: 12-31-2004
IP: Logged

That's right, 70 pirates die; stigant has explained exactly why. It is a very minor point, but #130 can nominate any of #1 thru #66. But you can't really get the 70 dead part correct if you didn't already know this, so I judge stigant as the winner. TAG

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

but #130 can nominate any of #1 thru #66.

oopsie.... um it was a typo? yeah, that's it :-)

ok, same basic set up as Hix's puzzle, but instead of 1 treasure, there are 500 gold coins (which can be divided up however you like, but no partial coins), and instead of 50% of the vote, you have to get a clear majority (ie if 3 pirates, then you have to have 2 votes including your own, if 4 pirates, you need 3 including your own etc)

____________________________
Progress Quest Progress

eytanz
Level: Smitemaster

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

The same method for solving works, though the solution is rather different:

If there was 1 pirate, he would just nominate himself to get all the treasure.

If there were 2 pirates, pirate #2 would have no chance of getting a clear majority. So, there's nothing he can do to survive, since pirate #1 gets all the treasure anyway.

If there are 3 pirates, pirate #3 needs 2 votes. He is assured of getting pirate #2's vote whatever he does, since if he walks the plank so does pirate #2, so he just nominates himself to get the entire treasure.

If there are 4 pirates, pirate #4 needs 3 votes. Since if he loses pirate #3 gets all the treasure, #3 won't vote for him. However, if he loses pirates #1 and #2 won't get any treasure at all. So pirate #4 offers 1 gold to each of them, getting their vote, and keeps the rest to himself.

If there are 5 pirates, pirate #5 also needs 3 votes. He has several options here (he can offer #4 499 coins and #3 1 coin, for instance), but he can both survive and get rich by keeping 497 coins, offering 1 coin to #3 (who gets nothing if he loses) and offering 2 coins to either #1 or #2 (who get 1 if he loses).

If there are 6 pirates, Pirate #6 needs 4 votes. He has no easy way of getting #5's vote, but he can offer 1 coin to #4, and 1 coin each to #1 and #2, since getting a sure 1 coin is better than a 50% chance of getting 2. He gets to keep 497 coins.

For 7 pirates, #7 needs to offer 1 coin to #5, 1 coin to #3, and 2 coins to either #1 or #2. He gets to keep 496 coins.

For 8 pirates, #8 needs to offer 1 coin to #6, 1 coin to #4, and 1 coin to both #1 and #2. He gets to keep 496 coins.

For 9 pirates, #9 needs to offer 1 coin to each of #7, #5 and #3, and 2 coins to either #1 or #2. He gets to keep 495 coins.

For 10 pirates, #10 needs to offer 1 coin to #8, #6, and #4, and 1 coin to both #1 and #2. He gets to keep 495 coins.

The divisions proceed the same way; an odd numbered pirate must offer 2 coins to either #1 or #2, and 1 coin to every other odd numbered pirate. An even numbered pirate must offer 2 coins to both #1 and #2, and 1 coin to every other even numbered pirate.

So, pirate #200 must offer 1 coin to #1, #2, and every even pirate from #4-#198. That's a total of 100 coins, so he gets to keep 400 coins for himself.

----

As a side note, pirate ships that operate by "Stigant's code" found themselves having a much easier time getting recruits than pirate ships operating by "Hix's code". However, these recruits, once already on the ship, had to watch their back because the next highest up pirate always seemed out to get them...




____________________________
I got my avatar back! Yay!

Hix
Level: Master Delver

Rank Points: 106
Registered: 12-31-2004
IP: Logged

eytanz wrote:

As a side note, pirate ships that operate by "Stigant's code" found themselves having a much easier time getting recruits than pirate ships operating by "Hix's code". However, these recruits, once already on the ship, had to watch their back because the next highest up pirate always seemed out to get them...

But if there are more than 1000 pirates (twice as many as there are gold pieces) the same difficulty will arise. There will be certain "stable" numbers of pirates (like 3, 4, 6, 10, 18, 34, 66, and 130 in the first pirate puzzle) with increasing differences between consecutive stable numbers.