: as title
: 廢話不多說先po題目
: 環球城市2001春季國中高級卷，第七題
: 7.小華先從10，11，…，99這些二位數中任意挑選一個數後，再由小明來猜這個數。若小
: 明猜的數屬於下列三種情形之一：(i) 完全正確；(ii) 個位數是正確的，且十位數字相
: 差為1；(iii) 十位數是正確的，且個位數字相差為1，則小華說〝帥〞，否則就說〝遜〞
: 。( 例如：小華所挑的數字為65，若小明說出65、55、75、64或66之一，則小華說〝帥〞
: ，否則小華就說〝遜〞。)
: (a)試證：在不超過18次猜測的限制下，小明沒有任何策略可以保證他能正確地推導出小
: 華所挑選的數。(二分)
: (b)在不超過24次猜測的限制下，請幫小明找一種策略可以保證他能正確地推導出小華所
: 挑選的數。(三分)
: (c)在不超過22次猜測的限制下，是否有一種策略可以保證小明能正確地推導出小華所挑
: 選的數？(三分)
好久沒解環球的問題了
想成座標點 (x,y) 表10x+y where 1<=x<=9, 0<=y<=9
所以當有"帥"出現時可以確認正確數字在一個十字內 (請畫圖)
當確認在十字內後至多要再三次才能保證能確定正確數值為何 (簡單推論)
由這些知識來解題
(a) 顯然 90/5 = 18
若"恰好"可以將90個點分成都不相交的十字, 至少需要18-1 = 17個十字
(p.s. 當前17個都不在內的話, 可以確定在第18個十字)
但是 萬一在第18個十字 仍無法用剩餘的一次操作空間判斷出是這個十字的哪一個點
因此(a)顯然是不可能
(b)(c) 一起做
因為(c)是正確的
如圖
http://minus.com/lt9qT7WgRuzfx
三角形為沒選到的部份
因此除了7個三角形點外
剩下的部份可以用18個十字不重疊的覆蓋住
如果這18中某次出現了 "帥" 則能保證在 18+3次內找出正確的數值
如果18次都沒有"帥" 那很顯然在剩下的三角形位置
首先是下面的四個三角形可以用兩個十字覆蓋
而當有一個有出現"帥"時 僅需再一次就可以確認出正確數值
因此至多 18 + 2 + 1 =21次
如果這20次仍然沒有"帥"
就在剩下的三個三角形內
因此只要確認其中的兩個是否"帥"
就能確定為這三個中的哪一個三角形是正確的數值
至多需 20 + 2 = 22次
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.28.199