No. 7≫ No.8 最新レスです
あれれ
2015/01/30 11:21
答えを発表します。
(n-m)が最大になるのはn=8,m=3のときです。
最短手順の一例は、
1回目1枚
2回目8枚
3回目4枚
4回目8枚
5回目1枚
6回目8枚
7回目4枚
8回目8枚
解法はすべて書くと長くなりますので色々省略します。
確実に成功できる手順が存在するn,mの条件を調べてみます。
m枚表の状態でn枚ひっくり返すと、(n-m)枚が表の状態になります。
表向きのコインがm枚または(n-m)枚になったら終了と考えても手順の存在については同じです。
ある時点の表向きのコインの枚数として可能な枚数を表す関数fを考えます。
表向きになっている枚数がk枚である可能性があればf(k)=1
その可能性がない場合はf(k)=0
と定義します。kは0以上n以下の整数です。
最初はすべての枚数が可能ですのでf(0)=f(1)=...=f(n)=1です。
任意のkについてf(k)=f(n-k)が成り立っています。
操作の対称性から任意の時点でf(k)=f(n-k)が成り立ちます。
m<n/2の場合を考えます。
最終的にf(m),f(n-m)のみ1で他のfの値は0となります。
その直前にはa枚のコインが表で、b枚のコインをひっくり返したとします。
その結果x枚のコインが表の状態になるとします。
あるaについてxの取り得る値が複数ある場合
xの値は2刻みなので、mと(n-m)の差は2。
m=n/2-1,n-m=n/2+1で、nは偶数です。
min(a,b)=1またはmax(a,b)=n-1ですので、
一つ前のfについて、次の4通りのいずれかが成り立ちます。
1.f(n/2)のみが1
2.f(n/2-1),f(n/2),f(n/2+1)のみが1
3.f(1),f(n-1)のみが1
4.f(1),f(n/2-1),f(n/2),f(n/2+1),f(n-1)のみが1
この直前にはa枚のコインが表で、b枚のコインをひっくり返し、
結果x枚のコインが表の状態になるとします。
1の場合
xの取り得る値が一つだけですので、
min(a,b)=0,またはmax(a,b)=n
b=0,nであれば1回前に終わっていたことになりますので不適です。
よってaは0またはn。
一つ前のfについて次のどちらかが成り立ちます。
・f(0),f(n)のみが1
・f(0),f(n/2),f(n)のみが1
4の場合
あるaについてxの取り得る値が1,n/2を含む場合、(n,m)=(6,2)
あるaについてxの取り得る値が1,n/2-1を含む場合、(n,m)=(8,3)
こんな感じですべての場合を調べると、(n,m)の組み合わせは有限個に絞れます。
(n-m)が大きいものから実際に手順が存在するかどうか確認すると、
(n,m)=(8,3)の場合に(n-m)が最大になることが分かります。
確実に成功する手順が存在する(n,m)の組み合わせは、
(n,m)=(1,1),(2,1),(2,2),(3,1),(3,2),(4,1),(4,2),(4,3),(5,2),(5,3),(6,2),(6,4),(8,3),(8,5)
の14通りです。
(n-m)が最大になるのはn=8,m=3のときです。
最短手順の一例は、
1回目1枚
2回目8枚
3回目4枚
4回目8枚
5回目1枚
6回目8枚
7回目4枚
8回目8枚
解法はすべて書くと長くなりますので色々省略します。
確実に成功できる手順が存在するn,mの条件を調べてみます。
m枚表の状態でn枚ひっくり返すと、(n-m)枚が表の状態になります。
表向きのコインがm枚または(n-m)枚になったら終了と考えても手順の存在については同じです。
ある時点の表向きのコインの枚数として可能な枚数を表す関数fを考えます。
表向きになっている枚数がk枚である可能性があればf(k)=1
その可能性がない場合はf(k)=0
と定義します。kは0以上n以下の整数です。
最初はすべての枚数が可能ですのでf(0)=f(1)=...=f(n)=1です。
任意のkについてf(k)=f(n-k)が成り立っています。
操作の対称性から任意の時点でf(k)=f(n-k)が成り立ちます。
m<n/2の場合を考えます。
最終的にf(m),f(n-m)のみ1で他のfの値は0となります。
その直前にはa枚のコインが表で、b枚のコインをひっくり返したとします。
その結果x枚のコインが表の状態になるとします。
あるaについてxの取り得る値が複数ある場合
xの値は2刻みなので、mと(n-m)の差は2。
m=n/2-1,n-m=n/2+1で、nは偶数です。
min(a,b)=1またはmax(a,b)=n-1ですので、
一つ前のfについて、次の4通りのいずれかが成り立ちます。
1.f(n/2)のみが1
2.f(n/2-1),f(n/2),f(n/2+1)のみが1
3.f(1),f(n-1)のみが1
4.f(1),f(n/2-1),f(n/2),f(n/2+1),f(n-1)のみが1
この直前にはa枚のコインが表で、b枚のコインをひっくり返し、
結果x枚のコインが表の状態になるとします。
1の場合
xの取り得る値が一つだけですので、
min(a,b)=0,またはmax(a,b)=n
b=0,nであれば1回前に終わっていたことになりますので不適です。
よってaは0またはn。
一つ前のfについて次のどちらかが成り立ちます。
・f(0),f(n)のみが1
・f(0),f(n/2),f(n)のみが1
4の場合
あるaについてxの取り得る値が1,n/2を含む場合、(n,m)=(6,2)
あるaについてxの取り得る値が1,n/2-1を含む場合、(n,m)=(8,3)
こんな感じですべての場合を調べると、(n,m)の組み合わせは有限個に絞れます。
(n-m)が大きいものから実際に手順が存在するかどうか確認すると、
(n,m)=(8,3)の場合に(n-m)が最大になることが分かります。
確実に成功する手順が存在する(n,m)の組み合わせは、
(n,m)=(1,1),(2,1),(2,2),(3,1),(3,2),(4,1),(4,2),(4,3),(5,2),(5,3),(6,2),(6,4),(8,3),(8,5)
の14通りです。