Quod Erat Demonstrandum

2015/01/08

被 8 整除

Filed under: Fun,mathematics — johnmayhk @ 2:08 下午
Tags: , ,

1.問題

證明對於任何正整數 n

n^4+2n^3+3n^2+2n

必可被 8 整除。

2.解答

(a)

本來利用 Mathematical Induction (M.I.) 來證明是很輕易的,但現在的 M2 課程已刪除了整除性,相信中四五的同學,要解題不易。

只寫 P(k)\Rightarrow P(k+1) 這步:

(k+1)^4+2(k+1)^3+3(k+1)^2+2(k+1)

=8Q+4k^3+6k^2+4k+1+2(3k^2+3k+1)+3(2k+1)+2

=8Q+4k^3+12k^2+16k+8

=8Q+4k^2(k+1)+16k+8

由於

k(k+1) 必然是偶數,故上式變成

8Q+8M+16k+8

(其中 M,Q 是正整數)

即可被 8 整除也。

(b)

如果不想用 M.I.,又可以怎樣處理?一般都是這樣考慮的:

只要證明

n^4+2n^3+3n^2+2n=0 (mod 8)

便可。

即是把正整數分為 8 類:就是分別把它除以 8 後,餘數為 0,1,2,…,7 這 8 類。如果這 8 類整數代入

n^4+2n^3+3n^2+2n

後,都是 8 的倍數(可被 8 整除),便有

n^4+2n^3+3n^2+2n=0 (mod 8)

只要檢查 n=1,2,...,7 的情況:

johnmayhk-divisible-by8

發覺

n^4+2n^3+3n^2+2n

皆可被 8 整除,即

n^4+2n^3+3n^2+2n=0 (mod 8)

證畢。

3.源起

其實這個表達式

n^4+2n^3+3n^2+2n

有何特別?這個能被 8 整除的它,是如何被製作出來?

原來是考慮數算(counting)而來。

考慮一條珍珠手鍊,當中有 4 顆形狀大小一樣的珍珠,如果珍珠塗上顏色,而可選用的顏色有 n 種,那麼珍珠手鍊的可能組合,共有

\frac{1}{8}(n^4+2n^3+3n^2+2n)

種。

(如此,n^4+2n^3+3n^2+2n 必能被 8 整除。)

比如,可選取的顏色只有黑白兩種(即 n=2),即珍珠手鍊的可能組合有

\frac{1}{8}(2^4+2(2^3)+3(2^2)+2(2))=6

種,分別是以下情況:

johnmayhk-divisible-by8-a

如何得到

\frac{1}{8}(n^4+2n^3+3n^2+2n)

這個式子?不過是伯恩賽德引理(Burnside’s lemma),希望遲些在學校數學學會出的雜誌寫少少東西介紹一下。

johnmayhk-divisible-by8-b
(知識比珍珠,何者更美?)

4.習題

利用伯氏引理,不難得到一些類似本文提及的題目。

比如,考慮立方體填 n 色的可能組合數目,便可知

n^6+3n^4+12n^3+8n^2

可被 24 整除,見:

http://en.wikipedia.org/wiki/Burnside%27s_lemma

發表迴響 »

仍無迴響。

RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: