◆愛知県 Y.M.Ojisan さんからのコメント。
「部分集合」の問題の解を一定のパターンのシフトで得ようとしたとき、この問題とそれはループかオープンかの違いを除いて同じ問題と考えられます。
まずは、PCの限界内で本問題を腕力で計算した結果を下表に示します。
数列A(１〜N)はビットパターンで示します。
左端を１としてビット位置がA(１〜N)値であるとして読みます。
任意シフトとのAND結果の１の数が３個以内｛：A(j)-A(i)=kとなるような、(i,j)の組み合わせは高々3通り。｝になっています。
この表では最初に見つかった最小長のものだけ示しています。
「部分集合」の問題設定からA(N)-A(N-3)はNの一次式のオーダーを予想していましたがそれより多いようです。
また３とびのパターンの繰り返しも弱いようです。
さらにA(N-３)数列のパターンの上にA(N)数列のパターンが作れるわけではないようで、漸化的な式の発見も困難です。
これはかなり難問ではないかと思います。
◆出題者のコメント。
コメントありがとうございます。
Y.M.Ojisan さんさすがです。
全て見抜かれてしまいました。
やっぱり、難しいですかね。
自分も色々考えてみたんですけれど、実際に計算する以外に方法が思い浮かびませんでした。
本来、出題者としてはあらかじめ答えを考えてから出題するべきでしょうが、どうも、私はそこらへんがおろそかになってしまっているようです。