當前位置:才華齋>範例>校園>

經典的排列與組合國小數學奧數題及答案

校園 閱讀(3.02W)

問題:小明所在的班級要選出4名中隊長,要求每位同學在選票上寫上名字,也可以寫自己的名字。結果全班的每位同學都在自己的選票上寫了4個互不相同的名字。當小明把同學們的選票收集後發現一個有趣的現象:就是任意取出2張選票,一定有且只有一個人的名字同時出現在2張選票上。請問:小明所在的班級共有多少人?

經典的排列與組合國小數學奧數題及答案

總體邏輯思路:首先,假設題目所說的情況存在。然後,得出班級人數。最後,構造出一個例子,說明確實存在這種情況。

我們先來證明這個班每個人都恰好都被選了4次。

思路簡介:我們首先用反證法證明沒有人被選了4次以上。由於平均每人被選了4次,既然沒有人被選了4次以上,肯定也不存在被選了4次以下的人。所以,可以得到每個人恰好被選了4次。

首先證明沒有人被選了4次以上,我們用反證法。

假設有一個人被選了4次以上(由於很容易證明這個班的人數肯定不少於7人,所以我們可以假設有一個人被選了4次以上),我們設這個人為A同學。接下來我們來證明這種情況不存在。

把所有選擇A同學的.選票集中到一起,有5張或5張以上。方便起見,我們把這些選票編號,記為A1選票,A2選票,A3選票,A4選票,A5選票,…。意思就是選擇A同學的第1張選票,選擇A同學的第2張選票,…。

這些選票都選擇了A同學。由於任意2張選票有且只有1個人相同,所以這些選票上除了A同學外,其他都是不同的人。

我們還可以證明,這些並不是全部的選票,不是太難,就不證明了。

既然這些(所有選A同學的選票)不是全部的選票,我們再拿一張沒有選擇A同學的選票。方便起見,稱之為B選票。

根據任意2張選票有且只有1個人相同,A1選票上必有一個人和B選票上的一個人是相同的,而且這個人不是A同學。

同樣道理,第A2、A3、A4、A5、…上也必有一個人和B選票上的一個人是相同的,而且這個人不是A同學。

由於B選票上只有4個不同的人,而A1、A2、…,的數量大於4.所以,A1、A2、A3、…選票中至少有2張選票,除了A同學外還有一個共同的候選人。根據任意2張選票有且只有1個人相同,我們知道這是不可以的。

所以,沒有人被選了4次以上。

由於平均每人被選4次,既然沒有人被選4次以上,當然也就不可能有人被選4次以下。

所以,每個人恰好被選了4次!