2017年8月22日 星期二

訓練數學感 144 ─ 解題

http://4rdp.blogspot.com/2017/08/144.html

圖片來自博客來
有個數學競賽 21 位男生及 21 位女生參加,結果沒有人解題超過七題 (最多解六題),每一題至少有一位男生以及一位女生解出,任何一位男生與任何一個女生都至少解出一道相同的題目。
請證明:有一題至少有三位男生以及三位女生解出來。

這個題目是從四十二屆國際數學奧林匹亞競賽的題目來的,對它有興趣是因為題目很簡單易懂,但是要解題不容易。

有一天與網友約在板橋車站碰面,之後剛好路過新北市無人圖書館,隨手翻到一本數學奧林匹亞特訓班的一年,ISBN 978-957-32-6789-8,史帝夫‧奧森 (Steve Olson) 著,齊若蘭譯,遠流出版社。新北市的圖書館很方便,可以 A 館借,B 館還,不然板橋車站不是我常去的地方,根本不會想到要去那裏借書。

10 則留言:

  1. 請問有限制題數嗎?
    如果總共有21題,每題分別由一男一女回答,那這樣與要證明的敘述不符。

    回覆刪除
    回覆
    1. 題目沒有提及有多少題數,因此視為沒有限制題數,我懂你的意思,若是21題將可能不符證明條件。
      重新檢視題目,發現有改寫題目,因此刪除我寫的並加入原文,大家再重新思考吧。

      刪除
  2. 這要用到抽屜原理吧。
    試解如下:
    一、
    因沒人最多解六題,且任何一位男生與任何一個女生都至少解出一道相同的題目,
    把21位女生看作蘋果,把6道題目看作抽屜,21/6=3.5
    故有某男A,其總是會與至少3名女生解出某題目。
    二、
    同理可證有某女a,其總是會與至少3名男生解出某題目。
    三、
    綜合一與二(這部分詞句暫時沒想好)得出結論。

    回覆刪除
    回覆
    1. 老師的答題非常正確,不要小看這題目,能如此精準說明不容易。

      刪除
    2. 太厲害了!
      我動手查了一下,發現抽屜原理和鴿籠原理是一樣的東西。我初次看到是把鴿子裝進鴿籠裡。不過因為理解簡單,可能就小看它的應用了。

      刪除
  3. 加分題,如原題目但條件修改為,任何一位男生與任何一個女生都剛好解出一道相同的題目。請問考題最多有幾題?

    回覆刪除
    回覆
    1. 無窮大……
      因爲可以有些題目沒有人答對,這點沒有被限制。

      刪除
    2. 確實,加分題漏了這個條件,如果每題都有男生女生答對呢?請問最多有多少考題?

      刪除
    3. 6 x 6 = 36
      建立一個直角坐標系,把男生分為若干組,每組編號記作橫軸的整數點,
      把女生分為若干組,每組編號記作縱軸的整數點。
      如下圖:
      女生組
      7-x-x-x-x-x-x-x
      6-x-x-x-x-x-x-x
      5-x-x-x-x-x-x-x
      4-x-x-x-x-x-x-x
      3-x-x-x-x-x-x-x
      2-x-x-x-x-x-x-x
      1-x-x-x-x-x-x-x
      0-1-2-3-4-5-6-7 男生組
      每個交叉位置x代表他們共解出同一道題。
      因每人最多解對6題,故每行每列最多只能有6個點。
      因每題都有男生女生答對,故不能有空行空列。
      把6個點看作蘋果,把行列數看作抽屜,
      則原題目轉化為:
      把6個蘋果放入多少個抽屜中,才能保證有蘋果的抽屜數最多?
      答案顯然是6。
      因橫軸和縱軸都為6,則最大考題數為36。

      刪除
    4. 正解,其實應該製作 21 x 21 表格,每格代表一位男生以及一位女生,格子內填入他們答對的題目,依老師的分析,考題總數不多於 36 題。

      進階題,根據加分題的條件,某一題最多有多少人答對?

      刪除