16 2色のラインアップv2

This is the follow-up question for
16 Two Colored Line Up

enter image description here

今度は、あなたはそれを解くべきではありませんが、それを解決するためにステップ数を最大にする各四角形について最悪の可能な配置を見いだします。

したがって、最悪の場合のシナリオに対して正しい例を得るための最適な最小ステップ数はいくらですか?

enter image description here

ヒント:自分の場所ではなく同じ色の番号を切り替える場合は、少なくとも16の移動が必要です。

誰もが1週間で解決できなければ、私は答えを分かち合うつもりです。

ベストアンサー

私はそれが常に16の動きで行うことができると信じています。まず、いくつかの補題。

    $ nc $で$ n $は要素の数、$ c
    $は順列のサイクル数です(すべての順列はいくつかのサイクルに分割できますが、サイクルは1つの要素だけシフトされる)。つまり、色の制限がなければ、最大で15回のスワップで解決できます。

  1. 各色の$ n $要素と$ n $要素があり、要素がそれぞれの色だけで混合されている場合、$ 2n
    $の動きで解決できます。これは次のように誘導で示されます:

2a。 $ n = 2 $に対しては真であり、最初のスワップは任意のペアであることに注意してください。

2b。 $ n leq k-1 $が真であるとします(最初の移動は任意のスワップが可能です)。

2c. Consider $n=k$. Make any swap (say 1<->2), and then
swap 1 and 2 into their correct positions (for a total of 3 moves).
We then have $2(k-1)$ squares left unsolved, and we have already
made an initial swap (whatever was in position 1 with whatever was
in position 2), so we have (by 2b) $2(k-1)-1$ moves left. Total
moves is therefore $2k$. QED.

この制限は、両側が1シフトのサイクルである場合に正確に満たされます。

  1. 各色の$ 2n $四角形と$ m( leq n)$が逆の色になっているとします。これらは$ 2m
    $の動きで右の四角に置くことができます(あなたは順序を慎重にする必要があるかもしれません).2の状況を残して、$
    2(n-m)$の動きで解くことができます。 QED

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です