0

長さが 36 のすべての 3 進数 (0 で始まるものを含む) について、1 と 2 の数が正確に等しい、または 2 より 1 だけ多い数はいくつありますか?

例えば:

  • 00 - はい
  • 01 - はい
  • 02 - いいえ
  • 10 - はい
  • 11 - いいえ
  • 12 - はい
  • 20 - いいえ
  • 21 - はい
  • 22 - いいえ

したがって、長さ 2 のすべての 3 進数について、9 つの可能性のうち 5 つが一致します。これは、長さが長くなるにつれて小さくなると考えられます。長さ 3 の場合、27 個中 13 個あります。

2 進数を扱っていた場合、ここで利用できる解決策がいくつかありますが、これらを 3 進数に一般化する方法は明確ではありません。

4

2 に答える 2

1

このプロセスは、組み合わせの演習としては十分に簡単に思えます。[1..18] のすべての N について、36 桁のトリットストリング内の "1" のすべての異なる配置を見つけます。次に、「1」がとらない位置にあるN個の「2」の異なる配置の数を掛け、N-1個の「2」についても掛けます。これらの 36 個の数の合計を求めます。結局のところ、N=0 の場合は 1 を追加します。これは、すべて「0」のトリットストリングです。

36 の長さのトリットストリングにおける N トリットの異なる配置の数は、

36! / N!(36-N)!

問題は頭の体操のように聞こえます。上記をさらに開発していませんが、ショートカットの存在を強く疑っています。

于 2009-01-20T16:43:52.573 に答える
0

私の友人は私に次の答えをくれました.彼は私よりも数学を知っています. これは私の作品ではないため、「コミュニティ」とマークしました。

1/2 に等しいだけでなく、すべての (ほとんどの?) 組み合わせのウェイ数を知る必要があります。たとえば、+18 と -18 を組み合わせて、1 と 2 を同じ数にすることができます。

18
0/0
0/1
...
0/18
1/0
1/1
...
1/17
...
18/0

直接解く方がはるかに簡単に思えます。

0/0
1/0
1/1
2/1
2/2
3/2
3/3
...
18/17
18/18

組み合わせ論を行う

0/0 = 1 way
1/0 = (36C1) = 36 possibilities
1/1 = (36C1) * (36-1C1) = 1260 possibilities
2/1 = (36C2) * (36-2C1) = 21420
2/2 = (36C2) * (36-2C2) = 353430
3/2 = (36C3) * (36-3C2) = 3769920
3/3 = (36C3) * (36-3C3) = 38955840
4/3
4/4
5/4
5/4

18/17 = (36C18) * (36-18C17) = 163352435400
18/18 = (36C18) * (36-18C18) = 9075135300

bc の行を出力するための Perl スクリプト。掛け算と割り算のバランスをとるコードを書くのが面倒なので。

sub print_choose
{
    $n = $_[ 0 ];
    $c = $_[ 1 ];

    if( $c == 0 ) { print "1"; return; }

    for( $j = 0; $j < $c; ++$j ) {
        if( $j ) { print "*"; }
        print $n - $j;
    }
    for( $j = 0; $j < $c; ++$j ) {
        print "/", $c - $j;
    }
}

for( $i = 0; $i <= 18; ++$i ) {
    if( $i > 0 ) {
        print_choose( 36, $i );
        print "*";
        print_choose( 36 - $i, $i - 1 );
        print "\n";
    }

    print_choose( 36, $i );
    print "*";
    print_choose( 36 - $i, $i );
    print "\n";
}


foo.pl | bc | perl -ne '$sum += $_; print "$sum\n"'
1
37
1297
22717
376147
4146067
43101907
335270707
2453494507
14315547787
78370635499
355942682251
1512492877051
5477807830651
18506699821051
54336152794651
148388466850351
357393609196351
798626687482351
1592846228397151
2943019447952311
4906907767305271
7584937293695671
10709305074484471
14094036837005671
17218404617794471
19862100432308071
21750454585532071
22964396541176071
23611832250852871
23913968915368711
24027270164562151
24062676804935101
24071007779140501
24072477951059101
24072641303494501
24072650378629801
于 2009-01-20T17:32:59.977 に答える