the egg had to come first. due to evolution. A bird can't evolve during life, its in the offspring that evolution takes place.

THINK PEOPLE!

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.

___________________

Last edited by Noisician on Jun-17-2004 at 16:40

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?

Last edited by Flyboy217 on Jun-17-2004 at 19:34

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.

___________________
"my son will be a gienues(sp?)" - Originally posted by Googooly
"many species of bear give blowjobs." - Originally posted by Sunsnail.. NOW CONFIRMED BY PHOTO EVIDENCE!
"astroboy is brave and gentle and wise." - Originally posted by pkcRAISTLIN
"ew! i wouldn't go anywhere near a homeless dudes butthole... not even if i was sodomizing him with a poison ivy cactus dildo" - Originally posted by lücid
"also can someone post the link to my mom's forum, thank you!" - Originally posted by miamitrance04
"dude man its not me its what the world does to me. Trust me I'm a normal person people just constantly fuck with me." Originally posted by ********
"I can see Lira getting a hard-on already. And believe me, Brazilian ass rape is the worst." - Originally posted by Meat187

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.