Comments about problems on graphs
and probability for Rutgers YSP, summer 2006

About the assignment for Tuesday

1. Well done.

2. Well done. Buffon's needle problem is a way of estimating Pi using a geometric probability argument. There are many web pages discussing this problem. One small part of the discussion needs calculus to compute an area.

3. Well done.

4. Well done, but students did not report on the expected time needed for one "flip". I should have mentioned a possible extension: given p (the probability of heads) with 0<p<1, can you explain how to use a fair coin to simulate a sequence of (p,q) biased coin flips (q=1-p). The problem asked for the case p=2/3.

5. Well done. And here is a link to Neil Sloane's Encyclopedia of Integer Sequences.

About the assignment for Wednesday

1. a) and b): Well done. As for c), really (0,1) and all the reals are the same (!). You can describe, as I tried, a geometric correspondance. Or, how about tan([Pi/2]·[x-1]): fairly explicit!

2. Well done. I should have remarked that after the great distress that this result of Cantor's caused in the mathematical community, the use of continuity (close-by points are mapped to close-by points, and there is no tearing or ripping or ...). So it turns out there is no one-to-one and onto mapping (bijection) between the interval and the square which is continuous.

3. Here students made an error. Throw out the first interval, whose length=1/4. The second two intervals have total length=2(1/42). The four intervals thrown out in the third stage have total length=22(1/43). Etc. All of these intervals are disjoint. So the first term in the geometric geometric series is 1/4, and the (constant) ratio between successive terms is 2/4=1/2. The sum is 1/2. So what is left has probability 1/2. It turns out that this set has no interval inside it even though it has positive "length" or probability. These facts together seemed startling to me when I first saw it.

4. A remarkable result. Please note that proving certain "naturally occurring" numbers such as Pi and e are transcendental is difficult. There are some "artificial" (?) numbers (first displayed by Liouville) that can be proved to be transcendental without much effort. All of these proofs, though, use some results from calculus.

5. The barber in the village who shaves everybody who does not shave himself ... Here I was disappointed in the student presentation. The difficulty is following a logical argument. You need to show that there can be no bijection, not that one specific suggestion bijection is invalid. If you are given a candidate, F, you should consider the set NIF. If every subset of X corresponds to an element of X then there must be an x in X with F(X)=NIF. But then either x is an element of F(X) or x is not an element of F(X).
If x is an element of F(X), then since F(X)=NIF, by the definition of NIF, x is not in F(X). This is a contradiction.
If x is not an element of F(X), then x must be a member of NIF since it satisfies NIF's descriptive phrase. But since F(X)=NIF, we know x is an element of F(X): again a contradiction>

Therefore x is not in and not not in F(X). This is impossible (the "law of the excluded middle") so our assumed bijection F cannot exist.

As I mentioned, this problem shows that there is not a biggest set. Then a whole bunch of other puzzling problems occur.

6. So for all this set stuff collections of disjoint sets with positive probility must have be very "big" -- no more than a sequence of sets.

About the assignment for Thursday

I thought that most of the presentations were quite good, and demonstrated understanding and more than minimal competence. I wish, though, that people would generally be more comfortable explaining their ideas.

1. (1-[1-p]2)n.

2. 1-(1-pn)2=2pn-2p2n.

3. a) Well done. I should have asked, however, how students chose the root of the quadratic equation (there is a +/- in the formula!).
b) I am very happy that the TI-89 was able to handle the polynomial computation. Could it also have graphed K3?

4. Well done.

5. I think there is an algebraic formula for the roots of a cubic, so maybe this can be given explicitly.

6. Well done.

About the assignment for Friday

1. This works just like my first "recreational example" (any 6 integers between 1 and 10 have a pair with odd sum): use parity (odd/even). For b), since 2 is the cardinality of {odd,even} we need 2·2·2=...

2. Maybe this is "easy" since 5·5=25 and 2·25=50<51. To me, the result is still irritatingly non-constructive.

3. One million pigeons is much bigger than 600,000 pigeonholes.

The theorem of Dirichlet that I mentioned is:
If x is irrational, then there are infinitely many integers p and q so that |x-p/q|<1/q2.
A proof and discussion are here.

4. 127, I bet. And, even Rn≤22(n-1)-1.

5. I guess that this Ramsey number is dominated by 3n(constant?)-1 or something like that. Certainly it is greater than ...

6. So here is the result of a "session" I just had (2 PM, Friday, July 21) with Maple on the computer in my office. We have this program installed on most systems. A major reason we chose Maple rather than Mathematica is that it was cheaper.

 > A:=2^14*6!; A := 11796480

> poly:=n->(1/A)*n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5);
                         n (n - 1) (n - 2) (n - 3) (n - 4) (n - 5)
            poly := n -> -----------------------------------------

> poly(10.);

> poly(15.);

> poly(19.);

> poly(17.);

> poly(18.);

I think that R6 is at least 18.

A useful quote about practice

... There have been many studies of elite performers -- concert violinists, chess grand masters, professional ice-skaters, mathematicians, and so forth -- and the biggest difference researchers find between them and lesser performers is the amount of deliberate practice they've accumulated. Indeed, the most important talent may be the talent for practice itself. K. Anders Ericsson, a cognitive psychologist and an expert on performance, notes that the most important role that innate factors play may be in a person's willingness to engage in sustained training. He has found, for example, that top performers dislike practicing just as much as others do. (That's why, for example, athletes and musicians usually quit practicing when they retire.) But, more than others, they have the will to keep at it anyway.

(From "The Learning Curve" by Atul Gawande, an article on the training of surgeons appearing on pages 52-61 of The New Yorker, January 28, 2002.) The article is also included in Complications, A Surgeon's Notes on an Imperfect Science, an interesting collection of Gawande's essays.

Maintained by and last modified 7/6/2006.