Day 2• Counting and its use (数え方とその利用）– Everyone knows, but few can use– Every mathematical proof uses counting• Even the proof of Fermat last theorem byAndrew Wiles• Today’s topic: Pigeonhole principle

Pigeonhole principle
鳩の巣原理• If Ｎ pigeons are in M holes and N>M, there isa hole with at least two pigeons

Ｎ羽の鳩がM個の巣箱に入っているとする。
N＞M なら、２羽以上の鳩が入っている巣がある

Figure is takenfrom Wikipedia

In modern mathematics
現代数学風に書くとConsider a map F from a finite set S to T.
If |S| > |T|, the map cannot be injective.
• 有限集合Sから有限集合Tへの写像Fがある
とき、|S|>|T|ならF は単射ではない
Note: Many of you may be confused justbecause of ignorance of “mathematical language”,
and it is irrelevant to your mathematical ability.

Paul Erdős asked to“genius epsilons”
For any set of 101 integers
in the range [1,200], prove two facts:
200以下の自然数が101個ある。下の2命題を示せ
1．It has a pair of coprime numbers
互いに素な2つの数が必ずある• 14 and 15, 18 and 35• (2,4,6,8,…200) 100 numbers without coprime pair

2．It has a pair one is divisible by another約数の関係にある2つの数が必ずある。
• 3 and 12 , 15 and 45• (101,102,103,..,200) 100 numbers without such pairSolution for problem 1• Existence of a coprime pair
互いに素な数の存在を示そう• Pegions＝101 positive integers  N=１0１• We want to make (at most 100) holes,
such that if two integers are in a hole, they
are coprime.
１０１匹のハト（正整数）を入れる１００個以下の巣を作る （巣に入る数は素であるように）Solution for problem 1, cont.
• We make 100 holes– （1，2), (3，4),…, ( i, i+1),…,(199,200)– M=100 holes N=101 pigeons– 巣の数は１００、鳩の数は１０１• Use pegeon hole principle!
– For any 101 numbers, there is a hole (k, k+1)
contains two of them (pigeons)– k and k+1 are coprime !

Solution of problem２• S: a set of １０１ positive integers <201
– S has a and b such that a is divisible by b

• Pegions＝101 numbers N=１0１• How to construct holes– Each hole has numbers such that each pair isdivisible pair
– (1,2,4,8,16,32,64,128)– (3, 6, 18, 90, 180)

Solution of problem２• Holes：（1,2,4,8,..), (3,6,12,24,..),(5,10,20,..),( 2i+1, 2(2i+1),4(2i+1),…),…, (197), (199)– Odd number and its multiple by 2 powers
奇数とその２べき倍– 100 holes covering all integers <201
200 以下の数は必ずどこかに入っている– There are pegions a > b in the same hole
同じ巣に入る2羽の鳩a > b が居る。
– a = 2k b

Pegionhole principle: advanced• Show that any set of 10 natural numbers <101 has two subsets such that the sum ofnumbers in subsets are same.
• 100 以下の１０個の自然数の集合は2つの部分集合で、その成分和が等しいものを持つことを示せ• (1,3,8, 16, 20, 50 )  1+3+20 = 24= 8+16
• What are pigeons? What are holes?

Solution• Given a set S of 10 numbers• Holes: 1,2,3,…, 1000
• Pigeons: Subsets of S
• What means “ a pigion is in a hole??”• The rest is given by using whiteboard

Extended pigeonhole principle• If Ｎ pigeons are in M holes and N> kM,
there is a hole with at least k+1 pigeons
Ｎ羽の鳩がM個の巣箱に入っているとする。
N＞kM なら、k+1羽以上の鳩が入っている巣があるExpert use of pigeonhole
Show that any sequence of n2 +1 different real
numbers contains a monotone increasing ordecreasing subsequence (not necessarilyconsequent) of length n+1.
長さn2+1の実数列（同じ数はないとする）は必ず長さn +1以上の単調増加あるいは単調減少部分列を持つことを示せ。
Erdős -Szekeres’s theorem

Proof of Erdos-Szekeres• Sequence a1,a2,…,aN, N = n2+1 (pegions)• L(j)：largest length of increasing subsequence
starting from aj• S(ｋ）＝｛aj: L(j)=k }• S(1), S(2),..,S(n): holes– If there is a pigeon not in the hole, we have an
increasing sequence of length n+1 (why?)– If all pigeons are in the holes, there is a hole containingn+1 pigeons• The set of elements in the holes makes decreasing sequence– Q.E.D (Do you understand? If so, genius!)

Pigionhole: Algorithmic use• Given a set S of n points in the plane• Find the nearest pair of points• Algorithm (by M. I. Shamos)
1. Sort S with respect to x-values
2. Divide S at the middle x-value to A and B
3. Recursively find nearest pairs in A and B
independently
4. Deal with pairs (a, b) such that a ∈A andb∈B using pigeonhole