Transcript ppt - HKOI

Mathematics in OI
Prepared by Ivan Li
Modified by LMH
Mathematics in OI
A brief content
• Euler Phi function
• Fibonacci Sequence and
Recurrence
• Twelvefold ways
• Combinations and Lucas
Theorem
• Catalan Numbers
• Josephus Problem
Euler Phi Function
• (n) = number of integers in
1...n that are relatively prime to
n
• (p) = p-1
• (pn) = (p-1)pn-1 = pn(1-1/p)
• Multiplicative property:
(mn)=(m)(n) for (m,n)=1
• (n) = np|n(1-1/p)
Euler Phi Function
• Euler Theorem
• a(n)  1 (mod n) for (a, n) = 1
• Then we can find modular
inverse
• aa(n)-1  1 (mod n)
• a-1  a(n)-1
Fibonacci Number
•
•
•
•
F0 = 0, F1 = 1
Fn = Fn-1 + Fn-2 for n > 1
The number of rabbits
The number of ways to go
upstairs
• How to calculate Fn?
What any half-wit can do
• F0 = 0; F1 = 1;
for i = 2 . . . n
Fi = Fi-1 + Fi-2;
return Fn;
• Time Complexity: O(n)
• Memory Complexity: O(n)
What a normal person
would do
• a = 0; b = 1;
for i = 2 . . . N
t = b;
b += a;
a = t;
return b;
• Time Complexity: O(n)
• Memory Complexity: O(1)
What a Math student
would do
• Generating Function
• G(x) = F0 + F1 x + F2 x2 +. . .
• A generating function uniquely
determines a sequence (if it
exists)
• Fn = 1/(n!) dnG(x)/dxn (0)
• A powerful (but tedious) tool in
solving recurrence
All the tedious works
G(x)
= F0 + F1 x + F2 x2 + F3 x3 +. . .
xG(x)
=
F0 x + F1 x2 + F2 x3 +. . .
x2G(x)
=
F0 x2 + F1 x3 +. . .
G(x) - xG(x) - x2G(x) = F0 +F1 x - F0 x = x
G(x) = x / (1 - x - x2)
Let a = (-1 - sqrt(5)) / 2, b = (-1 + sqrt(5)) / 2By Partial Fraction:
G(x) = A / (a – x) + B / (b – x)
Solve A, B by sub x = 0, x = 1 and form two equations
G(x) = ((5 + sqrt(5)) / 10) / (a-x)+((5 - sqrt(5)) / 10) / (b-x)
= -(sqrt(5) / 5) / (1- x/a) + (sqrt(5) / 5) / (1- x/b)
• Note that 1 + rx + r2x2 +. . . = 1 / (1 - rx)
G(x) = (sqrt(5) / 5)(-1-x/a-x2/a2-...+1+x/b+x2/b2+...)
• By Uniqueness, Fn = Coefficient of x^k =
• (sqrt(5) / 5)(-1/an + 1/bn)
•
•
•
•
•
•
•
•
Shortcut
•
•
•
•
Characteristic Equation
Fn - Fn-1 - Fn-2 = 0
f(x) = x2 – x – 1
Then Fn = Aan + Bbn
for some constants A, B
where a, b are roots of f(x)
However
• How to compute ((-1-sqrt(5))/2)n ?
• The result must be a whole
number, but the intermediate
values may not
• Use floating point numbers
• Precision problem?
• If we are asked to find Fn mod m?
What a programmer
would do
• Note that
( )( ) = ( )
0 1
1 1
• Then
(
0 1
1 1
Fn
Fn+1
Fn+1
Fn+2
F
n
)(
0
F1
)=( )
Fn
Fn+1
• Matrix Exponential
Just like fast exponential
Twelvefold ways
• Put n balls into m boxes
• How many ways?
•
•
•
•
Balls identical / distinct?
Boxes identical / distinct?
Allow empty boxes?
Allow two balls in one boxes?
Twelvefold ways
Combinations
• The number of ways to choose r
objects among n different
objects (without order)
• nCr = n!/r!(n-r)!
Combinations
•
•
•
•
How to calculate nCr?
Calculate n!, r!, (n-r)! ?
Note nCr = n(n-1)...(n-r+1)/r!
nCr = 1;
for i = n-r+1 . . . n nCr *= i;
for i = 1 . . . r nCr /= i;
Combinations
• Overflow problem?
• Note nCr = (n/r)(n-1)C(r-1)
• nCr = 1; //that is (n-r)C0
for i = 1 . . . r
nCr *= (n - r + i);
nCr /= i;
Combinations
• What if we are asked to find
nCr mod p for very large n, r?
• Lucas Theorem
• Let n = pk nk + pk-1 nk-1...+ p n1 + n0
r = pk rk + pk-1 rk-1...+ r n1 + n0 Then
nCr  (nkCrk)(nk-1Crk-1)...(n0Cr0) (mod p)
• Works only for prime p
• What if p is large such that storing
intermediate nCr wouldn’t be possible?
Combinations
• When p is large (larger than r),
computing niCri may be difficult
• (nCr)(r!) = n(n-1)...(n-r+1)
• nCrn(n-1)...(n-r+1)(r!)-1 (mod p)
where (r!)((r!)-1)  1 (mod p)
• Fermat Little Theorem gives
(r!)-1  (r!)p-2 (mod p)
• Turning division in mod  into
multiplication !
Combinations
• When we are asked to mod a
square-free number, factorize it
into primes
• The situation becomes
complicated when the number
is not square-free
• Store the prime factorization of
numerator and denominator
A drunken man
• A drunken man was standing
beside a wall. On each second
he moves left or right by 1m at
random.
• What is the probability that he
returns to the original position in
k seconds without hitting the
wall?
Observations
• If k is odd, then it is impossible
Let k = 2n
• If the man returns to original
position, then there are n left and
n right moves
• Number of possible outcomes
= 22n
• We have to find the number of
moving sequence such that the
man returns to original position
without hitting the wall
Observations
• If the wall is removed, the
number of ways is 2n C n
• Let An be the number of ways
• If the first time the man returns
to his original position is at the
2ith second
• Note that the first move must be
rightward, and the 2ith move must
be leftward
Observations
• From 2 to 2i – 1 second, he cannot
return to original position due to
definition of 2i
• In 2 and 2i – 1 second, he must be
standing on 1m on the right of original
position
• Problem in this time interval reduced
to a sub-problem with 2i – 2 total
moves
• Think of an invisible wall on his original
position
Observations
• Ai-1 ways for the first 2i seconds
• An-i ways for the remaining 2n-2i
seconds (may return to original
position again)
• An = i = 1...nAi-1An-i
Tedious works again
• Again, generating function
• g(x) = n=0,1,... Anxn
• g(x)2 = n=0,1,...i=0...n Ai An-i xn
= n=0,1,...An+1xn
• g(x) = A0+ xn=1,... Anxn-1
= 1 + xg(x)2
• xg(x) = (1-sqrt(1-4x))/2 or
(1+sqrt(1-4x))/2 (rejected since
xg(x)=0 when x = 0)
• Power series......
A much more elegant
approach
• We now remove the wall and note
when the man arrives at the
position 1m on the left of the
original position (If the man never
arrives at it, he won’t hit the wall)
• When he arrives at the considered
position on the first time, flip his
remaining moves, i.e. left to right,
right to left
• He will now end at the position 2m
on the left of the original position
A much more elegant
approach
• Wall removed: 2n C n ways
• End at 2m on the left of original
position: 2n C n-1 ways
• Therefore the number of ways
that the man never arrives at
the considered position is
(2nCn) – (2nCn-1)
= (2nCn)/(n+1)
• This is called Catalan Number
Applications of Catalan
Numbers
• The number of valid string
consisting of n pairs of
parenthesis
()()(), (())(), ()(()), (()()), ((()))
• The number of binary trees with
n nodes
• The number of monotonic
paths along the edges of a grid
with n × n square cells
An evil game
• N people in a circle
• Labelled from 1 to n
• Kill the k-th person, skip the
next k-1 people, then kill the
next, etc.
• Josephus Problem
N = 8, k = 2
8
7
1
6
2
3
5
4
N = 8, k = 2
8
7
1
6
2
3
5
4
N = 8, k = 2
8
7
1
6
2
3
5
4
N = 8, k = 2
8
7
1
6
2
3
5
4
N = 8, k = 2
8
7
1
6
2
3
5
4
N = 8, k = 2
8
7
1
6
2
3
5
4
N = 8, k = 2
8
7
1
6
2
3
5
4
N = 8, k = 2
8
7
1
6
2
3
5
4
Josephus problem
• Closed form for k = 2
Josephus problem
• Naive simulation
• O(nk)
• With little technique in handling
the index
• O(n)
• f(n, k) = (f(n-1, k) + k-1) mod n + 1
• f(1, k) = 1
• Confused about the new index?
New indexing
• f(8, 2) = (f(7, 2) + 1) mod 8 + 1
• 7 in f(7, 2) circle -> 1
8
• 1 in f(7, 2) circle -> 3 7
7
1
6
2
3
5
4
1
Josephus problem
• With some more little technique
in handling the index
• O(k log n)
Question?