TranceAddict Forums (www.tranceaddict.com/forums)
- Chill Out Room
-- Which did come first...
Pages (4): « 1 2 [3] 4 »

A chicken and an egg were lying in bed very sweaty and smoking a cigarette. After a while the egg turns to the chicken and says 'well i guess we've finally solved THAT issue!'

quote:

Originally posted by Flyboy217 Are you familiar with the Gosper-Zeilberger algorithm for finding closed forms for hypergeometrics, for example?

yes, i heard about it.

quote:

Originally posted by Flyboy217 I'm curious, are you a math undergraduate?

yes.and you are a graduate student?

quote:

Originally posted by Flyboy217 Oh and so that I have something to contribute, too, I'd like to share a problem or two.

all right, i will study them in depth when i have more time. at the moment i *think* i know how to do two of them.

quote:

Prove that there are two distinct permutations b and c, such that n! is a divisor of S(b) - S(c)

ok. if s(b)-s(c) weren't a multiple of n!, the remainders of s(a), s(b), etc. would form a complete residue system modulo m! because otherwise we would have

s(d) mod n! = s(e) mod n! ⇔ s(d)-s(e)≡0(mod n!) for some particular permutations d and e.

so assume n! does not divide s(b)-s(c) for any two distinct permutations. then since there are n! of such permutations in total, we have

∑_i=1^n!s(p_i) ≡ 0+1+2+3+...+n!-1 (mod n!) ≡ n!(n!-1)/2 (mod n!)

on the other hand, there are (n-1)! permutations in which the 1st term in a equals 1, (n-1)! permutations in which the same term equals 2... (n-1)! permutations in which it equals n. so k₁ is multiplied by each of them (n-1)! times. hence its cumulative weight equals

(n-1)!(1+2+3+...+n) = (n-1)!(n+1)n/2 = (n+1)!/2

the above applies to the rest of k's as well. so we have

∑_i=1^n!s(p_i) = (n+1)!/2(k₁+...+k_n)

hence,

(n+1)!/2(k₁+...+k_n) ≡ n!(n!-1)/2 (mod n!)

but (n+1)!/2 = n!(n+1)/2, which yields no remainder when divided by n! because n+1 is even.

at the same time, n!-1 is odd and hence is not divisible by 2.

a contradiction.

quote:

Show that there exist two disjoint subsets of S whose sums are equal.

we have |P(A)|=2^|A|

in this case, |P(A)|=2¹⁰=1024

since the greatest possible sum is 99+...+90=945, by the pigeonhole principle there must be at least 2 subsets with the same sum. call them B and C. then B-C and C-B are *disjoint* subsets with the same sum.

quote:

Originally posted by Noisician yes.and you are a graduate student?

No, I graduated with a CS degree some years back.

Your solutions are both correct. If you really solved them on the fly, then I'm thoroughly impressed. Both are from former International Math Olympiads, and the latter took me upwards of an hour to figure out (the former is far easier, of course). Did you ever compete at the IMO level?

quote:

Originally posted by Flyboy217 No, I graduated with a CS degree some years back. Your solutions are both correct. If you really solved them on the fly, then I'm thoroughly impressed.

actually, i spent about 45/50 minutes on this board figuring out/writing the solution. so i wouldn't say it was some kind of sudden irradiation. i just think 1b and especially 1c are going to take much longer than 1 hour to get them done.

quote:

Originally posted by Flyboy217 Both are from former International Math Olympiads, and the latter took me upwards of an hour to figure out (the former is far easier, of course). Did you ever compete at the IMO level?

no, not international. i did participate in a number of national olympiads though.

quote:

Originally posted by Noisician actually, i spent about 45/50 minutes on this board figuring out/writing the solution. so i wouldn't say it was some kind of sudden irradiation. i just think 1b and especially 1c are going to take much longer than 1 hour to get them done.

Whew, I feel a lot better . Still, impressive... I haven't found another TA who can solve problems at that level. For someone experienced with the pigeonhole principle, 1a is fairly trivial. 1b still took me (and friends) several hours. It's slightly painful, but still produces some nice ideas. Props if you solve 1c (since it's of course unsolved).

quote:

no, not international. i did participate in a number of national olympiads though.

Did pretty well I imagine?

Let's step up the heat

quote:

Given n > 2 points in the plane, no three collinear, show that some line is incident on exactly two points.

quote:

There is an nxn grid of cells. The state of each cell is always either "on" or "off." The cells evolve at discrete time intervals, by the following rules. 1) If at time t, a cell is on, then it will also be on at t+1. 2) If at time t, a cell is off, and has at least 2 adjacent neighbors (that is, cells that share an edge, so not diagonally), it turns on at time t+1. Show that, if at some time t, all n2 cells are on, then at no point in the past were fewer than n cells on.

I believe science explains life, and since Evolution is the best "scientific" theory (I wouldn't classify creationism as a scientific theory - it is religious dogma) as to the origins of life, I subscribe to that. And from that point of view the egg clearly came first. As the bird which was the chicken's evolutionary ancestor incrementally evolved with each generation, there was a point at which it had evolved enough chicken-like traits to be classifiable as a chicken. The first bird that was classifiable as a chicken, hatched from an egg... the egg however was laid by something other than a chicken (as it had not evolved in to a chicken yet). Therefore the egg came first.

quote:

Originally posted by Flyboy217 Given n > 2 points in the plane, no three collinear, show that some line is incident on exactly two points.

for any particular but arbitrary n > 2, let P be the set of n given points and L the set of all lines incident on two or more of them. since not all the points are on any one such line, there exist a line and a point not on this line for which the distance between them is minimal. call them l and A correspondingly. now suppose l is incident on three of the given points. then at least two of them have to be on one side of the perpendicular AA'. without loss of generality, assume these two points (B and C) are on the left side, with B being closer to A'.

triangles AA'C and CBB' are similar. we have CA > CA' > CB. hence AA' > BB'. and since CA is incident on A&C∈P, CA itself ∈ L, giving us a pair with the smaller distance between them, which contradicts the minimality of AA'.

quote:

Originally posted by Noisician for any particular but arbitrary n > 2, let P be the set of n given points and L the set of all lines incident on two or more of them. since not all the points are on any one such line, there exist a line and a point not on this line for which the distance between them is minimal. call them l and A correspondingly. now suppose l is incident on three of the given points. then at least two of them have to be on one side of the perpendicular AA'. without loss of generality, assume these two points (B and C) are on the left side, with B being closer to A'. triangles AA'C and CBB' are similar. we have CA > CA' > CB. hence AA' > BB'. and since CA is incident on A&C∈P, CA itself ∈ L, giving us a pair with the smaller distance between them, which contradicts the minimality of AA'.

Please, oh please tell me you had already read this solution somewhere. Sylvester's Theorem was an open problems for many decades, and this particular solution is generally regarded as the most elegant. In any case, it's nice to know the solutions to such problems

quote:

Originally posted by Flyboy217 Please, oh please tell me you had already read this solution somewhere. Sylvester's Theorem was an open problems for many decades, and this particular solution is generally regarded as the most elegant. In any case, it's nice to know the solutions to such problems

of course i was already aware of the theorem, just like any other mathematician i know. i'm still not sure why you wanted me to prove something whose proof(s) can be easily found in a number of elementary books on metric/euclidean topology. i mean, what's the point of proving a theorem that is nowadays considered a well-known fact in mathematics?

quote:

Originally posted by Noisician of course i was already aware of the theorem, just like any other mathematician i know. i'm still not sure why you wanted me to prove something whose proof(s) can be easily found in a number of elementary books on metric/euclidean topology. i mean, what's the point of proving a theorem that is nowadays considered a well-known fact in mathematics?

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.

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.

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?

chicken - egg

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!"

this thread has survived its creator.

quote:

Originally posted by {b.s.e.} this thread has survived its creator.

did he finally kill himself or something?

quote:

Originally posted by Noisician yes, i explained that in the post right above the one you quoted.

Like I said, please disregard that prior post

quote:

Originally posted by Noisician btw, you want to try to solve one of my favorite problems?

It's a common problem of course. I'd written a computer program to solve it, and I think the answers were 4 and 13? Off the top of my head I don't know of a more elegant way of solving it.

Is there one? If so, I'll give it more thought when I have time.

quote:

Originally posted by Flyboy217 It's a common problem of course. I'd written a computer program to solve it, and I think the answers were 4 and 13? Off the top of my head I don't know of a more elegant way of solving it. Is there one? If so, I'll give it more thought when I have time.

correct, 4 and 13. this problem was on the final for my number theory class i took a couple of years ago. computers were, of course, not allowed. what i like about it the most is the fact that it can seem incredibly confusing to many people in the sense that it is simply unclear how to proceed with it. out of all the people whom i asked to study this problem, quite a few didn't even know where to start, let alone actually solve it. so i'm glad you were able to find a solution all by yourself. but yeah, a computer would certainly be of great help here because the way we had to do it turned out to be unreasonably arduous.

Powered by: vBulletin
Copyright © 2000-2021, Jelsoft Enterprises Ltd.