第二版殺拉的五題串燒

21457

接下來我會陸續放出5道邏輯題
題目難度和類型會和我的《第一版殺拉五題串燒》相似，地址是 http://www.njjzkj.com/forum.php?mod=redirect&goto=findpost&ptid=39027&pid=406101
每解答出一道題我才會放出下一道題。
題目難度不一，涉及領域也不盡相同,有的會被秒掉的吧……
下面放出第一題……(求秒，求人氣……)

21457

1房間內有100盞燈，房間外有100個開關。開關和燈一一對應。只有進房間之后才知道，哪個燈亮著。如果一個人想把哪個燈和對應哪個開關弄全部弄清楚，至少需要進房間幾次？
(只考慮燈的光效應和熱效應)
(燈泡發熱需要的時間足夠長，發熱的時間也足夠長。)
(燈無故障)

17264

5次
因為3^4<100<3^5

22568

首先,不考慮發熱,只考慮開關..我覺得只有如此才是恰當的數學題..雖然lz好像不愿如此..
每次進入時僅能分辨開關,即每次都是拆分成兩個子集,熟知二分可以做到,需要ceil(log(100))=7次.

然后,我們考慮lz的意思:(只考慮燈的光效應和熱效應)(燈泡發熱需要的時間足夠長，發熱的時間也足夠長。)??
意思是可以考慮發熱了?
顯然,不考慮發熱的話,一次只能按是否亮分辨兩個;而我們熟知的一個日經題要求分辨三個,則是利用發熱.
事實上僅看是否發光是否發熱顯然可以分辨4個.所以將上一結論改成四分,可知需要ceil(log[4](100))=4次.

我說完了嗎,不,還沒..秉承一貫的吐槽屬性,我們提出真相:
假設進入時開關達到穩定狀態,那么發光狀態是只有雙值的;然而,熱效應跟電的大小啦通電時間啦斷電時間啦啥的都有關系,并不是一個簡單的雙值,而可以認為有一個連續的取值范圍.
理論上來講,做到任意多個溫度的梯度是可行的.
通俗點講結論就是,就算不考慮發光只考慮發熱,再多的燈也只需要一次.
再通俗一點講做法,在外頭先開第一個,過恰當時機開第二個,過恰當時機開第三個,...,直到全都開了,然后進去按溫度排序即可.

8475

為什么是4次~難道烏鴉叔腦子轉不過彎了嘛~
一次能分辨4盞燈~不能應該25次嗎~

21457

本題由天馬行空答對
一共四種狀態，每次可以把燈泡分成4組
4的三次方=64＜100＜256=4的四次方
則辨別100個燈泡只需要4次進入房間

2一個游戲中，拋出色子(色子有1到6)，拋出多少前進多少格。某玩家前進到第10格了，他從游戲開始之后拋出的色子順序，有多少種可能？

22568

第二題..也就是和為10的由1到6組成的有序數組的個數..
用生成函數來講,也就是1+A+A^2+A^3+A^4+...=1/(1-A)中x^10的系數,其中A=x+x^2+x^3+x^4+x^5+x^6.
將A/(1-A)拆成部分分式可得到通項公式,但1-A是不可約的六次式..故..
沒啥好方法,就是死算.
反正算出來就是1+1*x+2*x^2+4*x^3+8*x^4+16*x^5+32*x^6+63*x^7+125*x^8+248*x^9+492*x^10+976*x^11+1936*x^12+...
總之,答案是492,并且一般來講這個問題沒有什么特別好的方法.

為了避免有人看不懂..我們來換一個說法..直接說遞推..
記"若干次加起來是n"的方法種數是f(n),于是要求的就是f(10).
f(n)=0(n<0),f(0)=1,f(n)=f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)+f(n-6).
(ps.知道fibonacci吧..就是那些兔子啦爬樓梯啦那種112358的數列啦..跟這個是一樣的..只是這個多幾項而已..)
于是10這種規模就直接手算吧..

0	1	2	3	4	5	6	7	8	9	10
1	1	2	4	8	16	32	63	125	248	492

可以看到和上頭的答案是吻合的.(11個數都一樣.)
線性遞推,有通項公式,同樣是要解沒簡單解的六次方程.

21457

第二題還是由天馬行空回答正確
答案是492，方法也講對了

3有兩堆棋子，一堆50個，一堆100個。有兩個玩家，輪流拿棋子。拿棋子的規則是：從一堆中拿任意數目個，或者從兩堆中拿相同數目個。拿到最后一個棋子的玩家獲得勝利。那么，第一個玩家怎么拿，就能一定獲得勝利？

22568

第三題.
先說結論吧.敗局狀態集L={{[na],[nb]}|n為自然數},其中a=(1+sqrt(5))/2,b=(3+sqrt(5))/2,[.]為高斯函數/gauss/下取整函數/int/截尾函數/trunc/地板函數/floor(愛咋叫咋叫吧..).
于是{50,81}是敗局.從100中取走19即為第一步的正解.

下面稍微多說一點點..
觀察{[na]},{[nb]}這兩個數列:
首先由beatty定理知這兩個數列無重復的覆蓋了自然數集(0除外).(相關證明如若想要自行搜索.)
ps.數列的單調性則是顯然的.
其次,不難證明[na]+n=[nb].(反正,假定數列滿足beatty定理的形式,由此式亦可算出對應的系數(指之前的黃金數).)

然后稍微說下這的確是L的證明:
首先,其中兩兩間顯然不能轉化:
沒有重復數,故取一堆不能轉化;差也不重復,故同時取兩堆亦不可轉化.
其次,不屬于L的任一狀態{x,y}(x<=y)均可轉化為L中狀態:
記(x,z)為L的元素,則z<>y.
若z<y,將{x,y}取為{x,z}即可;否則,將{x,y}取為{p,q}={[(y-x)a],[(y-x)b]}即可(由z-x>y-x知p<a,q<b)(注意到q-p=b-a).

另附半個月前qq中寫的偽代碼,僅供參考:

1. input a,b
   
2. x=(sqrt(5)+1)/2
   
3. if a>b
   
4.         swap(a,b)
   
5. t=[(b-a)*x]
   
6. if t=a
   
7.         ret LOSE
   
8. if t<a
   
9.         ret (t,b-a+t)
   
10. t=[(a+1)*(x-1)]
    
11. if a<t*x
    
12.         ret (a,a+t)
    
13. t=[(a+1)*(2-x)]
    
14. ret (a-t,a)

復制代碼

ps.說到qq那么問題就來了..我當時是在對誰說的呢..沒錯就是lz..

35077

什么鬼
這種題專業性太強了吧，讓我這種數學弱智怎么辦？
邏輯跟數學雖然關聯是最強的，可惜我的數學很弱，完了...
數學里面我稍微在行一點的就是幾何，殺拉來點跟幾何有關系的題我試試吧