您當前的位置：首頁 > 舞蹈

【國際數學競賽】邏輯推理

作者：由雙木止月Tong 發表于舞蹈時間：2019-07-31

本想歸納一下邏輯推理題的方法與技巧，但發現很多題可能並不是靠什麼方法與技巧，就靠讀題分析與推理，所以直接把本文取名為“邏輯推理”。下面直接透過試題來分享：

第一題是2015年DMM杜克數學大會團隊賽的第二題（今年8月2日到5日DMM中國區終選在崑山杜克舉行）

問題一：2015-DMM-Team Round-2

題意：在一個圓上寫上了1到n共n個整數

$(n\geq2)$

，滿足任意相鄰兩個數其數位上至少有一個數字相同，請問最小的n是多少？

這裡解釋一下題意要求相鄰兩個數有數字相同，比如12與2都有一個數字2滿足要求，接下去我們就按照題意去思考就可以了。

解：因為

$n\geq2$

，為了保證相鄰兩個數有相同數字，那麼n必須大於10，不然1、2都沒有數字相鄰。因為n大於10，那麼必定有一個數字“9”在圓上，為了“9”左右兩側的數字都含有“9”那麼

$n\geq29$

。（不然“9”不滿足題意）

所以只需要給出一種

的數字排列，就可以說明n最小是29。下面給出n=29時滿足題意的一種排法：

所以答案為

$\boxed{29}.$

這道題的關鍵點就是在“9”這個數字上，為了滿足“9”的要求確定了n的取值範圍，然後嘗試得到了一個解。這裡排列的時候要注意，利用

$\overline{2a},a,\overline{1a}$

完成過渡。

問題二：2016-DMM-Tiebreaker Round-2

題意：找到最小的

，使得

$n\times n$

的正方形能夠劃分成5個長方形，且5個長方形的邊長各不相同，

$\{1,2,3,\ldots,10\}$

中的值都恰好用了一次。

把

$n\times n$

的正方形劃分成5個長方形，一共有10條線段長，恰好從

$\{1,2,3,\ldots,10\}$

取。那麼關鍵點是這個

是多少，然後再下手去嘗試。

解：我們可以根據5個長方形的面積來估計

的取值，因為10條邊長所組成的5個長方形最大的面積為：

$1\cdot2+3\cdot4+5\cdot6+7\cdot8+9\cdot10=190$

，

最小的面積為：

$1\cdot10+2\cdot9+3\cdot8+4\cdot7+5\cdot6=110$

。

（排序不等式，正序和≥亂序和≥逆序和）

所以，我們可以知道

$11 \leq n \leq 13$

。

於是，我們就可以從

開始去湊了，恰好可以滿足：

所以，滿足條件的

最小值為

$\boxed{11}$

。

這道題關鍵點在於計算出

的取值範圍，然後才能去湊，不然真的是毫無頭緒。

問題三：2016-DMM-Relay Round-2.3

注：T=12，這是接力賽的第三題，T是由第二題得到的。

題意：在一個房間裡有29個人

$a_1,a_2,\ldots,a_{29}$

，他們相互握手，且

$a_i,1\le i\le28$

握了

次手。請問

$a_{29}$

握了幾次手？

剛看到這道題時覺得有點懵，因為只告訴我們前28個人握了多少次，沒有告訴我們怎麼握的，然後就問第29個人握的次數，好像有很多種可能的樣子，不過這裡分析一下就會發現這個握手的情況已經被定下來了。

解：我們可以從

$a_{28}$

入手，

$a_{28}$

握了28次手，一共29個人，也就是說他和所有人都握了手。這裡想到

只握一次手，那麼

就只能和

$a_{28}$

握了；

接著可以考慮

$a_{27}$

，握手27次，除去

和其本身，剛好27個人，所以

$a_{27}$

與

$a_2,a_3\ldots,a_{29}$

握了手。接著發現

只握手兩次，那麼就只能和

$a_{27},a_{28}$

握手了，其他人都不能握手了。

以此類推，我們可以發現

$a_i,15\le i\le28$

與

$a_{29}$

和

$a_1,a_2,\ldots a_{29-i}$

握手，而

$a_{j},1\le j\le14$

都沒有和

$a_{29}$

握手。

所以，

$a_{29}$

一共握手

$28-15+1=\boxed{14}$

次。

按照題意一步一步分析發現這就是唯一的解，找到突破口很關鍵，就像是第一問的數位“9”，第二問

的取值範圍，和第三問的

$a_{28}$

握手次數，再加上嚴謹地推理才能較為順利地解決此類問題。當然能夠湊出來答案也是本事呀。

問題四：2018-AMT-Guts Round-5

題意：定義一個整數集合是powerful的，如果集合中任意一對整數的差都是2的次方。請問滿足powerful的集合中最多有多少個元素？

乍一想滿足powerful這一性質的集合裡面的元素應該挺多的，比如

$\{1\},\{1,2\},\{1,2,3\}$

，但實際上滿足這一性質的集合最多有三個元素。下面我們來證明一下四個元素是不可能的。

假設滿足powerful的集合中有四個元素

。

根據powerful的性質，

$b-a=2^{k_1}$

，

$c-d=2^{k_2}$

，

$d-c=2^{k_3}$

。那麼

$c-a=(c-d)+(d-a)=2^{k_2}+2^{k_1}$

，所以

，不然

就不是2的次方數了。同理，我們也可以推得

。

於是，

$d-a=(d-c)+(c-b)+(b-a)=3\cdot 2^{k_1}$

，這不是2的次方，跟powerful的性質矛盾了。

因此，滿足powerful性質的整數集中最多有

$\boxed{3}$

個元素，比如

$\{1,2,3\},\{2,3,4\}$

等。

這一類問題還有很多日後持續更新，歡迎交流討論~~

本文介紹的是正面突破，而反證法也是常見的方法與技巧，有興趣可參閱下文：

想了解更多國際數學競賽及課程的知識，可瀏覽下文：

微信訂閱號：數你好看

標簽：題意握手 powerful DMM 29

上一篇:錦春國際旅行社和佳途國際旅行社哪家好？國際哪家更專業靠譜？

下一篇：零基礎想練習傳統武術入門方法

猜你喜歡