ISE 390 -- Programming Challenges -- Week 6 Notes
This Weeks Goals:
To review some of the mathematics behind the solution of the
problems on the Warm-up World Competition held last week.
To introduce this weeks problems on modular arithmetic and primality
Topic for Discussion:
Should we do the problems in groups instead of individually?
Solving the 8-puzzle
This can be done by a breadth-first search from the initial
puzzle state, with a data structure (perhaps an array of boards)
to keep track of which states we have already visited.
Number of lattice points in a polygon:
This can be computed (in a slow way) with a plane sweep (try every
possible x-value and count the number of inside points), as will
be discussed when we get to computational geometry section.
Another approach would be to use "Pick's theorem":
Let P be a lattice polygon. Assume there are I(P) lattice points in
the enterior of P, and B(P) lattice points on its boundary.
Let A(P) denote the area of A. Then A(P) = I(P) + B(P)/2 - 1
We can compute the area by first triangulating the polygon and
adding up the numbers.
Repackaging
Gaussian elimination can be used to find three rows which will
generate solutions to any set of values (are the rows independent).
Marbles
This problem is a good example of the power of modular arithmetic.
You seek to solve the following equation (in variables c1 and c2)
c1 * x1 + c2 * x2 = n
where all quantities must be integers. Solving for c1 gives
c1 = (n - c2 *x2) / x1
which can only be an integer iff n = c2*x2 (mod x1)
Solving such a congruence requires a little number theory.
If the modulus x1 is relatively prime to x2, this has exactly
one solutionl. If x2 divides x1 but not n, there is no solution.
Otherwise, we can divide the whole things by the greatest common
divisor of the three constants.
Greatest Common Divisor
The greatest common divisor can be computed by Euclid's algorithm:
The algorithm is based on the following two observations:
1.If b|a then gcd(a, b) = b.
2.If a = bt + r, for integers t and r, then gcd(a, b) = gcd(b, r).
Example
Let a = 2322, b = 654.
2322 = 654*3 + 360
gcd(2322, 654) = gcd(654, 360)
654 = 360*1 + 294
gcd(654, 360) = gcd(360, 294)
360 = 294*1 + 66
gcd(360, 294) = gcd(294, 66)
294 = 66*4 + 30
gcd(294, 66) = gcd(66, 30)
66 = 30*2 + 6
gcd(66, 30) = gcd(30, 6)
30 = 6*5
gcd(30, 6) = 6
Therefore, gcd(2322,654) = 6.
Assigned Problems:
180 -- A variation of the Josephus problem. Is modular arithmetic
appropriate? (not clear)
202 -- Compute the repeating decimal component of a rational number.
Think long division..
294 -- Count the number of divisors which an integer has, in a clever
rather than brute force manner.
324 -- What is the digit distribution of n!, for large n?
Can we do better than brute force multiplication?
374 -- Use the power of modular arithmetic for efficiency?
382 -- What is the sum of the divisors of a given integer?
What fraction goes with given repeating decimal number?
Suppose that a simple fraction a/b has a repeat R of length of l.
Then 10^l * (a/b) - (a/b) will be equal to R, and
a/b = R / (10^l - 1)
The Fundamental theorem of Arithmetic
Despite the impressive title, all it states is that each
integer can be expressed only one way as the product of
primes. This simple fact can be very useful.
Puzzle: how many divisors does an integer have (2^n, n!, 10000).
Which has the largest number? Which has the smallest number? What
about sums of divisors?
Modular arithmetic
Is (s * t) mod m == (s mod m) * (t mod m) (mod m)?
YES -- because suppose s = a*m + b and t = c*m + d.
then s*t = (a*m + b)(c*m + d) = acm^2 + (ad+bc)m + bd
so the remainder must be bd (mod m)