## 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$