[規則性]0〜13の整数が書かれたカードが1枚ずつ、合計14枚あります。その中から、次の条件に合うようにしながらできるだけ多くのカードを取り出すことを考えます。条件:「取り出されたカードの中から3枚のカードを選び出して小さい順に並べる。このとき、どんな取り出し方をしても隣どうしの数の差が等しくならない。」この場合は、0、1、3、4、9、10、12、13の書かれたカードを取り出せば、上の条件に合いますね。0〜121の整数が書かれたカードが1枚ずつ、合計122枚あります。その中から上の条件に合うようにできるだけ多くのカードを取りだすとすると、全部で何枚のカードを取り出すことができるでしょうか。2.解答例1(長野美光さん、Gouさん、ありっちさん、ταροさん、AUさん、うっしーさん、高橋道広さん、トトロ@Nさん、糸瀬善人さん、ふぇるまーさん、ハラギャーテイさん、有無相生さん、M.Hossieさん、H.Takaiさん、他多数)0、1からはじめて、条件に合うカードナンバーを下図のように次々と求めていきます。(図では条件に合わない場合の3枚のカードを補足しています。)図1すると、下図のとおりになります。図2従って、0から121までのカードからは、0、1、3、4、9、10、12、13、27、28、30、31、36、37、39、40、81、82、84、85、90、91、93、94、108、109、111、112、117、118、120、121の32枚が条件を満たすことが分かります。条件に合うカード番号を見つけていくときに、カード番号の差の規則性に注目していけば、比較的容易に求まります。(ただし、何人かの方が対象性に言及していますが、33枚目の41、49枚目の122など必ずしも対象性に当てはまらないものがあります。10000、10001、10010、10011、10100、10101、10110、10111、11000、11001、11010、11011、11100、11101、11110、11111のように、2の数字を使わないものが並びます。これらを、2進数とみなすと、0から11111(10進数では0から31)の32通りあることが分かります。これらから任意の3つの番号を選んだとき、隣り合う数字の差が等しくならないことは次のようにして分かります。3つの数字を小さい順にa、b、cとすると、隣り合う数字の差が等しくなるのは、b−a=c−b、すなわちa+c=2b。ところが、bの各桁の数字は、0また1ですから2倍すると、0または2で、桁上がりはありません。(例えば、b=1010のとき、2b=2020)従って、2bの各桁について、2bの桁が0のとき:a、cの同じ桁も02bの桁が2のとき:a、cの同じ桁は1でなくてはなりません。ところがこれはa=c(上記例では、a=c=1010)を意味しますので、不適です。よって、a+c=2bとなることはあり得ません。次に、2の数字が含まれる任意のcに対しては、a+c=2bとなるa、b(2を含まない番号)が必ず1組は存在することが次のようにして分かります。c=cncn-1・・・c1c0に対して、a=anan-1・・・a1a0、b=bnbn-1・・・b1b0を次のように定めます。(図3参照)ck=0のとき:ak=0、bk=0ck=1のとき:ak=1、bk=1ck=2のとき:ak=0、bk=1(例えば、c=121に対して、a=101、b=111)図3このとき、p=a+c、q=2bの各桁は、ck=0のとき:ak=0、bk=0より、pk=0、qk=0ck=1のとき:ak=1、bk=1より、pk=2、qk=2ck=2のとき:ak=0、bk=1より、pk=2、qk=2となり、a+c=2bが成り立つことが分かります。最初の2つのカード番号を0、と1から始めれば、帰納法により2を含む番号は不適であることが分かります。(補足)本問では、解答例1、2等から必ずしも32枚が最大であることは示せません。いうのは、最初の2枚の番号が0と1以外の場合について調べていないからです。上記解法では、0、1、3、4の4枚が最大となりますが、これ以外に0、1、5、6、8という5枚のカード番号が条件を満たします。げんさんによれば0から121までの場合、プログラムの計算により32枚が最大であることが確認されました。