Ad Infinitum 17

The Matchstick Experiment

\(2*n*m-n-m\) matchsticks form a grid, each of which will be removed with probability \(p\). 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

\(F(N, M)\) is multiplicative in its second argument.

Factorizing \(M\) can be done in \((O(M^{1/3}))\) time, or \(O(\pi(M^{1/3}))\) if the preprocessing time of Euler's sieve is precluded, where \(\pi(x)\) denotes the prime counting function. After removing all prime factors less or equal to \(M^{1/3}\), the prime factorization of \(M\) can only look like \(p\), \(p^2\), or \(pq\) for primes \(p\neq q\).

The Axis of Awesome

Consider some axis given by its direction vector \(h=(u,v,w)\), the squared distance between it and a point \(p=(x,y,z)\) is \(|p \times h|^2\). The sum of these squared norms, which are quadratic forms, can also be represented as \(h^T A h\) where \[ A = \sum_{i} \begin{pmatrix} y_i^2+z_i^2 & -x_iy_i & -z_ix_i \\ -x_iy_i & z_i^2+x_i^2 & -y_iz_i \\ -z_ix_i & -y_iz_i & x_i^2+y_i^2 \\ \end{pmatrix} \]

Note, \(A\) is called inertia matrix.

The real symmetric matrix \(A\) is diagonalizable by an orthogonal matrix \(Q\): \(A'=Q^T A Q\) where \(A'\) is a diagonal matrix: \[ A' = \begin{pmatrix} \lambda_0 & 0 & 0 \\ 0 & \lambda_1 & 0 \\ 0 & 0 & \lambda_2 \\ \end{pmatrix} = \sum_i{\begin{pmatrix} {y'}_i^2+{z'}_i^2 & -{x'}_i{y'}_i & -{z'}_i{x'}_i \\ -{x'}_i{y'}_i & {z'}_i^2+{x'}_i^2 & -{y'}_i{z'}_i \\ -{z'}_i{x'}_i & -{y'}_i{z'}_i & {x'}_i^2+{y'}_i^2 \\ \end{pmatrix}} \]

Given an axis \(h\), we can find an axis \(h'\) satisfying \(h=Qh'\). The squared distance can be represented as \(h^T A h = h'^T A' h'\). The condition \(\forall g,h: |g|=|h|=1 \implies g^TAg=h^TAh\) can be restated as \(\forall g',h': |g'|=|h'|=1 \implies g'^TA'g'=h'^TA'h'\). If \(\lambda_0=\lambda_1=\lambda_2\), the answer will be 0.

\[ \begin{cases} \lambda_0 & = & \sum_i({y'}_i^2+{z'}_i^2) \\ \lambda_1 & = & \sum_i({z'}_i^2+{x'}_i^2) \\ \lambda_2 & = & \sum_i({x'}_i^2+{y'}_i^2) \\ \end{cases}\Leftrightarrow \begin{cases} s_0 & = & 2\sum_i{x'}_k^2 & = & \sum\lambda_j-2\lambda_0\\ s_1 & = & 2\sum_i{y'}_k^2 & = & \sum\lambda_j-2\lambda_1\\ s_2 & = & 2\sum_i{z'}_k^2 & = & \sum\lambda_j-2\lambda_2\\ \end{cases} \]

Without loss of generality, assume \(\lambda_0\leq \lambda_1\leq \lambda_2\).

• \(\lambda_0=\lambda_1<\lambda_2 \iff s_0=s_1>s_2\). Add a \((0,0,z)\). So the answer is 1.
• \(\lambda_0<\lambda_1\leq\lambda_2 \iff s_0>s_1\geq s_2\). It is impossible to raise both \(s_1\) and \(s_2\) with one point \((x,y,z)\) because \(yz\) will be positive, thus \(A'\) will not be diagonal. Add a \((0,y,0)\) to convert to the \(\\lambda_0=\lambda_1<\lambda_2\) case, then add another. So the answer is 2.

The answer is \(3-m\) where \(m\) is the multiplicity of the smallest root of the characteristic polynomial \(f(\lambda)=det(\lambda I-A)=a\lambda^3+b\lambda^2+c\lambda+d\). Its derivative is \(f'(\lambda)=3a\lambda^2+2b\lambda+c\).

• \(m=3\) iff \(f'(\lambda)\) has a double root, that is, its discriminant equals to 0.
• \(m=2\) iff \(f(\lambda)=(\lambda-e)^2(\lambda-f)\) and \(e<f\). \(f'(\lambda)=(\lambda-e)(3\lambda-e-2f)\). \(e\) is also the smaller root of \(f'(\lambda)=0\). The converse also holds. So we can take the smaller root of \(f'(\lambda)=0\) and see if it is also the root of \(f(\lambda)\). If it is, \(f(\lambda)\) must have a multiplicity of at least 2 at the smaller root. Because we know \(m\neq 3\), it must be 2.
• \(m=1\) iff \(m\neq 3\) and \(m\neq 2\).

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.