|
Which did come first... (pg. 6)
|
View this Thread in Original format
| Noisician |
| 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 :p |
|
|
| Flyboy217 |
| 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 :p |
Yeah yeah but at least we make cool ... 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.
|
|
|
|
| Noisician |
okay, i'm back online now. (had to do loads 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. |
|
|
| 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. |
|
|
| tranceaddikt143 |
| what in the flaming hell |
|
|
| Flyboy217 |
| 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. |
|
|
| Noisician |
| 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? :p
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. |
|
|
| Flyboy217 |
| 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" :p
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" :) |
|
|
| CityKitty |
[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. |
|
|
| Noisician |
| quote: | Originally posted by Flyboy217
So you meant "pigeonholes" :p |
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? |
|
|
| Izzy |
| 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!" |
|
|
| {b.s.e.} |
| this thread has survived its creator.:p |
|
|
|
|
