Determine whether an ellipse intersect a horizontal or vertical line

Assume an ellipse of width \(\sigma\) and length \(\kappa \sigma\) is centered at \((x_0, y_0)\), and has angle \(\theta_0\) with the \(x\)-axis. How do we determine whether it intersects a horizontal line or a vertical line?

It turns out the criteria is very simple

• The ellipse intersects a horizontal line \(y = y_1\) if and only if the following equation hods: \[ \triangle_1 = \sigma^2 \left(\cos^2(\theta_0) + \kappa^2 \sin^2(\theta_0)\right) - (y_1-y_0)^2 \geq 0 \]
• The ellipse intersects a vertical line \(x = x_1\) if and only if the following equation hods: \[ \triangle_2 = \sigma^2 \left(\sin^2(\theta_0) + \kappa^2 \cos^2(\theta_0)\right) - (x_1-x_0)^2 \geq 0 \]

Color Balls

Non-Coding Problem:
Given a bag of n balls each with a different color. Each time you pick up a pair of balls and paint both to one of their colors. What's the expected number of steps before all balls become the same color?

Analysis:
This is a problem from the "Green Cover Book". It's easy to see that we have the following transition probability.

Thus if we let \(\mu_i\) be the expected number of steps getting to one color when the bag has i distinct colors, then we have \[ \mu_i = 1 + \frac{i(i-1)}{n(n-1)} \mu_{i-1}+\left(1-\frac{i(i-1)}{n(n-1)}\right) \mu_i. \] From this we can use induction to prove that \[ \mu_i = \frac{i-1}{i} n(n-1). \] Therefore we have \[ \mu_n = (n-1)^2. \]

Another reason for linear convergence of Newton's method

It's well-known that Newton's method has quadratic convergence if the function is well-behaved and the initial guess is close to the solution. However, sometimes we only get linear (slow) convergence.

One possible reason is that the derivative f' is singular at the solution x*. Here singular means f'=0 in 1D case or f' is a singular matrix in higher dimensions. In the 1D case, we can still get quadratic convergence if we use the iteration \(\triangle x = -m f(x_n)/f'(x_n)\) with m equal to the multiplicity of the root x*.

Another possible reason is that there is a bug in the computation of the right-hand-side \(f(x_n)\). If there is a deviance of \(O(h)\), Newton's method will also converge linearly.

猴子和椰子的故事

5个人被丢到了荒岛，只有椰子可以吃。

五个人一起采摘了很多的椰子，他们决定平分， 每个人拿到1/5的椰子。

夜幕降临，大伙都去睡了~~~~~

第一个人 起来了，然后呢 他不相信其他几个人，决定先把自己那份椰子藏起来，可是他发现，把这些椰子平分为5分的话 会有一个椰子剩下，刚巧一直猴子路过，他就把那一个椰子给了猴子，然后他把自己的那份椰子藏起来了。 接着 继续去睡觉……

然后 过了一会儿第二个人醒了，他做了和第一个人一样的事情，他把剩下的那些椰子平均分为五分 还是有一个剩下， 刚巧 那猴子经过 给了猴子，

接下来的人都做了同样的举动 一直到 第五个人

【提问】一开始 最少数目的椰子有多少？？？


解答：

如果一开始加四个的话，五次都能平分。

五次都能平分的数最小是5的5次方，所以一开始最少椰子数是：5^5-4=3121

Nodes of height h in an n-element heap

This is exercise 6.3-3 of CLRS version 2.

Question:Show that there are at most \(\lceil n/2^{h+1} \rceil\) nodes of height \(h\) in any \(n\)-element heap.

Solution: First some facts

1. According to exercise 6.1-7, an \(n\)-element heap has exactly \(\lceil n/2 \rceil\) leaves.
2. Notice that the nodes with height \(i\) become leaves after deleting all the nodes with height \(0,\cdots, i-1\).

Let \(y_i\) be the total number of elements of the new tree after deleting all the nodes with height \(0,\cdots, i-1\), and let \(x_i\) be the number of leaves of the new tree. Then we have \(x_i = \lceil y_i/2 \rceil\) by fact #1 and \(y_{i+1}=y_i - x_i\) by fact #2. Thus we have \(y_{i+1} \leq y_i/2\), and this leads to
$$y_i \leq n/2^i, \quad \forall n=0,1,\cdots.$$
The final conclusion follows from the relation \(x_i = \lceil y_i/2 \rceil\).

Gift distribution problem

There are 20 person in a Christmas party. What is the probability that at least one of them get his own gift?

Solution:
Let \(A_i\)=person i get his own gift
Then we want \(P(A_1 \cup A_2 \cup \cdots \cup A_n)\),
which is equal to
$$
\sum P(A_i)-\sum P(A_i \cap A_j)
+ \sum P(A_i \cap A_j \cap A_k) - \cdots
+ (-1)^n \sum P(A_1 \cap A_2 \cap \cdots \cap A_n)
$$

The general term is
$$
C(n, k)\cdot \frac{(n-k)!}{n!} = \frac{1}{k!}
$$

Therefore the answer is
$$
1-\frac{1}{2!}+\frac{1}{3!}-\cdots+\frac{1}{20!}
$$

Puzzle: Show that cos 1°, sin 1°, and tan 1° are irrational numbers.

Let \(\theta=\)1°. Assume otherwise \(\sin(\theta)\) is rational.

Since $$\cos(2\theta)=1-2 \sin^2(\theta).$$ We know that \(\cos(2^k \theta)\) are rational.

Now

$$\cos(30\theta) = \cos(32\theta)\cos(2\theta)+\sin(32\theta)\sin(2\theta)$$

The first part \(\cos(32\theta)\cos(2\theta)\) is rational.

And we have

$$\sin(32\theta)=32sin(\theta)\cos(\theta)\cos(2\theta) \cdots \cos(16\theta)$$

and

$$\sin(2\theta)=2\sin(\theta)\cos(\theta)$$.

Thus for the second part \(\sin(32\theta)\sin(2\theta)\), we'll get a rational number times \(\cos^2(\theta)=1-\sin^2(\theta)\), which is also a rational number. Therefore the second part is also rational.

Thus we conclude that \(\cos(30\theta)=\sqrt{3}/2\) is rational, which contradicts the fact that \(\sqrt{3}\) is irrational.

To prove that \(\cos(\theta)\) is irrational, we can use the formula

$$\cos(2\theta) = 2\cos^2(\theta)-1$$

and similar arguments as above.

To prove that \(\tan(\theta)\) is irrational, we can use the formula

$$\sec^2(\theta) = \tan^2(\theta)+1$$

and similar arguments as above.

不相邻的数

1,...N中取X个两两不相邻的数，有多少种取法？

例如，1,2,3中取2个不相邻的数，只有{1,3}这1种取法。

解法1:
假设这X个不相邻的数中，第一个数之前有a个数，最后一个数之后有k-a个数。这X个不相邻的数形成了X-1个容器，每个容器中至少有一个数。这和把N-k-X个不可分辨的球分入X-1个容器，每个容器中至少有一个球的问题类似。按照前文“分球问题的总结”，这一共有C(N-k-1, X-2)种分法。当然，要使上述问题有意义，必须有N-k-X>=X-1。也就是说k最大可以取N+1-2X。k最小显然可以取0。对于每个固定的k，a可以取0,1,...,k，共(k+1)种取法。从而题目的答案是
\[\sum_{k=0}^{N+1-2X} (k+1)C(N-k-1,X-2)\]

解法2:
假设这X个数为$n_1<n_2<\cdots<n_X$。则不相邻等价于
$n_2-1>n_1$,
$n_3-1>n_2$,
...,
$n_X-1>n_{X-1}$
引入新变量$m_1=n_1$,$ m_2=n_2-1$, $m_3=n_3-2$, ..., $m_X=n_X-(X-1)$，则上述不相邻条件等价于
$m_2>m_1$,
$m_3>m_2$,
...,
$m_X>m_{X-1}$
也就是说，$m_1<m_2<\cdots<m_X$只是普通的X个从小到大的整数，不再有不相邻的限制。由于$n_X$最大可以取到N，从而$m_X$最大可以取$N+1-X$。于是$m_1,m_2,\cdots,m_X$有C(N+1-X,X)种取法。由于$m_1,m_2,\cdots,m_X$和$n_1,n_2,\cdots,n_X$有一一对应关系，从而$n_1,n_2,\cdots,n_X$也有C(N+1-X,X)种取法。

解法3:

把N个数看成N个小球。先取N-X个小球排成一排，然后把X个小球插进去。N-X个小球包括其两端一共有N-X+1个空位，所以答案是C(N-X+1, X)。

翻到4张A的次数

问题：52张牌随机放在桌上排成一排，你从第一张牌开始依次翻开。问平均多少次翻开所有4张A？

解法1：

假设第$X$步翻开第4张A，则

\[P(X=k) = C(k-1,3)/C(52,4), \qquad k=4, \cdots 52\]

从而

\[E(X) = \sum_{k=4}^{52} k C(k-1,3)/C(52,4)\]

用R写个简单小程序，可以算出$E(X)=42.4$

解法2:

4张A隔开5个位置，其他48张牌可以任选一个位置放。从而平均有48*1/5 = 9.6张牌放在4张A之后。从而第4张A平均出现在52-9.6=42.4张牌的位置。

分球问题总结

(1) n个球分入k个桶里，有多少种分法？（假设球不可分辨）

解答：把n个球排成一排，中间插k-1个挡板。这k-1个挡板隔开的k个区间对应放入相应桶的球的数目。从而答案是C(n+k-1, k-1).

(2) n个球分入k个桶里，要求每个桶至少一个球，有多少种分法？（假设球不可分辨）

解答：可以先给每个桶分配一个球，余下的n-k个球再任意分入k个桶里，这样共有C(n-k+k-1, k-1) = C(n-1, k-1)种分法。

(3) n个不同颜色的球分入k个桶里，有多少种分法？

解答：每个球有k种选择，所以答案是\(k^n\).

(4) n个不同颜色的球分入k个桶里，每个桶至少一个球，有多少种分法？

解答：

设f(n,k)为把n个不同颜色的球扔到k个桶里，每个桶至少一个球的扔法总数。由于第3题中把n个球随机分配到k个桶里，可能出现这些球分别只在\(1,2, \cdots, k\)个桶里的情况，所以我们有下面这个递推公式：

\[k^n = C(k,1)*f(n,1)+C(k,2)*f(n,2)+...+C(k,k-1)*f(n,k-1)+f(n,k)\]

当只有一个桶时，显然有f(n,1) = 1。由此根据上述递推公式可以用数学归纳法得到

\[f(n,k) = \sum_{i=0}^{k-1} (-1)^i C(k,i) (k-i)^n\]