|
Which did come first... (pg. 5)
|
View this Thread in Original format
| Flyboy217 |
| quote: | Originally posted by Noisician
let me tell you something. modern set theory is well-known for its dogma of reductionism that aims to reduce all mathematical concepts to the notion of class and the relation 'being a member of'. as a result, in set theory a function is considered to be a special case of a relation, which itself happens to be a subclass of the cartesian product of a number of (not necessarily distinct) classes.
...
a similar story happened to cardinals. when cantor first introduced cardinals, he regarded them as special abstract entities of a brand new kind. obviously, this was a big no-no for all advocates of the reductionist program. so there were a few attempts made to redefine cardinals in terms of hitherto posited objects of set theory. |
This is why I always loved math. It has a rich history to it, and understanding the details of past arguments makes us so much the more able. Are you familiar with the Gosper-Zeilberger algorithm for finding closed forms for hypergeometrics, for example? It just blows me away that one can learn in school today ways to solve problems that remained elusive to the best minds for centuries.
I thank you for sharing. I've already shared the Cantor/Russell proof with several friends :)
P.S. I'm curious, are you a math undergraduate?
Oh and so that I have something to contribute, too, I'd like to share a problem or two.
While we're on sets:
| quote: |
1a) S is a set of 10 natural numbers less than 100. Show that there exist two disjoint subsets of S whose sums are equal.
Definition: We say that a finite set X of integers has distinct subset sums if no two distinct subsets of X have the same sum.
1b) Suppose T is a set of 10 natural numbers less than M. Find the smallest M such that T may have distinct subset sums.
1c) This conjecture is attributed to Erdos and is an open problem:
Let X be a subset of {1,2,..,n} with distinct subset sums. Is it true that |X| < log_2(n) + C for some fixed constant C?
|
Part a I heard somewhere, part b is mine, and part c... well good luck :) And here's a favorite from a competition:
| quote: |
Let n be an odd integer greater than 1, and let k1, k2, ..., kn be given integers. For each of the n! permutations a = a1, a2, ..., an of 1, 2, ..., n, let
S(a) = Σni=1kiai
Prove that there are two distinct permutations b and c, such that n! is a divisor of S(b) - S(c).
|
Enjoy:) |
|
|
| BTG |
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! |
|
|
| -=M=- |
| 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!' |
|
|
| Noisician |
| 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=1n!s(pi) ≡ 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 k1 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=1n!s(pi) = (n+1)!/2(k1+...+kn)
hence,
(n+1)!/2(k1+...+kn) ≡ 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)|=210=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. |
|
|
| Flyboy217 |
| 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? |
|
|
| Noisician |
| 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. |
|
|
| Flyboy217 |
| 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.
|
:) |
|
|
| astroboy |
| 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. |
|
|
| Noisician |
| 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'. |
|
|
| Flyboy217 |
| 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 :) |
|
|
| Noisician |
| 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? |
|
|
| Flyboy217 |
| 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. |
|
|
|
|
