quote:

Originally posted by Flyboy217 Ahh but see, I am no mathematician. This was just a problem my friend gave me, after which I found it had a name and a solution. I like presenting such problems to smart friends to see what they come up with.

ah okay then. you computer scientists always learn everything too late in order for it to be considered news anymore

___________________

quote:

Originally posted by Noisician ah okay then. you computer scientists always learn everything too late in order for it to be considered news anymore

Yeah yeah but at least we make cool shit... You mathematicians are too abstract

You like combinatorics-type problems? Here's a recent favorite, that's not too bad:

quote:

There are 41 rooks on a 10x10 chess board. Show that there must exist 5 that do not attack each other.

okay, i'm back online now. (had to do shitloads of things irl this week)

quote:

Originally posted by Flyboy217 You like combinatorics-type problems? Here's a recent favorite, that's not too bad:

this shouldn't be too hard to prove. sounds like your typical p-hole principle kind of problem. the only difficulty that i see with this right now seems to be that of finding (41-1)/4 = 10 distinct holes. i'll see what i can do.

___________________

all right. here's how you prove it:



each hole is a monochromatic set of 10 squares in the picture. the rest is self-explanatory.

___________________

what in the flaming hell

___________________

quote:

Originally posted by Noisician all right. here's how you prove it: each hole is a monochromatic set of 10 squares in the picture. the rest is self-explanatory.

I'm gonna spend a bit of time and try to figure out what you mean.

In the mean time, here's how I solved it:

There is some row with [41/10] = 5 rooks
There are at most 31 rooks not in that row, so another row contains at least [31/10] = 4 rooks.
Similarly for 3, 2, and 1 rooks.

Select 1 rook from the last identified row, another in a different column with the second to last (the one with at least 2), up throuogh 5, and you're done.

quote:

Originally posted by Flyboy217 I'm gonna spend a bit of time and try to figure out what you mean. In the mean time, here's how I solved it: There is some row with [41/10] = 5 rooks There are at most 31 rooks not in that row, so another row contains at least [31/10] = 4 rooks. Similarly for 3, 2, and 1 rooks. Select 1 rook from the last identified row, another in a different column with the second to last (the one with at least 2), up throuogh 5, and you're done.

heh, why overcomplicate things?

5 rooks cannot attack each other iff they are in different rows AND columns. now note that i only used 10 colors to divide the board into 10 equal parts. in other words, i've got 10 pigeonholes that cover the entire area of the board. also note that even if 10 rooks were in any one such hole, they could not attack each other (look at the way 10 yellow squares are situated in the picture, for example). we've got 41 pigeons and 10 holes (again, they cover the whole board, so each pigeon MUST go in one of the holes). by the principle, some 5 pigeons must be in one hole. but no pigeons in the same hole can attack each other by construction of the hole.

___________________

quote:

Originally posted by Noisician all right. here's how you prove it: each hole is a monochromatic set of 10 squares in the picture. the rest is self-explanatory.

Disregard my last post. It was Friday night and I was a wee bit drunky. I was sitting there looking at those little dot things and going "Holes? Are those holes? They LOOK like holes..." So you meant "pigeonholes"

Sure, each hole is comprised of squares that do not attack each other. At least [41/10] = 5 rooks must be in one of those holes. I like it! How long did it take you to produce that picture anyway? You could have just said something like "diagonal stripes are holes"

[QUOTE]Originally posted by Noisician
[color=white]all right. here's how you prove it:



if you stare at this thing long enough I think you might start to hallucinate. Either way this whole thing is giving me a headache.

___________________
My love will go up in flames for you...

quote:

Originally posted by Flyboy217 So you meant "pigeonholes"

yes, i explained that in the post right above the one you quoted.

quote:

Originally posted by Flyboy217 I like it! How long did it take you to produce that picture anyway?

ummm... 5 minutes? probably even less than that. the grid option was already in the program - i just had to zoom in to make it look wider. i then began putting colored blobs in tens, starting with the leftmost square in the bottom row and moving diagonally thereafter. that's all.

the entire problem took me a little less than 40 minutes. it was pretty straight-forward.

-------------------------------------------------------------------

btw, you want to try to solve one of my favorite problems?

a certain person picked two natural numbers, each of which was greater than 1 and smaller than 100. to Mr. A, that person gave only the sum of these numbers. to Mr. B, the person gave only their product. they were then asked to find the numbers, but they were not allowed to tell each other what they initially knew about them..

when A & B (who were mathematicians, btw) met together, they had this short dialogue:

B: i'm afraid i can't deduce the right answer. there is not enough information given.
A: yes, i know that you can't possibly know the answer. i can even prove that.
B: in that case, i know what the numbers are, as you just unintentionally gave me a great hint.
A: but now i, too, know the answer, as what you just told me is enough for me to find both numbers.

believe it or not, this dialogue is all you need to be able to figure out what the numbers were, without even knowing their sum or product.

so what are these numbers?

___________________

Last edited by Noisician on Jun-27-2004 at 20:49

A chicken and an egg are lying in bed. The chicken is leaning against the headboard smoking a cigarette with a satisfied smile on its face. The egg, looking a bit pissed off, grabs the sheet and rolls over and says, "Well, I guess we finally answered THAT question!"

___________________
If God is the answer, it must have been a very stupid question.

this thread has survived its creator.

___________________
Wave is to particle as zero is to one as bagpipes are to modem noises.