Re: [其他] 問一題競賽題@@...
※ 引述《xx41102 (We are X!)》之銘言：
: 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次猜測的限制下，是否有一種策略可以保證小明能正確地推導出小華所挑
: 選的數？(三分)
: 第一題就卡了...
: 我原本打算用鴿籠原理(18x5=90)看看,發現不太可能
: 後來有一個想法是把10~99這90個數字排成10*9的長方形
: 然後以隨便點一點他上下左右一單位的格子跟自己那格會被"影響"到(也就是被喊帥)
: 可是發現邊邊的處理不了....
:
: (以上有我個人想法,想先自我嘗試的可以寫看看不要開燈,可是其實我的想法也沒解出來..
: ...)
: 有人能幫忙解嗎ˊˋ
: 謝~
(一)不管被說〝帥〞或〝遜〞,我們都可以確定一組5個數是我們要的還是我們不要的
所以最好個情況猜第一組數字就被說〝帥〞,最糟情況猜到第90/5=18組數字才被說〝帥〞.
(二)再來看這五個數字,先猜哪一個也不會影響其他數,
所以最好的情況,這五個數第一次就猜到,最糟的情況第五次才猜到.
綜合(一)(二)
最快就猜第一組的一個數字就猜中
最慢就猜到第18組,之後再猜4個數字(因為猜到18組已經猜掉五個數字中的一個)
最慢18+4=22次
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.200.69
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：