Ad Infinitum 17

The Matchstick Experiment

matchsticks form a grid, each of which will be removed with probability . Calculate the expected number of connected components which consists of 3 or less connected cells.

The answer can be decomposed into a sum of multiple random variables, each of which is represented as the probability that a specific shape appears in some position. Then apply linearity of expectation to get the answer.

Number of M-Coprime Arrays

is multiplicative in its second argument.

Factorizing can be done in time, or if the preprocessing time of Euler's sieve is precluded, where denotes the prime counting function. After removing all prime factors less or equal to , the prime factorization of can only look like , , or for primes .

The Axis of Awesome

Consider some axis given by its direction vector , the squared distance between it and a point is . The sum of these squared norms, which are quadratic forms, can also be represented as where

Note, is called inertia matrix.

The real symmetric matrix is diagonalizable by an orthogonal matrix : where is a diagonal matrix:

Given an axis , we can find an axis satisfying . The squared distance can be represented as . The condition can be restated as . If , the answer will be 0.

Without loss of generality, assume .

  • . Add a . So the answer is 1.
  • . It is impossible to raise both and with one point because will be positive, thus will not be diagonal. Add a to convert to the case, then add another. So the answer is 2.

The answer is where is the multiplicity of the smallest root of the characteristic polynomial . Its derivative is .

  • iff has a double root, that is, its discriminant equals to 0.
  • iff and . . is also the smaller root of . The converse also holds. So we can take the smaller root of and see if it is also the root of . If it is, must have a multiplicity of at least 2 at the smaller root. Because we know , it must be 2.
  • iff and .

Painting Figures

Calculate the area of the union of some rectangles and circles.

Sweep line algorithm

Green's theorem

By Green's theorem, the area of a region enclosed by a smooth and closed curve can be calculated by a line integral. To use Green's theorem, we need to find the boundary of the region, which is a set of arcs (circles splitted by circles or rectangles) and segments (rectangles splitted by circles or rectangles).

Keep an eye on which lines to calculate because line integrals are very sensitive to degeneracies. I make numerical perturbation to the position of points which allows me to ignore special cases.