Finite Playground

To verify is human; to prove, divine.


Leave a comment

Cute calculus puzzle

Let

f(x) = \mathrm{arctan}(x) + \mathrm{arctan}(1/x).

What is \frac{d}{dx}f(x)?  What does it say about f(x)?  Try to calculate some values of f(x) and explain.

Advertisements


Leave a comment

A few interesting open problems


Leave a comment

Zero-sum subsets

這個有趣的(小)問題是在 MathOverflow 上看到的。

假設我們有一個有限集合S=\{a_1, \ldots, a_n\}為某個群 (如自然數) 的子集, 滿足底下條件:

任何S中的元素都可以寫成另外兩個S中元素的和;也就是說令S+S = \{a_i+a_j \mid a_i,a_j \in S\},則S \subseteq S+S

試證明:S中存在一個非空子集Z使得Z中所有元素相加為零。

我們稱這樣的子集Z零和子集 (zero-sum subset)。

零和字集在加性組合學 (additive combinatorics) 中是個被廣泛研究的主題;例如在一個群G當中,若任意給定d個元素形成的集合其中都有零和子集,滿足這樣條件最小的d,我們稱作 restricted Davenport number\hat D(G)。在 Szemeredi 的 “On a conjecture of Erdos and Heilbronn” 中,他證明了

\hat D(G) = O(\sqrt{n}),

其中nG的大小。

但是由所謂 sum-full (也就是S \subseteq S+S) 這樣的條件而保證零和子集的存在性,在文獻中卻是沒有看過… 似乎是個很有趣的問題!目前為止只能想到一些標準化為圖論問題的方法,反證了幾個過於樂觀的猜想,卻沒有進一步的結果… 也許需要一些其他的工具來證明。有沒有什麼想法呢?


2 Comments

IMO 2009 Q6

從 Terence Tao 陶哲軒的 blog “What’s New” 上看到的,
花了大約一個小時找對了解題的方向, 就沒有再做下去了,
設計的很精良的題目, 有興趣可以試試看!

A = \{a_1, \ldots, a_n\} 皆為相異正整數, 令 M = \{m_1, \ldots, m_{n-1}\} 為正整數, 但其中不包含 s = \sum_i a_i. 有一隻蚱蜢, 從數線原點開始往右跳 n 步, 步伐長正好是 A 的某種排序.

請證明聰明的蚱蜢可以找出一種 A 的排序使得牠跳的每一步都不會落在 M 中的任一點上.


Leave a comment

Guessing numbers with wrong answers

在 Math Overflow 上看到的有趣問題!
假設給定平常常見的猜數字遊戲:
在 1~1000 當中選擇一個數字, 請問最少要多少次可以猜出來?
有經驗的玩家一定知道切半法是最好的答案, 因此是 10 次.

這是, 若我們假設回答問題的人會有一次的機會回答錯誤,
請問這時猜的人最少要多少次才能猜對?