|
uchinyan |
|
#42480，#42481，#42485，#42486，#42487
理論的なアプローチは難しそうだったのでプログラムチェックの様子を見ていたのですが， #42486の様子では本当の難問のようですね。 #42485の考え方にしたがって，自分の理解のために少しまとめておくと，次のようになるのでしょうか。 0 〜 3^n - 1 の最大枚数を c(n) とすれば，0 〜 3^(n+1) - 1 の c(n+1) は， 0 〜 3^(n+1) - 1 を， 0 〜 3^n - 1，3^n 〜 2 * 3^n - 1，2 * 3^n 〜 3^(n+1) - 1，の三つの区間に分けて， 0 〜 3^n - 1 には，0 〜 3^n - 1 の解の一つをそのまま 2 * 3^n 〜 3^(n+1) - 1 には，0 〜 3^n - 1 の解の一つの各々の数に 2 * 3^n を足したもの 3^n 〜 2 * 3^n - 1 には，0 〜 3^n - 1 と 2 * 3^n 〜 3^(n+1) - 1 の数の平均にならないもの を入れるようにすれば，題意を満たすものが作れて，このとき， 0 〜 3^n - 1 は c(n)，2 * 3^n 〜 3^(n+1) - 1 は c(n)，3^n 〜 2 * 3^n - 1 は d(n) とすれば， c(n+1) >= 2 * c(n) + d(n) になります。 問題は，不等号と d(n) ですが，プログラムによる実験では， c(n+1) = 2 * c(n) + d(n)，d(n) = 0 又は 1 程度 となりそうですね。 もし， 0 〜 3^n - 1 には，0 〜 3^n - 1 の解の一つをそのまま 2 * 3^n 〜 3^(n+1) - 1 には，0 〜 3^n - 1 に入れたのと同じもの を入れるとすれば，3^n 〜 2 * 3^n - 1 には入れられず d(n) = 0 になります 常にこうすることにして不等号を等号にすれば， c(n+1) = 2 * c(n)，c(n) = 2^n これはマサルさんの期待していた予想解で今回の出題のベースになったもので，3 進法解釈が容易です。 しかし，実際には，最大よりもむしろ，下界，だったようです。 もし，2 * 3^n 〜 3^(n+1) - 1 を調整して常に d(n) = 1 とでき不等号が等号になるならば， c(n+1) = 2 * c(n) + 1，c(n) = 3 * 2^(n-1) - 1 これは，n = 1, 2, 3 では正しく，#42485のおーちゃんさんの最初の予想ですが， それ以降はこれより小さくなるようです。これは，d(n) = 0 が増える，多くが 0，を意味します。 つまり，理論上ではなく，あくまでの今までのプログラムでの実験の予想ですが， この値は，上界，の一つのようです。 ちなみに，この場合の 0 〜 728 に対するのは c(6) = 95 です。 さらに， n = 1, 2, 3，c(n+1) = 2 * c(n) + 1，n >= 4，c(n+1) = 2 * c(n) と仮定すると， n = 1, 2, 3，c(n) = 3 * 2^(n-1) - 1，n >= 4，c(n+1) = 11 * 2^(n-3) となり，0 〜 728 に対するのは c(6) = 88 となり，#42485の最初の枚数と一致します。 しかしながら，#42487によると 90 が可能だろう，ということなので， どこかでポツポツと d(n) = 1 になるものと思われます。 それとも全く異なるパターンなのでしょうか？ |
|
ネコの住む家
10月4日（土） 14:45:30
42489 |