【Leetcode】458.Poor Pigs(厳密な数学的証明を配合)
タイトルアドレス:
https://leetcode.com/problems/poor-pigs/
(本文は題名の解答に対する厳格な数学の証明を配合して、少なくとも必要とする子豚の数量の上界を証明しただけではなくて、下界も証明しました.ほとんどのネット上の文章はただ一定の数量の子豚が毒水を見つけることができることを説明しただけで、しかしどうしてそんなに多くの子豚より少なく毒水を見つけることができないことを証明していません.確実性も最適性も証明しなければならない.本論文では,最適性についても厳密に証明した.)
1列のバケツが与えられ、そのうち1つのバケツの中に毒薬が入っていて、残りは普通の水です.子豚が毒水を飲むと、fixedの時間が経つと毒殺されます(この時間は他の水を飲めないので観察するしかありません).子豚は毎回たくさんのバケツの水を同時に飲むことができ、子豚たちが水を飲むたびに同時に飲むと仮定します.一定の時間を与えて、どれだけ少ないかを聞くと、この時間にどのバケツが毒であるかを検証することができます.
この問題は実際には符号化理論の問題である.まず、0、1、2、3の列が設けられていることを証明します.n − 1 0,1,2,3,...,n-1 0,1,2,3,...,n−1,合計n n n個の数字;ある人の甲を仮定して、心の中で1つのこの範囲内の数字を考えて、もう1人の乙は甲の心の中で何を考えているのかを推測したいと思っていますが、乙はk kが1 1 1 1 1 1 1の選択問題を選ぶようにしか質問できません.そして、1つの選択肢が正しいだけです.乙に少なくとも何回聞けば、必ず甲の心の中で考えている数字を推測できることを保証することができるかを聞く.
乙は少なくともc c c回聞けば推測できると仮定する.私たちはまずc c cの上界を考えます.0,1,2,...,n − 1 0,1,2,...,n-1 0,1,2,...,n−1このn n n個の数字がk k k進数整数に変換されると、最大数n−1 n−1には⌊logk(n−1)⌋+1lfloorlog_があるk(n−1)rfloor+1⌊logk(n−1)⌋+1ビット(ここで何ビットとは、最上位0 0以外のk k k進数として書かれた後、何ビットあるかを意味する).
私たちはまずこの小さな結論を証明します.m m mがk k k進数でx xビットあるとする、必然的にk x−1≦m≦k x−1 k^{x−1}le mle k^x−1 kx−1≦m≦kx−1(x x x x xビットk k k進法の最小数は1つ1 1の後ろにx−1 x−1 x−1と0 0 0 0、つまり1000...=k x−1 1000...=k^{x−1} 1000...=kx−1,最大数はx x x個1 1 1,すなわち111…=k x − 1 111...=k^x-1 111...=kx−1)なのでlogk(m+1)≦x≦logk m+1log_k(m+1)\le x\le\log_k m+1 logk(m+1)≦x≦logk m+1 x xは整数であるためx≦⌊logk m⌋+1 xlelfloorlog_k mrfloor+1 x≦⌊logk m⌋+1であり、またx x x xが存在し唯一であるため、x=⌊logk m⌋+1 x=lfloorlog_k mrfloor+1 x=⌊logk m⌋+1(ここでの論理は、x x xがk x−1≦m≦k x−1 k^{x−1}le mle k^x−1 kx−1≦m≦kx−1を満たす唯一の整数である以上、この不等式logk(m+1)≦x≦logk m+1log_k(m+1)\le x\le\log_k m+1 logk(m+1)≦x≦logk m+1で、⌊logk m⌋+1lfloorlog_k mrfloor+1
次にc c cがどれだけあるかを求めることができる:ステップ1:c≦⌊logk(n−1)⌋+1 clelfloorlog_を証明するk(n-1)\rfloor+1 c≤⌊logk(n−1)⌋+1.このような質問があることを証明するだけで、k k kに1 1 1の選択問題を聞くたびに、不等号の右側を何度も通って、必ず甲の心の中で考えている数字を聞くことができます.問題の設計は以下の通りである:第1の問題は、甲の心の中で考えている数がk k進法の下で右から第1の1桁数が0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のうちのどれか.第2の問題は、甲の心の中で考えている数がk k進法の下で右から2番目の2桁目が0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のうちのどれか.第三の問題は、甲の心の中で考えている数がk k進法の下で右から3番目の3 3桁目が0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のどちらか;第⌊logk(n−1)⌋+1lfloorlog_k(n-1)rfloor+1k(n-1)rfloor+1⌊logk(n−1)⌋+1桁は0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のうちのどれか.合計⌊logk(n−1)⌋+1lfloorlog_k(n-1)rfloor+1明らかにこんなに多くの問題がすべて答えを得た後、乙は甲が何を考えているのかを知った.
ステップ2:c≧⌊logk(n−1)⌋+1 cgelfloorlog_を証明するk(n-1)\rfloor+1 c≥⌊logk(n−1)⌋+1.反証法⌊logk(n−1)⌋+1lfloorlogより少ない場合k(n−1)rfloor+1⌊logk(n−1)+1個の数の問題、例えばl l個の問題だけを聞いても、甲の心の中で考えている数を問うことができるので、0〜n−1 0sim n−1〜n−1の数を質問ごとに符号化し、数ごとに右から1桁目の数に対して、最初の質問の答えのオプション番号に等しくします(0 0 0から).例えば、1番目の問題において、数字i i iに対応する正しい選択肢がj j番目の項目であれば、i i iの右から1桁目をj j j jとする.これに類する.これにより、0〜n−1 0sim n−1 0〜n−1の各数がl l進数にマッピングされる.k(n−1)rfloor仮に、甲がその二つの数のうちの一つを考えているとすると、乙はその二つの数のどちらであるかを区別することができない(この二つの数は乙の質問の下で、それぞれの問題の答えが同じであるため、乙はどれであるか判断できない)、これは矛盾する.だから、乙は、⌊logk(n−1)⌋+1lfloorlog_k(n−1)rfloor+1⌊logk(n−1)+1個の質問は,結果を出す保証はない.
以上より,c=⌊logk(n−1)⌋+1 c=lfloorlog_k(n−1)rfloor+1 c=⌊logk(n−1)⌋+1証明プロセス全体は,復号化を保証するためにどのように符号化すれば元のまま復元できるかという問題を実際に考慮している.
これから私たちはこの問題を解決することができます.バケツごとに0〜n−1 0sim n−1 0〜n−1の数にマッピングした.1匹の子豚が水を飲みに行きます.それはせいぜいm i n u t e s T o T e s t m i n u t e s T o D i efrac{minutesToTest}{minutesToDie}minutesToDieminutesToTestを何度も飲むことができます.m i n u t e s T o T e s t m i n u t e s T o D i e+1=kfrac{minutesToTest}{minutesToDie}+1=k minutesToDieminutesToTest+1=kとし、水を飲むたびにバケツごとに符号化することに相当する.具体的には、まず最初の子豚にk k進数の次の桁が0 0 0のバケツをすべて飲ませ、2番目の子豚はk k進数の10桁が0 0 0のバケツをすべて飲ませ、このように推すことができます.最初の时間を过ぎて、もしある子豚が死んだら、私たちは毒のあるバケツがk k k進数の下である桁数が0 0 0であることを知っていて、もしある子豚が死んでいないならば、それを続けて1 1 1のバケツを飲ませます.全部で最大k−1 k−1 k−1回飲む必要がある(k−1 k−1 k−1であるのは、子豚がk−1 k−1回飲んでも死んでいないからであり、本位数がk−1 k−1 k−1であることを示しており、一度多く飲んで判断する必要はない)ことから、有毒水の1桁あたりの数字が何であるかが分かる.したがって、必要な子豚の数はn−1 n−1 n−1 k進数である.
上記の引数で理解すると,子豚1匹につき1つの問題に相当し,m i n u t e s T o T e s t m i n u t e s T o D i e+1frac{minutesToTest}{minutesToDie}+1 minutesToDieminutesTost+1は選択肢数に相当する.少なくともどれだけの質問をして答えを得ることができますか.
コードは次のとおりです.
問題はまだ終わっていない.上はただそんなに多くの子豚が答えを保証できることを証明しただけで、どのようにして少なくともこんなに多くの子豚が必要であることを証明することができますか?私たちはただ上界を得ただけで、この上界が下界に等しいことを完全に証明していない.実は下界はその理屈で得られる.証明は次のとおりです.
各子豚は水を飲んで、全部でk−1 k−1 k−1ラウンドを飲んだ.例えば、最初の子豚は、毎回飲むバケツの集合がA 1,A 2,.,A k − 1 A_1,A_2,...,A_{k-1} A1,A2,...,Ak−1これは、A 1,A 2に有毒な水があるというk k選択問題に相当する.A k − 1 , C A_1,A_2,...,A_{k-1},C A1,A2,...,Ak−1,C(ここでC Cは残りの集合と集合の補完)の1つですか?子豚1匹は実際にはこのような選択問題に相当します.前の理屈から、結果を出すには、少なくとも⌊logk(n−1)⌋+1lfloorlog_k(n−1)rfloor+1⌊logk(n−1)+1という数回の問題が必要であり,これが必要な子豚の数である.証明済み.
https://leetcode.com/problems/poor-pigs/
(本文は題名の解答に対する厳格な数学の証明を配合して、少なくとも必要とする子豚の数量の上界を証明しただけではなくて、下界も証明しました.ほとんどのネット上の文章はただ一定の数量の子豚が毒水を見つけることができることを説明しただけで、しかしどうしてそんなに多くの子豚より少なく毒水を見つけることができないことを証明していません.確実性も最適性も証明しなければならない.本論文では,最適性についても厳密に証明した.)
1列のバケツが与えられ、そのうち1つのバケツの中に毒薬が入っていて、残りは普通の水です.子豚が毒水を飲むと、fixedの時間が経つと毒殺されます(この時間は他の水を飲めないので観察するしかありません).子豚は毎回たくさんのバケツの水を同時に飲むことができ、子豚たちが水を飲むたびに同時に飲むと仮定します.一定の時間を与えて、どれだけ少ないかを聞くと、この時間にどのバケツが毒であるかを検証することができます.
この問題は実際には符号化理論の問題である.まず、0、1、2、3の列が設けられていることを証明します.n − 1 0,1,2,3,...,n-1 0,1,2,3,...,n−1,合計n n n個の数字;ある人の甲を仮定して、心の中で1つのこの範囲内の数字を考えて、もう1人の乙は甲の心の中で何を考えているのかを推測したいと思っていますが、乙はk kが1 1 1 1 1 1 1の選択問題を選ぶようにしか質問できません.そして、1つの選択肢が正しいだけです.乙に少なくとも何回聞けば、必ず甲の心の中で考えている数字を推測できることを保証することができるかを聞く.
乙は少なくともc c c回聞けば推測できると仮定する.私たちはまずc c cの上界を考えます.0,1,2,...,n − 1 0,1,2,...,n-1 0,1,2,...,n−1このn n n個の数字がk k k進数整数に変換されると、最大数n−1 n−1には⌊logk(n−1)⌋+1lfloorlog_があるk(n−1)rfloor+1⌊logk(n−1)⌋+1ビット(ここで何ビットとは、最上位0 0以外のk k k進数として書かれた後、何ビットあるかを意味する).
私たちはまずこの小さな結論を証明します.m m mがk k k進数でx xビットあるとする、必然的にk x−1≦m≦k x−1 k^{x−1}le mle k^x−1 kx−1≦m≦kx−1(x x x x xビットk k k進法の最小数は1つ1 1の後ろにx−1 x−1 x−1と0 0 0 0、つまり1000...=k x−1 1000...=k^{x−1} 1000...=kx−1,最大数はx x x個1 1 1,すなわち111…=k x − 1 111...=k^x-1 111...=kx−1)なのでlogk(m+1)≦x≦logk m+1log_k(m+1)\le x\le\log_k m+1 logk(m+1)≦x≦logk m+1 x xは整数であるためx≦⌊logk m⌋+1 xlelfloorlog_k mrfloor+1 x≦⌊logk m⌋+1であり、またx x x xが存在し唯一であるため、x=⌊logk m⌋+1 x=lfloorlog_k mrfloor+1 x=⌊logk m⌋+1(ここでの論理は、x x xがk x−1≦m≦k x−1 k^{x−1}le mle k^x−1 kx−1≦m≦kx−1を満たす唯一の整数である以上、この不等式logk(m+1)≦x≦logk m+1log_k(m+1)\le x\le\log_k m+1 logk(m+1)≦x≦logk m+1で、⌊logk m⌋+1lfloorlog_k mrfloor+1
次にc c cがどれだけあるかを求めることができる:ステップ1:c≦⌊logk(n−1)⌋+1 clelfloorlog_を証明するk(n-1)\rfloor+1 c≤⌊logk(n−1)⌋+1.このような質問があることを証明するだけで、k k kに1 1 1の選択問題を聞くたびに、不等号の右側を何度も通って、必ず甲の心の中で考えている数字を聞くことができます.問題の設計は以下の通りである:第1の問題は、甲の心の中で考えている数がk k進法の下で右から第1の1桁数が0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のうちのどれか.第2の問題は、甲の心の中で考えている数がk k進法の下で右から2番目の2桁目が0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のうちのどれか.第三の問題は、甲の心の中で考えている数がk k進法の下で右から3番目の3 3桁目が0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のどちらか;第⌊logk(n−1)⌋+1lfloorlog_k(n-1)rfloor+1k(n-1)rfloor+1⌊logk(n−1)⌋+1桁は0,1,.,k − 1 0,1,...,k-1 0,1,...,k−1のうちのどれか.合計⌊logk(n−1)⌋+1lfloorlog_k(n-1)rfloor+1明らかにこんなに多くの問題がすべて答えを得た後、乙は甲が何を考えているのかを知った.
ステップ2:c≧⌊logk(n−1)⌋+1 cgelfloorlog_を証明するk(n-1)\rfloor+1 c≥⌊logk(n−1)⌋+1.反証法⌊logk(n−1)⌋+1lfloorlogより少ない場合k(n−1)rfloor+1⌊logk(n−1)+1個の数の問題、例えばl l個の問題だけを聞いても、甲の心の中で考えている数を問うことができるので、0〜n−1 0sim n−1〜n−1の数を質問ごとに符号化し、数ごとに右から1桁目の数に対して、最初の質問の答えのオプション番号に等しくします(0 0 0から).例えば、1番目の問題において、数字i i iに対応する正しい選択肢がj j番目の項目であれば、i i iの右から1桁目をj j j jとする.これに類する.これにより、0〜n−1 0sim n−1 0〜n−1の各数がl l進数にマッピングされる.k(n−1)rfloor仮に、甲がその二つの数のうちの一つを考えているとすると、乙はその二つの数のどちらであるかを区別することができない(この二つの数は乙の質問の下で、それぞれの問題の答えが同じであるため、乙はどれであるか判断できない)、これは矛盾する.だから、乙は、⌊logk(n−1)⌋+1lfloorlog_k(n−1)rfloor+1⌊logk(n−1)+1個の質問は,結果を出す保証はない.
以上より,c=⌊logk(n−1)⌋+1 c=lfloorlog_k(n−1)rfloor+1 c=⌊logk(n−1)⌋+1証明プロセス全体は,復号化を保証するためにどのように符号化すれば元のまま復元できるかという問題を実際に考慮している.
これから私たちはこの問題を解決することができます.バケツごとに0〜n−1 0sim n−1 0〜n−1の数にマッピングした.1匹の子豚が水を飲みに行きます.それはせいぜいm i n u t e s T o T e s t m i n u t e s T o D i efrac{minutesToTest}{minutesToDie}minutesToDieminutesToTestを何度も飲むことができます.m i n u t e s T o T e s t m i n u t e s T o D i e+1=kfrac{minutesToTest}{minutesToDie}+1=k minutesToDieminutesToTest+1=kとし、水を飲むたびにバケツごとに符号化することに相当する.具体的には、まず最初の子豚にk k進数の次の桁が0 0 0のバケツをすべて飲ませ、2番目の子豚はk k進数の10桁が0 0 0のバケツをすべて飲ませ、このように推すことができます.最初の时間を过ぎて、もしある子豚が死んだら、私たちは毒のあるバケツがk k k進数の下である桁数が0 0 0であることを知っていて、もしある子豚が死んでいないならば、それを続けて1 1 1のバケツを飲ませます.全部で最大k−1 k−1 k−1回飲む必要がある(k−1 k−1 k−1であるのは、子豚がk−1 k−1回飲んでも死んでいないからであり、本位数がk−1 k−1 k−1であることを示しており、一度多く飲んで判断する必要はない)ことから、有毒水の1桁あたりの数字が何であるかが分かる.したがって、必要な子豚の数はn−1 n−1 n−1 k進数である.
上記の引数で理解すると,子豚1匹につき1つの問題に相当し,m i n u t e s T o T e s t m i n u t e s T o D i e+1frac{minutesToTest}{minutesToDie}+1 minutesToDieminutesTost+1は選択肢数に相当する.少なくともどれだけの質問をして答えを得ることができますか.
コードは次のとおりです.
public class Solution {
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int k = minutesToTest / minutesToDie + 1;
int n = buckets - 1;
int count = 0;
while (n != 0) {
n /= k;
count++;
}
return count;
}
}
問題はまだ終わっていない.上はただそんなに多くの子豚が答えを保証できることを証明しただけで、どのようにして少なくともこんなに多くの子豚が必要であることを証明することができますか?私たちはただ上界を得ただけで、この上界が下界に等しいことを完全に証明していない.実は下界はその理屈で得られる.証明は次のとおりです.
各子豚は水を飲んで、全部でk−1 k−1 k−1ラウンドを飲んだ.例えば、最初の子豚は、毎回飲むバケツの集合がA 1,A 2,.,A k − 1 A_1,A_2,...,A_{k-1} A1,A2,...,Ak−1これは、A 1,A 2に有毒な水があるというk k選択問題に相当する.A k − 1 , C A_1,A_2,...,A_{k-1},C A1,A2,...,Ak−1,C(ここでC Cは残りの集合と集合の補完)の1つですか?子豚1匹は実際にはこのような選択問題に相当します.前の理屈から、結果を出すには、少なくとも⌊logk(n−1)⌋+1lfloorlog_k(n−1)rfloor+1⌊logk(n−1)+1という数回の問題が必要であり,これが必要な子豚の数である.証明済み.