Category Archives: 無數不學

92年國安局三等考數理組初等數論(一)

Posted by —

2

題目：設 p 是質數，a, b 是整數，如果 \displaystyle\frac{a^p-b^p}{p} 是整數，證明 \displaystyle\frac{a^p-b^p}{p^2} 也是整數。

解答：Suppose we have know the following lemma

If p is prime, then { p \choose k} is divisible by p if and only if nonnegative integer k\neq 0, p

For convenience, let \displaystyle\frac{a^p-b^p}{p} = n and a = b+c , where c is also an integer.

Then we can rewrite n as

\displaystyle\frac{(b+c)^p-b^p}{p} = \frac{\sum_{k=1}^{p-1}{ p \choose k}c^{k}b^{p-k} + c^p}{p}

Since n is an integer, then c^p is divisible by p.

Thus c is also divisible by p , since p is prime.

Then { p \choose k}c^{k}b^{p-k} is divisible by p^2, \forall 1\leq k < p

and c^p is also divisible by p^2 since p \geq 2.

Hence n is divisible by p, that means \displaystyle\frac{a^p-b^p}{p^2} is an integer

互斥與獨立的概念

Posted by —

0

這是今天看到的一題

Suppose A and B are two events with P(A) = 0.5, P(A\bigcup B)=0.8
  1. For what value of P(B) would A and B be mutually exclusive?
  2. For what value of P(B) would A and B be independent?

解法很簡單，只要觀念清楚並且始用P(A\bigcup B) = P(A)+P(B)-P(A\bigcap B) 就可以了！

  1. A and B are mutually exclusive 是指 A and B 兩個王不見王，也因此 P(A\bigcap B) = 0 ,所以 P(A\bigcup B) = P(A)+P(B) 。因此帶入公式得到 P(B) =0.8-0.5=0.3
  2. A and B are independent 是指 A and B 兩個是陌生人，所以彼此不影響。 所以 P(A\bigcap B) = P(A)P(B) ,也就是說 P(A\bigcup B) = P(A)+P(B)-P(A)P(B) ,因此 0.8=0.5+P(B) -0.5P(B) ,所以 P(B) =0.6

有意思的鴿籠定理一題

Posted by —

0

這題是在 PTT 的 math 版看到

把自然數 1,2,3,4,5,….,10 任意排程一個圓圈，證明:一定存在 3 個相鄰的數，它們的和大於17。

我一開始的想法跟大部分人一樣：假設任 3 個相鄰的數的和都 ≦16, 那麼把 10 組這種 3 個相鄰數的和相加會得到 ≦160 的整數。然而實際的情況是 1~10 這 10 個數字每個都會被算 3 次.因此和應該是 (1+…+10)*3=165，矛盾。

不過問題在於「大於17 = 大於等於18」，所以上面是錯的。而 mgtsai.bbs@ptt.cc 提出了他的證法，不過很長就是了。而隔了幾天，我打算趁搭高鐵時想想有沒有簡單的解法，結果車還沒來我就想到了。 XD 但是回到高雄卻發現這方法前一天就被 Sfly.bbs@ptt.cc 想到了。 :(

方法如下：

Suppose the numbers are ordered by 1,a,b,c,d,e,f,g,h,i, 1,.. consider s=a+b+c, t=d+e+f, u=g+h+i, But s+t+u = 55 – 1= 54, one of s,t,u must be >= 54/3=18.