5

以下の場所から記事を読んでいます。これがテキスト スニペット フォーム ドキュメントです。

リンク

勝利を保証するチケットの最小セットを見つける問題は簡単ではありません。R の結果のうちの P が占い師のセットからのものになることを考えると、NCP = (N/P!)/(NP)! があることを確認することは難しくありません。当選チケットで発生する可能性のある占い師セットからの可能な P サブセット。占い師のセットからすべての P サブセットを W 回選び、残りの RP スロットを任意に埋めると、得られたチケットのセットには各 P サブセットが少なくとも W 回出現し、W 回の勝利が保証されます。ただし、そのようなセットは最小のものである必要はなく、ほとんどの場合そうではありません。

占い師の約束から、当選チケットで P サブセットの 1 つが発生することがわかっています。2 つの P サブセットの違いが J 数未満である可能性があります。このような状況が発生した場合、サブセットは、共有された J 番号に関して互いに重複またはカバーしていると言われ、P サブセットの 1 つだけが購入されたチケットに含まれている必要があります。この現象は、例を使用して最もよく説明されています。PICK-4 ロトをプレイしていて、2/4 の勝利が 1 回必要であるとします。したがって、R=4、J=2、W=1 です。さらに、占い師が 5 つの数字のセットから 3 つの数字を予測するとします (つまり、 P=3 および N=5 )。すべての P サブセットが占い師のセットから取得され、チケットを完了するために任意に埋められた場合、1 つの 2/4 の勝利を保証する 10 個のチケットのセットが得られます (図 1 を参照)。でも、いくつかの 2 つの番号が重複しているため、このセットから一部のチケットを除外することもできます。たとえば、サブセット {3, 4, 5} は {1, 3, 5} とは 1 つの数字だけが異なり、購入したチケットでこれらの両方を使用するのは無駄です。{3, 4, 5} を含めないと負ける可能性があると考えるかもしれませんが、{3, 4, 5} が発生した場合、{1, 3, 5}賞品を獲得するために購入したものです! 同様に、さらに多くの冗長な P サブセットが存在する可能性があります。最適な解を図 2 に示します。私たちの宝くじの問題は、重複の数を最小限に抑えることによって指定された勝利数を保証する、占い師のセットから最小の P サブセットのセットを見つけることです。

私の質問は次のとおりです

  1. 著者が述べたように、「すべての P サブセットが占い師セットから取得され、チケットを完了するために任意に入力された場合、10 個のチケットのセットが得られます」切符売場？

  2. 上記の例で、1 と 3 が発生し、{1, 3, 5} を選択しなかった場合、どうすればここで勝つことができるでしょうか?

  3. 記事にない図2を思いつく人はいますか?

感謝！

4

2 に答える 2

0

2つのチケットは次のとおりです。

{1、3、5、X}

{2、4、5、X}

ここで、Xは、解に影響を与えない任意に選択された数値です。

于 2012-10-31T16:50:12.923 に答える
0

  1. これは非効率な 10 枚のチケットのリストです

    {1, 2, 3, 6}
{1, 2, 4, 6}
{1, 2, 5, 6}
{1, 3, 4, 6}
{1, 3, 5, 6}
{1, 4, 5, 6}
{2, 3, 4, 6}
{2, 3, 5, 6}
{2, 4, 5, 6}
{3, 4, 5, 6}

  2. ム。勝つためには、4 つのうち 2 つを一致させる必要があります。したがって、1 と 3 が発生する場合ではなく、特定の 3 つのセットが発生し、そのうちの 2 つだけを一致させる必要がある場合です。

  3. これが最適だと思います。

    {1, 2, 3, 4}

しかし、私は 4 つを選択できると完全に確信しているわけではありません。チケットごとに 3 つしか選択できない場合、最適なセットは次のようになります。

    {1, 2, 3}
    {2, 3, 4}
于 2012-10-31T15:55:02.483 に答える