から奇妙なボールを見つけます $18$ ボール、どこ $17$ 同じ重さ。
この問題には多くの変種があります。私が取り組んでいるのは
がある $17$ 同じ重さのボール、そして $1$重量を量ることができ、ボールのいずれか他のより重いか軽いです$17$。バランススケールで何個の重りがあり、奇数を決定する必要がありますか？それが重いか軽いかを判断しますか？
奇数のボールが重いか軽いかがわかる簡単なケースは、 $3$重さ。アイデアは分割することです$18$ のグループにボール $6$、 いう、 $6A$、 $6B$、 $6C$。計量する$6A$ そして $6B$スケールで。それらが互いにバランスをとっている場合、$6C$奇妙なものがあります。それらが互いにバランスをとっていない場合、そして$6A$ スケールが低い場合は $6A$ より重いボールを持っています、そして同様に $6B$。したがって、最大で$1$ のグループを決定するために計量する $6$重いボールで。次に、このグループを分割できます$6$ に $3$ のグループ $2$、そして同じ考えを使用して、あなたはの奇妙なグループを見つけることができます $2$ 最大でアウト $1$計量します。その後、あなたはのグループが残っています$2$ そしてそれはかかります $1$重いボールを決定するために計量します。だから、合計で、あなたは必要です$3$ この場合、重量を量ります。
しかし、この問題のより難しい変種は、奇数のボールが重いか軽いかがわからない場合です。この場合、私はあなたが最大で必要であることがわかりました$5$ 奇妙なものを見つけて、それが重いか軽いかを判断しようとしますが、これが正しいかどうか、またはこれが最大試行回数の最小数であることを正当化する方法がわかりません。
考え方は前の問題と似ています。除算$18$ ボールに $6A$、 $6B$、 $6C$。今回は最大で$2$ のグループを見つけようとします $6$。すなわち、重量を量る$6A$ そして $6B$ スケールで、それらが一致する場合、 $6C$奇妙なグループです。場合$6A$ そして $6B$が一致しない場合は、奇数を決定するために追加の重量が必要です。したがって、$2$ 試みます。
今、私たちはの奇妙なグループを見つけたら $6$、同じアイデアを適用します。 $2$試行（最大）。その後、私たちはのグループが残っています$2$。正確にかかる$1$ あなたが取ることができるので計量する $1$ のグループからのボール $2$ そしてそれを他の1つと計量します $16$私たちが知っているボールはです。このボールが同じである場合、残りのボールは奇数です。したがって、最大で$2+2+1 = 5$この奇妙なボールを見つけようとします。この残りのボールが重いか軽いかを判断するために、追加の重量を量る必要はありません。
これは、 $6$、および後続のグループ $2$、私たちは最大を取りました $2$試みます。かかる場合$2$ の奇妙なグループを見つけようとします $6$ アウト、それは2番目の重量を意味します $2$ 試行することで、この奇妙なボールアウトが重いか軽いかを判断できます。
たとえば、 $6A$、 $6B$、 $6C$再び。最初に計量するとします$6A$ そして $6B$重さが同じではないことがわかります。次に、重量を量ります$6C$ どちらかと $6A$ または $6B$。計量すれば$6A$ と $6C$ そしてそれを見つける $6A$ 一致しません $6C$、その後 $6A$ 奇妙なものですが、 $6A < 6C (6A > 6C)$、それから私たちは知っています $6A$ 重量が少ない（多い）ボールがあります。
これが最適なアプローチですか、それとも唯一の方法がありますか $4$計量しますか？私の腸は私にあるべきだと言っています$4$ 計量アプローチ。
ザ・ $12$-問題のボールバリアントとその解決策はに掲載されています http://www.mytechinterviews.com/12-identical-balls-problem。あなたは彼らが破ることによって類似のアプローチを適用するのを見ることができます$12$ ボールに $3$ のグループ $4$、しかし、彼らはいくつかの興味深いミックスとマッチングを適用して、奇妙なものを見つけるだけです $3$ 移動します。
回答
私は古典の解決策をチェックしませんでした $12$ ボールバージョン http://www.mytechinterviews.com/12-identical-balls-problem。しかし、それが機能する場合、それは些細なことにつながります$4$ の計量ソリューション $18$ ボールケース。
本当に、古典を考えると、やるべき余分な仕事はほとんどありません！
まず、体重を量ります $3A$ vs $3B$。バランスが取れていない場合は、$3A > 3B$、あなたはで見つけることができます $3A$ vs $3C$ （すべて $3C$良い）悪いボールが重いか軽いか。その後、確かにあなたはのグループの中から犯人を見つけることができます$3$もう1回計量するだけです。合計$3$ 計量。
で、もし $3A = 3B$、それからあなたは古典に還元されます $12$-で解決できるボールの問題 $3$ 追加の計量、合計 $4$。
さらなる考え：実際には、 $4$ 計量は解決できます $30$ ボールだけでなく $18$。
上記では、 $3A \neq 3B$ ブランチは常に $3$無駄な総計量。あなたが持っていると想像してください$9+9+12 = 30$ボール。最初の計量は$9A$ vs $9B$。それらが不均衡な場合は、もう一度$9A$ vs $9C$ （すべて良い）悪いものが重いか軽いかを教えてくれます、そしてあなたは使うことができます $2$ 犯人を見つけるためのより多くの計量 $9$ （三次検索）、合計 $4$ 計量。
さらに、何年も前に私はケース（クラシックの拡張）を解決しました $13$ ボール（未知の重い/軽い）はで解決することができます $3$ 計量、良いことがわかっている追加のボールにアクセスできる場合-必要なIIRC $2$そのような良いエキストラ。これの意味は$9+9+13 = 31$ で解決することができます $4$ 計量、coz in the $9A=9B$ あなたが本当に残されている場合 $13$ 容疑者が、良いことが知られている多くの余分なボール。
私も疑う $31$ 制限ではありません（ $4$計量）。体重を量るとき$9A$ vs $9C$、2つの結果のみが発生する可能性があります（ $9A > 9B$）。これは非常に非効率的であり、さらなる悪用が可能かもしれません...
あなたはおそらく古典的な限界を知っています $n$ 計量のみがあります $3^n$ 可能な結果、 $n=4, 3^n = 81$、解決できません $\ge 41$ ボール（$\ge 82$結果）。私は言っていない$40$ 達成可能ですが、間に大きなギャップがあります $31$ そして $40$..。
計量1：計量$1$-$6$ 対 $7$-$12$。結果のバランスが取れている場合、奇数のボールがセットに含まれていることがわかります$13$-$18$、（実際に）かかる $3$合計4つの計量のためのより多くの測定。
最初の計量が不均衡である場合、一般性を欠くことなく、$1$-$6$ より重い $7$-$12$。次に実行します...
計量2：計量$1$-$3$ 対 $7$-$9$。結果のバランスが取れている場合、奇数のボールは$\{ 4, 5, 6, 10, 11, 12 \}$、それは確かにかかります $3$より多くの計量、合計5つの計量。
代わりに結果が不均衡である場合、一般性を失うことなく、$1$-$3$ より重い $7$-$9$。次に、奇数のボールが6つのセットに含まれていることがわかります。これには、合計5つの計量に対してさらに2つの計量が必要です。