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月23日 星期二

簡單複雜化

今天母校的奧數訓練班,有幾個學生在想一條題目:

若 1#2 = 44,3#4 = 36,12#10 = 6,5#7 = 26,4#9 = 24,求6#8。

過了一段時間,我跟他們說「提示」:

若將每一條等式的三個數字考慮為三維空間的x-座標、y-座標和z-座標,如(1,2,44)、(12,10,6),則這五點都在同一個平面。

他們以為我胡說八道(因為我經常胡說八道……),沒理我,繼續自己想。

但朋友們,你們知道我是正確的,對嗎?

2008年12月21日 星期日

估中有獎

我在兩張卡片上分別寫下兩個不同的實數 (Real Number)然後你選其中一張,我讓你看看你選的卡片上面的數字。現在,你估另一張卡片上的數字是較大還是較小?

試想出一個策略,使得無論我寫下那兩個實數,你估中的機會都大於 1/2。

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

驟眼看,也許你會想:(車!) 我怎樣估也只得 1/2 機會估中。此策略沒理由存在!


但我告訴你,它是存在的! 看答案前再想一想吧。

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

其中一個策略如下

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".

若你想知多一點有關概率的問題,萬勿錯過 12 月 28 日(星期日)的 MD Academic seminar !


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

2008年12月17日 星期三

世界紀錄

以下列出部分賽跑項目的世界紀錄(可參考國際田聯網頁):

男子 100 米:     9.69 秒
男子 200 米:     19.30 秒
男子 400 米:     43.18 秒
男子 4 x 100 米接力:  37.10 秒
男子 4 x 400 米接力:  2 分 54.29 秒

看著這些數字,可以問一些有趣的問題:

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

這個當然是因為跑 100 米的「極速」不能維持太長時間,簡單點說就是「跑得久會累」。

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

這個很有趣,原因是從起跑達至「極速」是需要數秒時間的。這個加速的過程會拖低平均速率,而這在較短途的 100 米會較為明顯。不過「跑 200 米速率高於跑 100 米」,相信只有高手才能做到,一般人跑 100 米的速率都會較跑 200 米為高(原因是一般人不能把跑 100 米的「極速」維持至 200 米)。

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

這個很簡單,因為有四人接力,所以「跑得久會累」的問題不會出現

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

其實四人所跑的距離之和是略小於 400 米的,這是因為接力棒本身長約 0.3 米。更重要的因素是負責第二、三、四棒的選手可以在接棒前加速。

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

最佳的解釋相信是因為 400 米的世界紀錄實在太快,而在同一隊中很難找到四個跑得這樣快的選手!

還有一個相關的問題,就是在跑步機上所造出的時間一般會比在田徑場上所造的快了一大截。這又有甚麼原因呢?我嘗試提出幾個:
  • 在跑步機上不用轉彎,從而省下不少力量
  • 在跑步機上,身體的重心不用向前移,省下不少力量
  • 跑步機一般置於室內,沒有風阻

2008年12月14日 星期日

MD Academic Seminar

數學資料庫將於本月底舉行 academic seminar,詳情如下:

日期:2008 年 12 月 28 日(星期日)
時間:下午 4 時 30 分至 5 時 45 分
地點:香港科技大學 2304 室(近 17、18 號升降機)
講者:張潤權先生(香港科技大學數學系研究生)
語言:粵語輔以英語

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

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



By manually doing division algorithm once, you can show that . Simultaneously, you can find a particular integer solution to , which is




Now, set Then we have




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

Take , we have . However, . The remainder 1651 is too large to be x.

Now observe that when z is increased by 2, a drops by 4609. Notice . That means when we increase z by 2, drops by 537.

Increase z from 1 to 7, drops from 1651 to . Setting , we get . A possible solution is given by



2008年12月1日 星期一

培正數學邀請賽:最新消息

數學資料庫協辦的第八屆培正數學邀請賽將於 2009 年 1 月 24 日(星期六)及 2009 年 3 月 14 日(星期六)舉行,詳情請瀏覽比賽網頁 http://www.puichingcentre.edu.hk/pcimc/

有意參賽的同學請留意,學校報名(包括輸入參賽學生資料)的截止日期為 2008 年 12 月 12 日(星期五)。如果就讀學校沒有報名參賽,則該校的同學可於 2008 年 12 月 15 日(星期一)至 2008 年 12 月 22 日(星期一)期間以個人名義報名參賽。

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月23日 星期日

三角題一則

問題:求 3 sin x + 4 cos x 的最大值。

在會考的附加數學科裏這題有以下的標準解法:設 3 sin x + 4 cos x = R sin (x+y),則 3 sin x + 4 cos x = (R cos y) sin x + (R sin y) cos x,故比較系數可知 R cos y = 3 而 R sin y = 4(這時頭腦清醒的學生應該問「為何可以比較系數?」),解方程可得 R = 5 而 y = tan-1(4/3),從而 3 sin x + 4 cos x 的最大值是 5。

最近碰到以下有趣的題解:不妨設 x 為銳角(為何可以這樣做?,再考慮下圖,易見 CE = 3 sin x 而 ED = 4 cos x。再者,不難發現 AEB 是直角而 AC // BD,故此 3 sin x + 4 cos x = CD ≦ AB = 5(等號何時成立

2008年11月19日 星期三

香港大學公開講座

日期:2008 年 12 月 6 日(星期六)
時間:下午 2 時 30 分至 4 時
地點:香港大學許磐卿講堂(LE1)
講者:吳端偉博士
講題:拍賣中尋對策

有關其他詳情及查詢電話,可瀏覽 http://147.8.101.93/math/2008dec/2008dec06.pdf

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 are integers, then is a multiple of .

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 is .

4. A function is continuous if and only if it has the form where as .

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]?