Funny Theorems/Conclusions

  • Shoelace formula wiki

Shoelace fomular is an efficient solution to calculate the area of a simple polygon whose vertices are described in the clockwise or counterclockwise direction.

$$
\begin{aligned}
\mathbf { Area } &= \frac { 1 } { 2 } | \sum _ { i = 1 } ^ { n - 1 } x _ { i } y _ { i + 1 } + x _ { n } y _ { 1 } - \sum _ { i = 1 } ^ { n - 1 } x _ { i + 1 } y _ { i } - x _ { 1 } y _ { n } | \\
&= \frac { 1 } { 2 } | x _ { 1 } y _ { 2 } + x _ { 2 } y _ { 3 } + \cdots + x _ { n - 1 } y _ { n } + x _ { n } y _ { 1 } - x _ { 2 } y _ { 1 } - x _ { 3 } y _ { 2 } - \cdots - x _ { n } y _ { n - 1 } - x _ { 1 } y _ { n } |
\end{aligned}
$$

This expression is extremely better than Heron’s formular especially in the aspect of precision when it comes to triangles.

Funny Problems

  • Cat and Mouse

    A game on an undirected graph with no more than 50 nodes is played by two players, Mouse and Cat, who alternate turns. At begining, Mouse and Cat are at node 1 and node 2, respectively, and Mouse moves first. There is a Hole at node 0. During each player’s turn, they must travel along one edge of the graph that meets where they are. Additionally, it is not allowed for the Cat to travel to the Hole (node 0.) Then, the game can end in 3 ways:

    • If ever the Cat occupies the same node as the Mouse, the Cat wins.
    • If ever the Mouse reaches the Hole, the Mouse wins.
    • If ever a position is repeated (ie. the players are in the same position as a previous turn, and it is the same player’s turn to move), the game is a draw.

    Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// Time Complexity: O(n^3)
const int N = 55, DRAW = 0, MOUSE = 1, CAT = 2;
class Solution {
public:
struct Node {
int u, v, turn, winner;

Node () {}
Node(int _u, int _v, int _turn, int _winner) { u = _u, v = _v, turn = _turn, winner = _winner; }
};

int degree[N][N][3], color[N][N][3], link_zero[N];

int catMouseGame(vector<vector<int>>& graph) {
int n = graph.size();
memset(color, 0, sizeof (color)); // 0: draw; 1: mouse wins; 2: cat wins
memset(degree, 0, sizeof (degree)); // the number of out-going edges
memset(link_zero, 0, sizeof (link_zero));
for (int i = 0; i < n; ++i) {
for (int j: graph[i]) if (j == 0) {
link_zero[i] = 1;
break;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
degree[i][j][1] = graph[i].size();
degree[i][j][2] = graph[j].size();
if (link_zero[j]) degree[i][j][2]--; // cat cannot travel to the Hole (node 0)
}
}

queue<Node> que;
// initialize colors
for (int i = 0; i < n; ++i) {
for (int t = 1; t <= 2; ++t) {
color[0][i][t] = MOUSE;
que.push(Node(0, i, t, MOUSE));
if (i > 0) {
color[i][i][t] = CAT;
que.push(Node(i, i, t, CAT));
}
}
}

while (!que.empty()) {
Node cur = que.front(); que.pop();
int u = cur.u, v = cur.v, turn = cur.turn, winner = cur.winner;
vector<int> parent;
if (turn == MOUSE) parent = graph[v];
else parent = graph[u];

for (int w: parent) {
Node nxt = Node(-1, -1, 3 - turn, winner);
if (turn == MOUSE) nxt.u = u, nxt.v = w;
else nxt.u = w, nxt.v = v;
if ((turn == MOUSE && nxt.v == 0) || color[nxt.u][nxt.v][nxt.turn] != DRAW) continue;
if (nxt.turn == winner) {
color[nxt.u][nxt.v][nxt.turn] = winner;
nxt.winner = winner;
que.push(nxt);
} else {
if (--degree[nxt.u][nxt.v][nxt.turn] == 0) {
color[nxt.u][nxt.v][nxt.turn] = 3 - nxt.turn;
nxt.winner = 3 - nxt.turn;
que.push(nxt);
}
}
}
}
return color[1][2][MOUSE];
}
};
  • Coupon Collector’s Problem

The Coupon Collector’s Problem can be discribed as below. You have a dice with n faces. The i-th face has i dots. It is guaranteed that when the dice is tossed, every face appears with equal probability $\frac{1}{n}$. Now the question comes: what is the expectation of times that you need to toss the dice to ensure each face appearing at least once?

Let $E(n)$ be the expectation of n faces dice. Let $t_i$ be the time to make sure $i$ different faces appearing at least once. Observe that the probability of the appearance of a new face is $p_i=\frac{n-(i-1)}{n}$. Therefore, $t_i$ has geometric distribution with expectation $\frac{1}{p_i}$. By the linearity of expectation we have:

$$
\begin{aligned}
E(n)&=E(t_1) + E(t_2) + \cdots + E(t_n) \\
&=\frac{1}{p_1}+\frac{1}{p_2}+\cdots + \frac{1}{p_n} \\
&= \frac{n}{n} + \frac{n}{n-1} + \cdots + \frac{n}{1} \\
&= n \times (\frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{n})\\
&=n\times H_n
\end{aligned}
$$
Here $H_n$is the n-the harmonic number. Using the asymptotics of the harmonic numbers, we obtain:
$$
E(n)=n\times H_n = n\log n + \gamma n + \frac{1}{2} + o(1) (n\rightarrow \infty)
$$
where $\gamma \approx 0.5772156649$ is the Euler-Mascheroni constant.