◆東京都 Asami さんからの解答。
【問題１】
０１０,１０１,１１１,０００
【問題３】
下から１段目、２段目と名付けていく。
(つまり、０,１配列がｋ個ある段がｋ段目となる)
最終的に当たりすなわち“１”となるためには、２段目は０１,１０の２通り。
今、最終的に当たりとなるためのｎ−１段目の配列が２n-2通りあったとする。
ある１つの配列から、上の段に行くとき、一番左の数が決定すれば、順次定まってしまうから、その場合２通りある。
下の段の配列が異なれば、上の段配列は決して一致しないわけだから、
ｎ−１段目の配列が２n-2通りであれば
ｎ段目は２・２n-2通り
すなわち２n-1通りの配列が存在する。
ところでｎ段目のすべての配列は２n通りあるから、最終的に当たりとなる配列は丁度半分存在し、当然残り(はずれとなる)配列も半分でなければならない。
【問題２】は問題３から明らか
【問題４】
とりあえず、以下の規則を見つけましたが、方法としてはあまり簡潔でない(進歩していない)ので、出直してきます(^_^;;)。
＜方法＞
連続する２つを足して下の段に置くことを繰り返す。
例えば０,１,０,０,０,１,１,１は
1,1,0,0,1,2,2 2,1,0,1,3,4 3,1,1,4,7 4,2,5,11 6,7,16 13,23 36 |
最後が偶数なら当たり。奇数ならはずれ。
【感想】
なかなか斬新な問題ですね。とても面白い問題だと思います。
【問題３および２】の別解
初めの(n-1)文字を固定すると、最後の文字を入れ換えれば、当たりはずれが入れ替わる。
つまり、初めの(n-1)文字を固定するたびに、当たりはずれが１つずつ現れるので、当たり(はずれ)となる配列は２n-1通りあるといえる。
【問題３,２】に関してはこの方が簡潔かな。
◆東京都 Asami さんからの解答。
【問題４】の解決のための、数ある中の１つの方針(アイディア)を書きます。
↑の【４】の考え方を押し進めれば、
“ｎが２のベキであるとき”
初めの数の総和≡0(mod2)⇒当たり
初めの数の総和≡1(mod2)⇒はずれ
と分かります(帰納的に)。
従って、ｎが２のベキであるか、そうでないかで場合分けして考えていって、これを突き詰めれば、解決はほど遠いことではない気がします。
おまけ。【問題２,３】のもうひとつの考え方。
“数のセット”の列を上から１段,２段……と呼ぶことにする。
次に、“１段目の右から１番目,２段目の右から１番目,…,ｎ段目の(当然)右から１番目の数のセット”を“ナナメ１段”と呼び、“１段目の右から２番目,２段目の右から２番目,…,n-1段目の(当然)右から１番目の数のセット”を“ナナメ２段”と読んで、以下同様にナナメｋ段を
定義する。
さて、“１段目の数のセット”が決まれば、一意的に“ナナメ１段の数のセット”が決まり、逆に“ナナメ１段の数のセット”が決まれば“１段目の数のセット” が一意的に決まる。
(∵順に“ナナメ２段”,“ナナメ３段”……が決まるから！)
このことは、
“１段目のセット”と“ナナメ１段のセット”が１対１対応になっていることを意味している。
従って、“当たり”となるようなｎ文字(＝１段目)の配列は、 一番下側の数が“１”となるような、起こり得るすべての“ナナメ１段のセット”を考えれば良く、それは２n-1通り存在する。(はずれも同様)
Ｐ.Ｓ.
つまり、ナナメの段から眺めていっても、題意の条件を満たす列を成しているわけです！
(この性質も面白いと思いました！)
◆東京都 Asami さんからの解答。
１段目に２k＋α (0≦α＜２k)個あるとします。
初めの２k個と残りのα個とにわけて、α個の真上に初めの２k個のコピーを書きます。(図１)
10101111 ……コピー 10101111 100001 ……残りα個 (図１)すると、２k段目にあるα+１個の配列は以下のようにして決まります。
わかりやすくするために、(図１)の14個の配列で考えます。
まず、最初の８個の和≡0 (mod2)なので８段目の一番左にある数は“1”に決まります。
次に、αとコピーとで順次左から見ていき、一致しているか異なるかで判別します。
左から１番目は1
1
と一致しているので、８段目の左から２番目にある数は、８段目の左から１番目にある数と同じものを書きます。
(すなわち“1”)
左から２番目は0
0
と一致しているので、８段目の左から３番目にある数は、８段目の左から２番目にある数と同じものを書きます。
(すなわち“1”)
左から３番目は1
0
と異なるので、８段目の左から４番目にある数は、８段目の左から３番目と違う数を書きます。
(すなわち“0”)
左から４番目は0
0
と一致しているので、８段目の左から５番目にある数は、８段目の左から４番目にある数と同じものを書きます。
(すなわち“0”)
………
順次これを繰り返すことで、８段目は1110011と決定します！
この方法だと、文字数がかなり少ない場合に帰着されるのでけっこういいのではないでしょうか？
(１段目が２k＋α個なら、高々k＋1回の上記の操作で当たりはずれが決定する)
◆富山県 いくまる さんからの解答。
数の並びをx,yで表し、xから題意の操作でyを作ることを、関数fを用いて、
y=f(x)と表す。
【問題２】
数の並びxに対し0と1をすべて入れ替えたものを-xとすると、任意のxに対し
f(x)=f(-x)が成り立つ。
よってxがあたりのとき、-xもあたりとなる。
すべてのあたりのxに対し-xを組として対応させることが出来るので、あたりの数は偶数個である。
【問題３】
fの逆関数f-1を考えると、この関数は異なる２価の値を与える。
（f-1(x)の一方をyとすると、もう一方は-yである。）
またx1≠x2のとき、f-1(x1)≠f-1(x2)が成り立つ。
よって関数{f-1}nは2n価の関数となる。
n個の数の並びのうち、あたりのものとはずれのものはそれぞれ
{f-1}n-1(1)、{f-1}n-1(0)である。
この数はともに2n-1個。
（もちろん２つ併せると2n個)
問題４はひ・み・つ。
◆神奈川県 ch3cooh さんからの解答。
問４の答えは、n C m(コンビネーション,パスカルの３角形)の奇数の部分のパリティをとり、
答えが偶数なら'1'
(n C mの最下位の偶奇の判定であればもっと簡単な数式を得ることも出来ると思うが、式を示すのが面倒であるため省略)
●上の答えの証明
0,1のex-orを計算しているが、各々の値が影響を与える範囲などを考えるとAsamiさんの考え方が成立する。
これを一気に求めるものとすると、
各々の値に対し、n C mの値を掛けてやることになる。
ここで、最終的に使用する値は最下位の桁のみであることに注目、
n C mの値が偶数の場合、答えに影響を与えないため、計算は不要、
よって、最小の計算のみとなると上の答えになる(と思う)
元の数列の長さが２n-1の場合、すべての値のパリティが必要になるような気がする。
「感想」
擬似的なパスカルの３角形
(p->p, p+p->n, p+n->p, n+p->p, n+n->n)
を１６以上並べると、その作り出す模様は結構きれいだと思う。
◆神奈川県 ch3cooh さんからの解答。
●プログラム
* MAX_RESULTの値を変更することで、ある程度大きい値まで対処可能
* きれいな３角形にするために、スペースを利用しています。
コンパイラを持っていない方のために、50までの答えを示します。#include #define MAX_RESULT 50 #define CHAR_P 'p' #define CHAR_N 'n' int main( void ) { int n, i ; int table[MAX_RESULT] ; table[0]= 1 ; printf( " 1 :" ) ; for( i= 1 ; i< MAX_RESULT ; i++ ) putchar( ' ' ) ; putchar( CHAR_P ) ; putchar( '\n' ) ; for( n= 2 ; n< MAX_RESULT ; n++ ) { table[n-1]= table[n-2] ; for( i= n-2 ; i> 0 ; i-- ) table[i]= table[i]^table[i-1] ; printf( "%3d :", n ) ; for( i= n ; i< MAX_RESULT ; i++ ) putchar( ' ' ) ; for( i= 0 ; i< n ; i++ ) { putchar( table[i]?CHAR_P:CHAR_N ) ; putchar( ' ' ) ; } putchar( '\n' ) ; } return 0 ; }
表示する文字としては、'p'と'n'よりも、格差の激しい'0'と'.'のようなものの方が視覚効果が良いと思います。
(置換したものも示します。)
(プログラムでは、CHAR_P,CHAR_Nに定義している値を変更して下さい。)
1 : p 2 : p p 3 : p n p 4 : p p p p 5 : p n n n p 6 : p p n n p p 7 : p n p n p n p 8 : p p p p p p p p 9 : p n n n n n n n p 10 : p p n n n n n n p p 11 : p n p n n n n n p n p 12 : p p p p n n n n p p p p 13 : p n n n p n n n p n n n p 14 : p p n n p p n n p p n n p p 15 : p n p n p n p n p n p n p n p 16 : p p p p p p p p p p p p p p p p 17 : p n n n n n n n n n n n n n n n p 18 : p p n n n n n n n n n n n n n n p p 19 : p n p n n n n n n n n n n n n n p n p 20 : p p p p n n n n n n n n n n n n p p p p 21 : p n n n p n n n n n n n n n n n p n n n p 22 : p p n n p p n n n n n n n n n n p p n n p p 23 : p n p n p n p n n n n n n n n n p n p n p n p 24 : p p p p p p p p n n n n n n n n p p p p p p p p 25 : p n n n n n n n p n n n n n n n p n n n n n n n p 26 : p p n n n n n n p p n n n n n n p p n n n n n n p p 27 : p n p n n n n n p n p n n n n n p n p n n n n n p n p 28 : p p p p n n n n p p p p n n n n p p p p n n n n p p p p 29 : p n n n p n n n p n n n p n n n p n n n p n n n p n n n p 30 : p p n n p p n n p p n n p p n n p p n n p p n n p p n n p p 31 : p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p 32 : p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p p 33 : p n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n p 34 : p p n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n p p 35 : p n p n n n n n n n n n n n n n n n n n n n n n n n n n n n n n p n p 36 : p p p p n n n n n n n n n n n n n n n n n n n n n n n n n n n n p p p p 37 : p n n n p n n n n n n n n n n n n n n n n n n n n n n n n n n n p n n n p 38 : p p n n p p n n n n n n n n n n n n n n n n n n n n n n n n n n p p n n p p 39 : p n p n p n p n n n n n n n n n n n n n n n n n n n n n n n n n p n p n p n p 40 : p p p p p p p p n n n n n n n n n n n n n n n n n n n n n n n n p p p p p p p p 41 : p n n n n n n n p n n n n n n n n n n n n n n n n n n n n n n n p n n n n n n n p 42 : p p n n n n n n p p n n n n n n n n n n n n n n n n n n n n n n p p n n n n n n p p 43 : p n p n n n n n p n p n n n n n n n n n n n n n n n n n n n n n p n p n n n n n p n p 44 : p p p p n n n n p p p p n n n n n n n n n n n n n n n n n n n n p p p p n n n n p p p p 45 : p n n n p n n n p n n n p n n n n n n n n n n n n n n n n n n n p n n n p n n n p n n n p 46 : p p n n p p n n p p n n p p n n n n n n n n n n n n n n n n n n p p n n p p n n p p n n p p 47 : p n p n p n p n p n p n p n p n n n n n n n n n n n n n n n n n p n p n p n p n p n p n p n p 48 : p p p p p p p p p p p p p p p p n n n n n n n n n n n n n n n n p p p p p p p p p p p p p p p p 49 : p n n n n n n n n n n n n n n n p n n n n n n n n n n n n n n n p n n n n n n n n n n n n n n n p 1 : 0 2 : 0 0 3 : 0 . 0 4 : 0 0 0 0 5 : 0 . . . 0 6 : 0 0 . . 0 0 7 : 0 . 0 . 0 . 0 8 : 0 0 0 0 0 0 0 0 9 : 0 . . . . . . . 0 10 : 0 0 . . . . . . 0 0 11 : 0 . 0 . . . . . 0 . 0 12 : 0 0 0 0 . . . . 0 0 0 0 13 : 0 . . . 0 . . . 0 . . . 0 14 : 0 0 . . 0 0 . . 0 0 . . 0 0 15 : 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 16 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 17 : 0 . . . . . . . . . . . . . . . 0 18 : 0 0 . . . . . . . . . . . . . . 0 0 19 : 0 . 0 . . . . . . . . . . . . . 0 . 0 20 : 0 0 0 0 . . . . . . . . . . . . 0 0 0 0 21 : 0 . . . 0 . . . . . . . . . . . 0 . . . 0 22 : 0 0 . . 0 0 . . . . . . . . . . 0 0 . . 0 0 23 : 0 . 0 . 0 . 0 . . . . . . . . . 0 . 0 . 0 . 0 24 : 0 0 0 0 0 0 0 0 . . . . . . . . 0 0 0 0 0 0 0 0 25 : 0 . . . . . . . 0 . . . . . . . 0 . . . . . . . 0 26 : 0 0 . . . . . . 0 0 . . . . . . 0 0 . . . . . . 0 0 27 : 0 . 0 . . . . . 0 . 0 . . . . . 0 . 0 . . . . . 0 . 0 28 : 0 0 0 0 . . . . 0 0 0 0 . . . . 0 0 0 0 . . . . 0 0 0 0 29 : 0 . . . 0 . . . 0 . . . 0 . . . 0 . . . 0 . . . 0 . . . 0 30 : 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 . . 0 0 31 : 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 32 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 33 : 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 34 : 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 35 : 0 . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . 0 36 : 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 37 : 0 . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 . . . 0 38 : 0 0 . . 0 0 . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 . . 0 0 39 : 0 . 0 . 0 . 0 . . . . . . . . . . . . . . . . . . . . . . . . . 0 . 0 . 0 . 0 40 : 0 0 0 0 0 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 41 : 0 . . . . . . . 0 . . . . . . . . . . . . . . . . . . . . . . . 0 . . . . . . . 0 42 : 0 0 . . . . . . 0 0 . . . . . . . . . . . . . . . . . . . . . . 0 0 . . . . . . 0 0 43 : 0 . 0 . . . . . 0 . 0 . . . . . . . . . . . . . . . . . . . . . 0 . 0 . . . . . 0 . 0 44 : 0 0 0 0 . . . . 0 0 0 0 . . . . . . . . . . . . . . . . . . . . 0 0 0 0 . . . . 0 0 0 0 45 : 0 . . . 0 . . . 0 . . . 0 . . . . . . . . . . . . . . . . . . . 0 . . . 0 . . . 0 . . . 0 46 : 0 0 . . 0 0 . . 0 0 . . 0 0 . . . . . . . . . . . . . . . . . . 0 0 . . 0 0 . . 0 0 . . 0 0 47 : 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 . . . . . . . . . . . . . . . . . 0 . 0 . 0 . 0 . 0 . 0 . 0 . 0 48 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 49 : 0 . . . . . . . . . . . . . . . 0 . . . . . . . . . . . . . . . 0 . . . . . . . . . . . . . . . 0