## 2008年12月24日 星期三

### Fifteen Consecutive "9"s

I read a book today, and I found one interesting problem.

There are a lot of integers which consist of one "1", two "2"s, three "3"s, ... , eight "8"s and nine "9"s. If you sum all these 45-digit integers up, there are fifteen consecutive "9"s in the answer.

There is no coincidence. Can you explain why?

(Hint: To explain this phenomenon, you need only shallow knowledge in combinatorics and number theory.)

## 2008年12月21日 星期日

### 估中有獎

(e.g. 估中的話在 MD Academic seminar 中有優先座位選擇權 ^^)

---------------------------------------------------------------------------------------------

Construct a strictly increasing function f(x) from the real line to the open interval (0, 1).
For example, f(x) can be

or (the latter is the cumulative distribution of a normal random variable), etc. Can you create another example for f(x)?

The strategy is simple:

If the number you picked is x, guess that it is larger with probability f(x).

Here' s how you can do it "practically": After you see the number, say x, create a coin which has probability f(x) to show up head and 1-f(x) to show up tail, and then flip it. Then you guess "x is bigger" if head shows up, and guess "x is smaller" if tail shows up.

Suppose the number I wrote are a and b, where a < b, then the probability that you guess correctly is

which is bigger than 1/2 as f(b)>f(a). ( Verify the formula above!)

The interesting thing in the above strategy is:
Even if you look at the number x, you do not know whether you'll guess "larger" or "smaller" until you've flipped the coin. This is a so called "Probabilistic Strategy".

p.s. 此問題與 MD Academic seminar 無關，如有雷同，實屬巧合。

## 2008年12月17日 星期三

### 世界紀錄

(1) 為何 400 米的世界紀錄大於 100 米的世界紀錄的 4 倍？

(2) 為何 200 米的世界紀錄小於 100 米的世界紀錄的 2 倍？

(3) 為何 4 x 100 米接力的世界紀錄小於 400 米的世界紀錄？

(4) 為何 4 x 100 米接力的世界紀錄小於 100 米的世界紀錄的 4 倍

(5) 為何 4 x 400 米接力的世界紀錄大於 400 米的世界紀錄的 4 倍

• 在跑步機上不用轉彎，從而省下不少力量
• 在跑步機上，身體的重心不用向前移，省下不少力量
• 跑步機一般置於室內，沒有風阻

## 2008年12月14日 星期日

============================================================

Topic: How "randomness" exists in our world

Abstract:
We will see what "randomness" is from a philosophical angle with some examples in mathematics, physics, computer science, psychology and finance, and hopefully we can get some idea to answer the hard problem "does randomness really exist in our world?". After that, we will focus on the use of probability theory in computer science for random variate generation.

## 2008年12月6日 星期六

### 「係咪小兒科」裏的數學題

今天翡翠台的遊戲節目《係咪小兒科》 (《Are you smarter than a fifth grader?》的香港版本）出現了以下的數學題：

「在數列 A、9、BCDE、7 裏，任何三個連續項之和皆為 19，求 A + B + C + D 的值。」

乍看題目，不少人會立即以聯立線性方程組 (simultaneous linear equation system) 求得各未知數的值，從而求得 A + B + C + D 的值。可是這種原始的解題方法既費時，又破壞了題目的對稱美。我們只要稍加思索，便會發現題目很容易。

題中的條件表示 B + C + D = 19。因此我們只需求得 A 的值，再加上 19 便是答案。怎樣迅速求得 A 的值呢？我們得再巧妙地應用條件。考慮任意連續四項。因為左邊的三項和右邊的三項之和相同（它們皆為 19，但這值不重要），所以最左邊的項和最右邊的項相等。以題中的數列作例子，我們考慮 CDE、7 連續四項，可發現因 C + D + E = D + E + 7，消去等式兩邊的 DE 後可知 C = 7。同理可知 A = C，因此 A 的值也是 7。換言之，A + B + C + D = 7 + 19 = 26。

注意上述的推論沒用過數列第 2 項的值 9。事實上，無論第 2 項的 9 換成甚麼值，題目的答案也不會改變。假如希望將這道題改難一點，可以將這項換成未知數 X。替換後，聯立方程組便沒有唯一解，直接求得各未知數的人可能因此卻步，而看不見答案與 X 無關。

### A Solution to the "Ten-Minute" Problem

It should be easy to observe that z must be odd. We are looking for positive integer solution to

$4024x+4178y=3757057-4609z$

By manually doing division algorithm once, you can show that $gcd(4024,4178)=2$. Simultaneously, you can find a particular integer solution to $4024x'+4178y'=2$, which is

$x'=-624$
$y'=601$

Now, set $2a=3757057-4609z$ Then we have

$x =-624a-2089K$
$y =601a+2012K$

as general solution. To keep x and y both positive, we may have a "sense" that when $-624a(\mod 2089)$ is small, we can adjust K to keep x small but positive, and hence "allow room" for y to be positive.

Take $z=1$, we have $a=1876224$. However, $-624a\equiv 1651(\mod 2089)$. The remainder 1651 is too large to be x.

Now observe that when z is increased by 2, a drops by 4609. Notice $-624\times 4609\equiv 537(\mod 2089)$. That means when we increase z by 2, $-624a(\mod 2089)$ drops by 537.

Increase z from 1 to 7, $-624a(\mod 2089)$ drops from 1651 to $1651-3\times 537=40$. Setting $x=40$, we get $y=853$. A possible solution is given by

$x = 40$
$y = 853$
$z = 7$

## 2008年11月27日 星期四

### Solve it in ten minutes!

My friend heard a problem from his friend:

Find a positive integer solution to 4024x + 4178y + 4609z = 3757057.

Yes, this is a not-so-interesting question if you have a computer and you know how to write a programme (just do some brute-force calculation).

Also, if you requires an integer solution (so you may have non-positive integers as x, y or z), it is still easy to do it by hand quickly. (Do you know how?)

However, assume what you have is a sheet of paper and a pen, can you find a positive solution in ten minutes?

## 2008年11月16日 星期日

### Analytic function on a disk

Suppose f is a holomorphic function on the unit disk that is continuous up to the boundary. If f vanishes on an arc of the boundary circle, show that it is identically zero.

This is a standard question from complex analysis. I just learn today that there is a really cute solution to it. You may want to think about it before continuing.

The classical method is to use Schwartz reflection principle and argue that you can analytically continue the function outside the disk a little bit; then the continued function vanishes on a segment, so it must vanish identically.

The cute solution that I was referring to is the following: take (finitely many) copies of f, rotate each of them suitably and multiply the rotated functions altogether. Then the product is going to vanish identically on the boundary of the unit disk, and of course the product is holomorphic inside the disk. Hence the product is identically zero, and thus f is identically zero. (Just argue that all derivatives of f vanishes at the origin by differentiating the product.)

## 2008年11月13日 星期四

### Factorial

Today I went to a talk by Manjul Bhargava, and he stated some interesting facts in number theory that has to do with the factorial:

1. If $a_0,a_1,\dots,a_n$ are integers, then $\prod_{i is a multiple of $0!1!...n!$.

2. Suppose that f is a primitive polynomial with integer coefficients and let k be its degree. Let Let d(f) be the gcd of all f(a) as a runs through all the integers. Then d(f) divides k!.

3. The number of polynomial maps $f:\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z}$ is $\prod_{k=0}^{\infty}\frac{n}{\gcd(n,k!)}$.

4. A function $f:\mathbb{Z}_p\to\mathbb{Q}_p$ is continuous if and only if it has the form $f(x)=\sum_{n=0}^{\infty}\frac{c_n}{n!}x(x-1)\dots(x-n+1)$ where $c_n\to 0$ as $n \to \infty$.

In fact in the talk he gave a far reaching generalization of the factorial functions. For each compact subset of the p-adic rationals (e.g. the p-adic integers), he defined a factorial function adapted to that set such that the above seemingly unrelated facts about the factorial goes through. It's amazing to see how he could generalize things that are so well known, and give non-trivial results that fits in so many settings.

[I just realize that his original article can be found here.]

## 2008年10月26日 星期日

### The interplay of group and topological structures

One of the permeating themes in mathematics is the study of structures. When we study a mathematical object, we hope to find out something nice about it. The more structures it possesses, the nicer it mathematically is, and the more relationships to other mathematical objects it can spawn.

In this article we would like to discuss two important structures in mathematics--group structure and topological structure--and how they interact. For the definitions of groups and topological spaces, see here and here.

There are abundant examples of topological spaces which at the same time are group themselves. For instance, $\mathbb{R}$ is a group with respect to addition, and a topological space, with open sets generated by open intervals. We say that the group structure is compatible with the topological structure of $X$ if left multiplication, right multiplication by any element, and taking inverse are continuous maps on $X$. So addition in $\mathbb{R}$ is compatible with its standard topology. This definition is crucial in our discussion for the following two reasons. First, it ties the two structures together. Second, it excludes examples of topological spaces with pathological group structures which would be uninteresting. Consider $\mathbb{S}^2$ with its group multiplication defined by
$x\cdot y=f^{-1}(f(x)+f(y))$
where $f:\mathbb{S}^2\to\mathbb{R}$ is any set-theoretic bijection. We know that $f$ can be extremely sporadic.

Now here comes the question: given a topological space, does there always exist a compatible group structure?

Let's get our hands dirty by working out some concrete examples. We want to see if there is any compatible group structure in $(-1,1)$. If you are reading this article carefully enough, you may notice that the previous discussion gives a hint to construct a suitable multiplication in $(-1,1)$. Simply observe that
$\tan\left(\frac{\pi}{2}\cdot\right): (-1, 1)\to\mathbb{R}$
is a homeomorphism and so it is natural to define, for $x,y\in(-1, 1)$
$x\cdot y=\frac{2}{\pi}\tan^{-1}\left(\tan\frac{\pi x}{2}+\tan\frac{\pi y}{2}\right)$
It can be easily verified that it indeed is a compatible group structure. The above construction gives a recipe to define a compatible group structure to any topological space which is homeomorphic to another known to have a compatible group structure.

Now we modify the topological space a little bit and consider $[-1, 1]$, the closure of $(-1, 1)$. It turns out that the addition of two endpoints not only alters the topology, but also makes the new space void of any compatible group structure. The reader is encouraged to prove this fact and we will discuss it in the sequel.
The above example has told us that in order for topological spaces to have compatible group structures, some topological assumptions need to be imposed.

What if the topological space is a circle $\mathbb{S}^1$? An open disk $\mathbb{D}=\{x\in\mathbb{R}^2| \|x\|<1\}$? A cylinder $\mathbb{S}^1\times[-1, 1]$?