2: 3 Rules Flashcards
3 principles
parity
pigeon hole principle
inclusion/exclusion
parity
prove impossible by parity mismatch
odd even,
black white
(can’t prove possible only disprove)
12x+18y=2
2x+6y=11
do they have sols
12x+18y=2
has even parity but no Solutions
2x+6y=11
left hand side is even but right hand side is odd so there are no Solutions
EXAMPLE: for nxn chess board Domino’s cover without overlap if
Domino’s cover without overlap if and only if n is even.
- if n is odd then parity mismatch as each covers 2 squares and reduced #uncovered by 2. Thus #uncovered is odd and never equal to 0
- if n is even integer valued nxn/2 blacks and nxn/2 whites hence covered by nxn/2 Domino’s each covering one black and one white each
EXAMPLE: for nxn chess board Domino’s cover without overlap ..
when removing squares from two opposite corners
board cannot be covered
- even: two black squares missing hence two more white squares than black squares, #uncovered never equal to 0 as 2 White’s always uncovered.
- if n is odd require odd half of domino ie parity mismatch
EXAMPLE: 7 components,each 4 squares: 4x7 grid?
1x4 rectangle
{3 across one up} x 2 L shapes
{2 across one up one across} x 2
{2x2 square}
t shape ( 3 across then one up in middle)
impossible:
most tiles cover 2 • and 2W no matter how they’re rotated
T shape covers 3•1w or 3w1•.
altogether all shapes cover 15•13W or 15W13•
however colour party mismatch as 4 by 7 grid covers 14•14W
for a tour of all vertices
supposed set of nodes A_1,…,A_n with bridges such that #bridges attached to A_i is d_i. For a tour starting at A_p and ending at A_q Crossing each path exactly once.
consider node A_i st ≠ p or q (ie not end or start). Let K_i = #times tour passes through A_i. each time we arrive and leave and thus use 2 Bridges. Must use every Bridge d_i = 2K_i ie d_i is even for all i ≠ p or q.
so every node not at start / finish must have even #Bridges d_i.
the pigeonhole principle
placing more than n in n pigeon holes:
then some will contain more than one
EXAMPLE: handshaking between n ppl ST none shake own and no pair more than once
supposed A_1,…,A_n shake hands in some combo with d_i = # hands A_i shakes. d_i in {0,1,…,n-1}. assume all d_i different. as n choices i.e. size of set |{0,1,…,n-1}.|=n must completely fill up set. So there exists p,q such that d_p=0 and d_q=n-1. A_p shakes none, A_q everyone. but this must includeA_p, contradiction.
EXAMPLE: there are at least 2 people in the world with the same number of hairs
assume everyone less than 10 ^ 6.
divide people into groups H_0, H_1,…, H_10^6 where H_k is the set of those with k hairs. total #people is |H_0| +|H_1|+…+|H_10^6|=1+1+…+1 =10^6 if each set at most one.
but there are more than this in the world. so there exists a H_k st |H_k| bigger than 1
EXAMPLE: given any 10 different positive integers less than 100, there will be two disjoint subsets with the same sum
suppose U ⊆{1,2,…,100} with |U|=10. U has 2^10=1024 subsets (A_1,…,A_1024). let S_k be the sum of elements in A_k. S_k is that most the sum of the 10 terms which is at most 91+92+…+100= 10 (91+100)/2 = 955 buy standard arithmetic formula.
So the 1024 S_k are in the set S={0,1,…,955} which has |S| = 956 less than 1024. So S_i cannot all be different. We can find p≠q st S_p = S_q. ie A_p and A_q have the same sum.
Let Z= A_p ∩ A_q
Y=A_q \ A_p
X= A_p \ A_q
put x= sum of elements of X, Y= …of y, Z=… of z
S_p = x+ z, S_q = y+z. By assumption S_p=S_q, x+z = y+z implies x=y. X and Y are disjoint subsets of U with the same sum
EXAMPLE: show that given any sequence of n integers, x_1, x_2,…,x_n. some consecutive collection has a sum divisible by n
ie partial sums are ___mod n
“consecutive block whose sum is 0 mod n”
by considering partial sums in terms of mod n & by taking the difference between two equations we can find a consecutive block whose sum is 0 mod n.
consecutive subsequence x_p, x_{p+1},…,x_q (p≤q)
st x_p +…+x_q = 0 mod n.
put y_0=0 mod n, y_1= x_1 mod n, y_2 = x_1 + x_2 modn ,…, y_n = x_1 +…+x_q = 0 mod n. Giving (n+1) numbers y_0,…,y_n (mod n) lying in set {0,…,n-1} size n. hence they cannot all be different. we can thus find m less than q with y_m = y_q. now y_m = x_1+…+x_m mod n, y_q= x_1+…+x_m + … + x_q so y_q- y_m = x_{m+1}+…+x_q mod n.
thus take p=m+1 ≤q for x_p +…+x_q = 0 mod n
EXAMPLE: each day for 100 Days £1 or £2 deposited into bank. on 50 days at £1 other 50 £2. Let k in Z with 1 ≤k ≤50
show that over some consecutive period of days I will put a total of precisely k pounds into bank
*let x_i = amount deposited on day i, x_i in {1,2}. y_i=x_1+...+ x_i = total deposited up to and including i
y_0=0
y_100=150 as 50 are 1 and 50 are 2, so 0 ≤ y_i ≤ 150 for all i.
y_{i+1} = y_i + x_{i+1} bigger than y_i
so y's are all distinct, put Y={y_0,...,y_100}. So |Y|=101 and is subset of {1,...,150}
- Fix k such that so 1 ≤ k ≤ 50 and z_i = y_i +k, z={z_0,…,z_100} so |Z|=101 and is a subset of {k,…,150+k} subset of {0,..,199}=U. |U|=200 and |Y| +|Z| = 202 bigger than |U|. it follows that Y and Z cannot be disjoint .
- thus, z_i = y_j for some i,j. this implies that y_i + k = y_j. as sequence why is increasing we must have i Less Than j. Now x_{i+1} +…+x_j = y_j - y_i = k, so we deposit a total of k for days i+1 to j.
inclusion exclusion principle
related to number of items with at least one of properties
and
|X∪Y| = |X| + |Y| - |X∩Y|
inclusion exclusion principle theorem
suppose we have a finite set of items and properties 1,2,…,n. Let N(i_1, i_2,…,i_r) be the #items with properties i_1,…,i_r (and maybe others). Then #items with at least one of the properties is
N(1) + N(2) + N(3) +...+N(n)
- N(1,2) - N(1,3)-...-N(n-1,n)
\+N(1,2,3) + N(1,2,4)+...
-N(1,2,3,4)-...
...
\+ (-1)^{n-1}N(1,2,3,...,N)
={for (i_1, i_2,…,i_r)} Σ (-1)^{r-1}N(i_1, i_2,…,i_r)
