51 張牌任意分成兩堆給兩個人,如何在只能傳遞一張牌的情況下猜出缺失的牌?

時間 2021-05-12 01:08:47

1樓:

題目並沒有說傳遞牌的時候不能在牌面做記號,那麼最簡單的方式就是Bob把手中的牌寫在任意一張牌上傳遞過去。當然還有別的傳遞方式,例如摺疊牌通過摺痕來傳遞資訊,此外還可以通過一定的編碼方式降低需要的資訊量(例如用52bit的二進位制數標明所有手上的牌,再將52bit的數字轉換到高進製以減少數字位數)。個人理解,這道題的本質是問如果用最少的資訊量(能表示在一張牌面上面),使得對方能夠得到所需的資訊

2樓:zokoko

1.把答案寫在牌上

2.牌用尺子分為7*8份,編碼好52個順序,沒有的牌就撕掉那乙份(或者用指甲劃一下),傳牌就知道了

3.一分鐘有60秒,每秒做編碼對應,有牌就響(彈牌或抽拉),直到資訊傳完

4.如果傳遞的時候大家都能看到的話,畫個52個格仔(大富翁),用牌在上面移動,停一秒就算有,走完格仔就知道了

5.樓上chen的1到52相加的演算法挺好的,就時間長了點,一小時有3600秒呢~(手錶或手機有秒的話)

暫時這麼多吧~

3樓:孔玄

此題無解。

我們從Bob被分到兩張牌看起吧。

我們先給牌組隨機編號1-52,這總是可以的。(程式設計師勿亂入)假如Bob拿到了1號和2號牌。他必須按照某種規則X選出一張牌給Alice。

不論他選出了1號還是2號,這兩張牌總是等價的。不妨設他選出了1號牌,那麼問題就來了——

此時鮑勃如果拿到了1號和3號,他就必須給愛麗絲3號,否則如果愛麗絲恰好沒有1號,2號和3號牌,鮑勃給她的是1號牌,她就無法判斷鮑勃手裡另一張是2號還是3號牌。同樣的道理,鮑勃在面對1號和4號,1號和5號牌的時候,必不能給1號。

問題已經明顯了,同樣的推理可以得出,由於鮑勃拿到了1號和3號給出了3號,他就不能在手裡有3號牌而沒有1號牌的時候給出3號牌,這樣一來,如果愛麗絲沒有1,3,4號牌,而鮑勃手裡有一張4號牌。他只能給愛麗絲4號牌,這樣一來愛麗絲就無法判斷鮑勃還剩一張1號牌還是3號牌了。

故而此題無解。

4樓:

這裡傳遞一張牌的意思不是很確定。傳遞是傳遞一張實體的牌還是說出來一張牌?兩者區別很大,因為的確可以用一張牌來傳遞自己手裡牌的很多資訊,但是自己手裡不一定剛好有這張牌,如果是說出來的話想了一下覺得是有解法的。

5樓:

先編號黑桃:1-13(牌面)

紅心:14-26(牌面+13)

方塊:27-39(牌面+26)

黑梅:40-52(牌面+39)

比如,方塊三是3+26=29

把一副牌總數1378(1加到52)算出,Bob和Alice也各自算出自己手上總數x,y,1378-x-y就是答案了,(比如1378-x-y=29,29=26+3,所以缺的就是方塊三)

這點很容易,大家一定都想到了。

問題是。Bob要怎麼讓Alice知道x值呢?

已知x的取值範圍在1-1375之間

(52×(52+1)/2-1-2=1375)肯定不能對牌做手腳(寫字,摺疊),也不能說話發簡訊等交流,手頭的牌數量既不定又有限,很難保證一定可以用他們表達出想要的數字(比如Bob手頭就兩張牌什麼的)。

所以,只好想其他辦法。

有乙個思路,是利用雙方共同知道的資訊來暗中傳達數字。

在本題中,就是。。。時間!

兩人各帶一塊表,進入房間前校對好時間。

午夜零點過了幾分鐘。那個時間就是x。

比如當x=248

也就是0點過了248分鐘,

即早上4:08分。

到那個時候,Bob自信地隨便遞張牌給Alice,她看看自己的手錶,會心一笑,就懂了。

那張不帶任何含義的牌,也可以順便表達些別的意思。

紅心:我喜歡你

黑桃:我不喜歡你

方塊:今晚你家。

黑梅:今晚我家。

。。。。。等等

6樓:Changlong Wu

把 @張雨萌的argument推廣一下,可以得到如下結論:

設為全域集且。

若那麼不存在函式,使得.

證明:考慮任意n-2階子集,我們通過新增兩個新元素將其擴充套件為兩個n-1階集合。容易知道對於每個i = 1,2我們有種方式擴充套件為n階集合,但這些集合中只有最多n-1個集合取值為中的元素,因此至少有個集合取值為新加入的元素,由於所以當時,根據鴿巢原理存在e使得

,矛盾!

Edit: 這裡證明有問題,只能得到.

這表明,只有當Bob擁有多數牌時才可能有解決方案。

====

下面是乙個奇數的染色方案

====

事實上 @張雨萌提到的染色方案等價為乙個idempotent symmetric latin square。

可以證明n階idempotent symmetric latin square存在,當且僅當n是奇數。

必要性已經由張雨萌提到的反證法證明,充分性由如下同余式構造:

記,那麼,容易驗證這是可行的。

====

更新: 09/22/2015

之前在Mathoverflow上問了這個問題:co.combinatorics,現在有了乙個新回答可以得到乙個更好的界這裡p是n的最小素因子。

7樓:qfzklm

52=13*2*2

記桃心和非桃心分別對應1,0,紅色和黑色分別對應1,0。

B給出一張牌Z,Z的點數是把手上所有牌的點數加起來模13的餘數,花是桃心牌的個數模2的餘數,顏色是紅色牌的個數模2的餘數。

唯一的問題就是Z需不需要是B的手牌,我原先看到這個問題時,是說B可以告訴A一張牌的資訊,不需要是手牌。

8樓:

我們考慮A的視角他缺了N張牌 B有可能給他這N張牌的某一張他需要把這張牌和缺的牌建立乙個一一對應。

考慮B的視角,他有N–1張牌他要根據這N-1張牌確定唯一給出的一張牌。

要是能給乙個數就好了,給數字和就好了。

我們假設只有四張牌1 2 3 4,並且B手裡有1 2的時候會給1。

那他手裡有1 3的時候呢?如果給1,假如A手裡是4,A就傻了,他不知道B手裡是1 2還是1 3。所以B應該給3。

所以他手裡有2 3的時候應該給2。同理有1 4的時候應該給4。

那2 4的時候呢?我也不知道應該給什麼了。

怎麼就無解了?我也不知道。一定是因為我發燒了。

打完字才發現就是@張雨萌的答案,果然該睡覺了。

爐石傳說如果一張牌能滿編三十張,哪一張牌可以使勝率最高?

公尺粒 刺客的話30張影襲爆牌魚這樣的話效率是最高的,但是其實你這個問題有一點漏洞就是你沒有考慮到過牌,如果是30張低費,如果前期一下子打完即使有很高的爆發,也彌補不了後期一張一張打的缺陷,因為在不考慮解場,回血,免疫,潛行等等因素即使你有一定的攻擊頻率但是也無法做到爆發,再單獨講一下爆牌魚,他這張...

把某張十分好用的藍白紫卡,出一張牌面一模一樣的橙卡,意味著你通過氪金可以帶第三張,這個點子怎麼樣?

沈天昊 職業卡和中立差很多,銀行家來洗牌對於盜賊來說就太弱了,火車王當年4費打6對法師來說只是一張火球,爐石很多時候最大的差別就在職業差距了。機械的話牧師沒法玩,惡魔是術士專屬,魚人基本只有騎士薩滿,元素只有法師牧師薩滿,牧師的龍和戰士的龍最強。由此可得,建議出一些中立,無種族的卡。麻風侏儒就可以出...

爵士 129 127 險勝掘金,公尺切爾 51 分穆雷 50 分,如何評價這場比賽?

陳kk 掘金少了哈里斯和巴頓,爵士少個博洋。掘金實際上來說陣容缺陷因為這兩人,顯得更為突出,就就集中在對外線的防守上。歷史交手看,加里哈里斯進攻效率很低,但是往往將公尺切爾拉到同一水平上菜雞互搏,防守功力可見。巴頓替補效率很高,能攻能傳,而且無縫銜接主力。而這是這輪掘金的痛點,替補陣容效率不足以往。...