Saturday, October 18, 2008

Our blog are alive now!

Tuesday, September 30, 2008

The Pigeon Hole Principle (a part of Introduction to proof book)

The so called pigeon hole principle is nothing more than the obvious remark: if you have fewer pigeon holes than pigeons and you put every pigeon in a pigeon hole, then there must result at least one pigeon hole with more than one pigeon. It is surprising how useful this can be as a proof strategy.
Example
Theorem. Among any N positive integers, there exist 2 whose difference is divisible by n-1.
Proof. Let a1, a2, ..., an be the numbers. For each ai, let ri be the remainder that results from dividing ai by n - 1. (So ri ai mod(n-1) and ri can take on only the values 0, 1, ..., n-2.) There are n-1 possible values for each ri, but there are n ri's. Thus, by the pigeon hole principle, there must be two of the ri's that are the same, rj = rk for some pair j and k But then, the corresponding ai's have the same remainder when divided by n-1, and so their difference aj - ak is evenly divisible by n-1.
Example
Theorem. For any n positive integers, the sum of some of these integers (perhaps one of the numbers itself) is divisible by n.
Proof. Consider the n numbers b1 (a1) mod(n), b2 (a1 + a2) mod(n), b3 (a1+a2+a3) mod(n), ..., bn = (a1 + ... + an) mod(n). If one of these numbers is zero, then we are done. Otherwise, only the n-1 numbers 1, 2, ..., n-1 are represented in this list, and so two of them must be the same, bi = bj (say i < j). This would then imply that (ai+1 + ... + aj) mod(n) = 0, proving our claim.
Exercises
Prove each of the following using the pigeon hole principle.
If a city has 10,000 different telephone lines numbered by 4-digit numbers and more than half of the telephone lines are in the downtown, then there are two telephone numbers in the downtown whose sum is again the number of a downtown telephone line.
If there are 6 people at a party, then either 3 of them knew each other before the party or 3 of them were complete strangers before the party.

Saturday, September 27, 2008

Relax! back at one

Back at One - Brian McKnight

Books available in software!

Introduction to Proofs
New World Selection I
New World Selection II

Elementary Math word Problems (7th Grade)

12th grade—International Books
Advanced Calculus with Applications in Statistics
103 Trigonometry problems
104 Number Theory Problems
The William Lowell Putnam Mathematical Competition 1985-2000
Hypercomplex Numbers in Geometry and Physics
IMO Competition 1959-2004
Mathematical Problems and Proofs, Kluwer Academic
Math Olympiad problems Collection, version 1
Math Olympiad Problems and Solutions from around the world 1995-1996
Topics in Inequalities - Theorems and Techniques (1st Edition), Hojoo Lee
Mathscope, Vietnamese journal
Math Excalibur
IMO Compedium

Good tips for Mathematics Olympiad participants!

The term "olympiad" is used generically to refer to a math contest in which students are asked not to compute numerical answers, but to give proofs of specified statements. (Example: "Prove that 2003 is not the sum of two squares of integers.") The most famous example is the International Mathematical Olympiad; most countries that participate at the IMO have national olympiads as part of their team selection process. Some areas have additional olympiads at the regional or local level.

The jump from short answers to olympiads is a tough one. Here are some tips for students making this transition.

Practice, practice, practice.

The only way to learn math is by doing.Proofs are essays. The better written a proof is, the more likely it is to be understood. Even such mundane things as grammar, spelling and handwriting are worth a bit of attention.

Define your terms. If you're going to use a word in a way that might not be commonly understood, define it precisely. Then stick to your definition!

Read the masters. No one ever learned how to do good mathematics in a vacuum. When you do practice problems, read the solutions even of the problems you solved.

There's more than one road. Different solutions can be equally valid; even when solutions agree in substance, differences in perspective can be significant and valuable.

It's not over when it's over. Don't hesitate to continue thinking about the problems on a contest after the time ends, or to discuss the problems with others.

Learn from your peers. They're smarter than you might have expected.

Learn from the past. Try to relate new problems to old ones; you may learn something from the similarities, or from the differences.

Patience. No one said this was easy!