算術平均を最小化できますか？

Question

しましょう $n$正の整数である。がある$2n$ $1$sホワイトボードに書かれています。ジョンは次の手順を繰り返します$3n$ 次のように、回：

2つの数字を選択してください $x,y$ ボード上で、それらのそれぞれをに置き換えます $2x+y, 2y+x$ それぞれ。

彼の目標は、数値の算術平均を可能な限り低くすることです。彼の最良の戦略は何ですか、そして最良の算術平均は何ですか？

---

数学オリンピックトレーニングの授業での問題。いくつかの変更が加えられています。

---

ヒント：

IMO問題で一般的に使用される不等式を使用します。

Answer 1

これは一見しただけでは明らかではないことに注意してください。たとえば、怠惰な仮定

小さいほど良い

正しくありません。例$n=2$。につながる最初のステップの後すでに$1,1,3,3$ 最適な次のステップは

$1,1$ または $3,3$

だがしかし

$1,3$ 小さいのに $3,3$。

実際の証明の専門性に入る前に、まずトリックが何であるかを述べさせてください。

秘訣は追跡にあります：考えないでください $x\mapsto 2x+y$、考えてみてください $x\mapsto x+2y$！

正式な証明（私の 'orrbileフォーマットを修正してくれた@bobbleに感謝します）：

表記法：同じラベルのセットを維持すると便利です $\alpha,\beta,\gamma,...$ 進化する数字について、非常に正式に私たちは州を持っています $X(k) = X_\alpha(k),X_\beta(k),...$ どこ $k$は歩数です。これを大幅に省略します$a = X_\alpha(k),b = X_\beta(k)$ ラベルは平均に影響を与えないため、各ステップで選択できます。 $S^\times_{\alpha\beta}:a,b \mapsto a+2b,b+2a$ 対。 $S^=_{\alpha\beta}:a,b \mapsto 2a+b,2b+a$。（最初のオプションを使用し、2番目のオプションはまったく使用しません。）もちろん、参照されていない番号は変更されないままであると理解されます。また、実際に処理せずに交換できる必要があります。$\times_{\alpha\beta}: a,b \mapsto b,a$。これは純粋に本の保管であるため、この種のステップはカウントされないことが理解されます$k$。

「常に2つの最小数を取る」という貪欲な戦略が最適であると私たちは主張します。これは最後のステップで明らかです。貪欲が最後に最適であることが示されていると仮定します$k$ 状態に関係なくステップしますが、状態が存在します $X(3n-(k+1))$最小の2つを取ることは最適ではありません。最適なステップを$S^\times_{\alpha\beta}$。仮定により、最適な次のステップは貪欲なものになるように選択できます$S^\times_{\gamma\delta}$。3つのケース：

1）$\alpha=\gamma,\beta=\delta$：最初のステップを貪欲ではないと仮定したため、そうすることはできません。

2）$\alpha\ne\gamma,\beta\ne\gamma,\alpha\ne\delta,\beta\ne\delta$ 明らかにそうすることはできません

$S^\times_{\alpha\beta} \circ S^\times_{\gamma\delta}=S^\times_{\gamma\delta} \circ S^\times_{\alpha\beta}$そして、最初のステップでは貪欲が最適ではないと仮定しました。

最後のケースを解決する前に、半順序を紹介しましょう$X(k)<X'(k)$ どこ $<$ 手段 $X_\psi(k)\le X'_\psi(k)$ すべてのために $\psi \in \{\alpha,\beta,...\}$そして、不等式の少なくとも1つは厳密です。明らかに、$X(k)<X'(k)$ そして両方とも同じステップにかけられます $X(k+1)<X'(k+1)$。

3）$\alpha\ne\gamma,\beta=\delta$ それから仮定によって $c<a$。直接計算$X(3n-(k-1))$ 収量

$S^\times_{\beta\gamma} \circ S^\times_{\alpha\beta}: a,b,c \mapsto a+2b,b+2a+2c,4a+2b+c$

最適であると想定された元の2つのステップを使用する場合。

それらを交換し、その後ラベルも交換すると$\alpha$ そして $\gamma$ 我々が得る

$\times_{\alpha\gamma}\circ S^\times_{\alpha\beta} \circ S^\times_{\beta\gamma}: a,b,c \mapsto c+2b,b+2a+2c,4c+2b+a$

この状態は、コンポーネントごとに最適と思われる手順で得られる状態よりも優れているか等しいため、これは矛盾しています。 $\square$

ほとんど忘れてしまった：もちろん、最小値は、

27

Answer 2

免責事項：これは生意気な答えです。

関数はすべての正の整数に対して厳密に増加しているため、簡単な答えは、各段階で関数に最小の数値を供給することです。これにより、$n$ （1,1）から（3,3）をとるアプリケーション、別の $n$ （3,3）から（9,9）までの操作、および最後の操作 $n$ （9,9）から（27,27）までの操作で、平均27です。

ただし、不可解な答えは、平均の定義をより慎重に選択する必要があるということです。平均を選択する代わりに、モードを選択する必要があります（この場合、中央値も同様に機能します）。次に、以外の$n=2$ （上記の「単純な」アルゴリズムを使用します）、関数を適用します $3n$同じ数のペアに時間をかけます。これらの数は$3^{3n}$、ただし、残りはすべて1のままです。

の平均 $n=1$ そして $n=2$ まだ27ですが $n>2$、平均（中央値または最頻値）は1になりました。

敷物の下で2つの異常を一掃できますか？ええ、そうです、パズルの角度をさらに押しれば。問題の説明は次のとおりです。

彼の目標は、数値の平均をできるだけ低くすることです。彼の最高の戦略は何ですか、そして最高の平均は何ですか？

彼らがどの「数字」を参照しているかは述べられていないので、数字として中央値のシーケンス（メディア？）を選びましょう：27、27、1、1、1、...。もちろん、この無限シーケンスの中央値または最頻値は1です。

したがって、最良の平均は、生意気な戦略を使用した場合は1（または、単純な戦略を使用した場合は27）です。

Answer 3

各ステップで合計が2 *（x + y）増加します。特定のステップでの合計の最小の増加は、利用可能な最小の2つの数値を取得した場合であることは明らかです。しかし、これは欲張りアルゴが最良であることを示すには十分ではありません。

y = x + dを取り、3x + d、3x + 2dに変換した後に数値を書き換えます。ここで、別の数w、w = x + eを導入します。e <d（およびe> = 0）。後で別の操作を行うと、3x + 2d、5x + 2e + d、7x + e + 2dになります。これらの数値を3x + 2e、5x + e + 2d、7x + 2e + dと比較してください。最初にxとwを混合し、次にyを混合に追加します。違いは2 *（de）です。-（de）; （de）; 合計は明らかに欲張りアルゴリズムを支持します。dが大きいと仮定しても、欲張りでない場合は第2項が実際に最小になりますが、差は2x + d、-（2x + e）、de-ですが、欲張りでない場合は第2項が再び小さくなります。この場合、最小の2項の合計は、再び欲張りアルゴリズムを支持します。

すべての場合において、すべての数値が非欲張りアルゴリズムよりも欲張りで小さい演算を見つけることはできませんが、上記は、最小の2の合計がすでに欲張りアルゴリズムを支持していることを示しており、これで十分だと思います。