・不等式の本数の節約    ハンニバル・フォーチュン氏

 某所で教わりまして……面白かったのでご紹介させて頂きます。

 有限数列 a[1],a[2],a[3],a[4],a[5],a[6],a[7] およびに 
有限数列 A[1],A[2],A[3],A[4],A[5],A[6],A[7] がある。

 上記各項の値は、それぞれ 100 または 101 であるとする。

 後に述べるような条件を満たす3本の不等式を作って、それらの不等式が成立するとき
には、

  a[n] < A[n]  (1≦n≦7)

が導かれるようにして頂きたい。

 <3本の不等式の条件> 左辺 < 右辺 の形である。

左辺は、a[n] または A[n] の中から 5個をダブらせずに選んだものの総和とする。

右辺は、a[n] または A[n] の中から 5個をダブらせずに選んだものの総和とする。

#条件のうち、5個という縛りがないほうが簡単です。(たとえば、1個でもよい、など)
 そちらを先に考えてもよいかも知れません。

 表現が曖昧かもしれませんので補足させて頂きます。

「左辺は、a[n] または A[n] の中から 5個をダブらせずに選んだものの総和とする。」は、
「左辺は、a[n] または A[n] の14項の中から 5項をダブらせずに選んだものの総和とする。」
と読んでください。

 〈ダブらせずに〉とは、例えば以下が禁止されるという意味です。

A[1]+a[2]+a[3]+a[1]+A[1] (← A[1]がダブっています。)


 らすかるさんからのコメントです。(平成30年10月3日付け)

 惜しくも解けていないのですが、

a[*]+a[*]+A[*]+A[*]+A[*]<a[*]+A[*]+A[*]+A[*]+A[*]
a[*]+a[*]+a[*]+A[*]+A[*]<a[*]+a[*]+A[*]+A[*]+A[*]
a[*]+a[*]+a[*]+a[*]+A[*]<a[*]+a[*]+a[*]+A[*]+A[*]

 (第1式の左辺)=(第2式の右辺)、(第2式の左辺)=(第3式の右辺) という形でしょうか…。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月3日付け)

・私が教えて頂いた3本の不等式の組とは形が一致しません。

・私が教えて頂いた3本の不等式の組以外に、答えがあるかないかについて、残念ながら
 全容をつきとめていません。従いまして、今回らすかるさんからご提示いただいた形のな
 かに解があるかないかについて、私のほうからはなにも申し上げられません。

※素敵なアイデアだとは直感いたしました。私も少し試してみたく思います。


 DD++さんからのコメントです。(平成30年10月3日付け)

 確かに、5個ずつという縛りがなければ簡単ですね。それと同じことを5個ずつという制限の
中でどう実行するかが問題、ですか……。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月3日付け)

 DD++さんのおっしゃる通りと思います。頭の中だけで解きえるパターンとして、1個ずつ、3
個ずつ、7個ずつ、の計3本の不等式のパターンが比較的に簡明かと存じます。

 5個ずつという制限の中での解をみたときに、私は度肝を抜かれました。各々の不等式に
きちんとした理由づけが込められていたものでしたので。
(計算機を回さないで見つけたようです)


 らすかるさんからのコメントです。(平成30年10月3日付け)

 やっと出来ました。一度別の不等式を投稿しましたが、より綺麗な式に直して再投稿しまし
た。

 (1) A[1]+A[2]+a[3]+a[4]+a[5]<a[1]+a[2]+A[3]+A[4]+A[5]

 (2) A[3]+A[4]+a[5]+a[6]+a[7]<a[3]+a[4]+A[5]+A[6]+A[7]

 (3) A[5]+A[6]+a[1]+a[2]+a[6]<a[5]+a[6]+A[1]+A[2]+A[6]


 (1)から、A[1]+A[2]+a[3]+a[4]+a[5]+1≦a[1]+a[2]+A[3]+A[4]+A[5]
 (2)から、A[3]+A[4]+a[5]+a[6]+a[7]+1≦a[3]+a[4]+A[5]+A[6]+A[7]
 (3)から、A[5]+A[6]+a[1]+a[2]+a[6]+1≦a[5]+a[6]+A[1]+A[2]+A[6]

 全式を足して整理すると、 a[5]+a[6]+a[7]+3≦A[5]+A[6]+A[7] なので、

  a[5]<A[5] 、a[6]<A[6] 、a[7]<A[7]

 これと(3)から、 a[1]<A[1] 、a[2]<A[2]

 これと(1)から、 a[3]<A[3] 、a[4]<A[4]


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月4日付け)

 らすかるさんの

 (3) A[5]+A[6]+a[1]+a[2]+a[6]<a[5]+a[6]+A[1]+A[2]+A[6]

を見て、あーーーー、出題をミスりました。両辺にA[6](とa[6]と)がありますね、これを許した
のは私の大失敗です。

 気を取り直しまして。

 「+1」 などを使って、< を ≦ に変身させる 式の取り回しはさすがと存じます。こうした発
想は私にはありませんでしたのでとても勉強になりました。無論、題意を満たしております。
正解です。

 3本を足すとか、キャンセルを系統的に発生させるとか素晴らしいと思います。

 〈5項づつ〉という制限をはずしたものの一例をお示しいたします。

 まず、

 (1) a[1] < A[1]

がひとつめの不等式です。これを基礎として建物を立てます。次に柱を立てます。

 (2) a[1]+A[2]+A[3] > A[1]+a[2]+a[3]

 意味としては、(1)の両辺に2項づつ加えたならば、不等号の向きが逆転するという主張です。
こんなことがおきるのは、

  a[2] < A[2] 、a[3] < A[3]

のときのみです。次に家を完成させます。

 (3) a[1]+a[2]+a[3]+A[4]+A[5]+A[6]+A[7] > A[1]+A[2]+A[3]+a[4]+a[5]+a[6]+a[7]

 意味としては、以下のようになります。

 (1)(2)より、

 (4) a[1]+a[2]+a[3] < A[1]+A[2]+A[3]

です。(4)の両辺に4項づつ加えたら不等号の向きが逆転しました。これが(3)です。

 このような逆転がおこるのは、

 a[4] < A[4] 、a[5] < A[5] 、a[6] < A[6] 、a[7] < A[7]

のときのみです。以上となります。


 らすかるさんからのコメントです。(平成30年10月4日付け)

 両辺に同じ要素があってはいけないということでしたら、一つ前に考えた解で大丈夫だと
思います。

 (1) A[3]+A[4]+a[5]+a[6]+a[1]<a[3]+a[4]+A[5]+A[6]+A[1]

 (2) A[5]+A[6]+a[3]+a[4]+a[2]<a[5]+a[6]+A[3]+A[4]+A[2]

 (3) A[1]+A[2]+a[3]+a[4]+a[7]<a[1]+a[2]+A[3]+A[4]+A[7]


 (1)から、A[3]+A[4]+a[5]+a[6]+a[1]+1≦a[3]+a[4]+A[5]+A[6]+A[1]
 (2)から、A[5]+A[6]+a[3]+a[4]+a[2]+1≦a[5]+a[6]+A[3]+A[4]+A[2]

 2式を足すと、a[1]+a[2]+2≦A[1]+A[2] なので、a[1]<A[1] 、a[2]<A[2]

 すると、(3)から、 a[3]<A[3] 、a[4]<A[4] 、a[7]<A[7]

 そして(1)から、 a[5]<A[5] 、a[6]<A[6]


 DD++さんからのコメントです。(平成30年10月4日付け)

 別アプローチから作ってみましたが、完成したものはらすかるさんの解と同等のものでした。

 A[2]+A[3]+a[5]+a[6]+a[7] < a[2]+a[3]+A[5]+A[6]+A[7]
 A[4]+A[5]+a[1]+a[2]+a[3] < a[4]+a[5]+A[1]+A[2]+A[3]
 A[6]+A[7]+a[2]+a[3]+a[4] < a[6]+a[7]+A[2]+A[3]+A[4]

 両辺に異なる1項を加えた場合、不等号が等号になる可能性はありますが、逆向きの不等
号になることはありません。

 第 1 式の左辺に A[1] を、右辺に a[1] を加えます。
 第 2 式の左辺に A[3] を、右辺に a[3] を加えます。
 第 3 式の左辺に A[2] を、右辺に a[2] を加えます。

  A[1]+A[2]+A[3]+a[5]+a[6]+a[7] ≦ a[1]+a[2]+a[3]+A[5]+A[6]+A[7]
  A[4]+A[5]+a[1]+a[2] ≦ a[4]+a[5]+A[1]+A[2]
  A[6]+A[7]+a[3]+a[4] ≦ a[6]+a[7]+A[3]+A[4]

 これらの不等式を全て加えたものは明らかに等号が成立するので、もともとの不等式は
全て等号が成立していたこと、そして各不等式で左辺に加えた数は右辺に加えた数より大
きかったことがわかります。

  A[1]+A[2]+A[3]+a[5]+a[6]+a[7] = a[1]+a[2]+a[3]+A[5]+A[6]+A[7]
  A[4]+A[5]+a[1]+a[2] = a[4]+a[5]+A[1]+A[2]
  A[6]+A[7]+a[3]+a[4] = a[6]+a[7]+A[3]+A[4]
  A[1] > a[1]
  A[3] > a[3]
  A[2] > a[2]

 ここから先は容易なので省略。


 GAIさんからのコメントです。(平成30年10月4日付け)

 各項の値は、それぞれ、100 または 101 であるとする。

 この条件(a[1]〜A[7]の値はこの2種類しか取ってはいけない。)は変更できないんでしょう
か?

例 a[1]=1;A[1]=3;a[2]=4;A[2]=5;a[3]=2;A[3]=3;a[4]=6;A[4]=7;a[5]=8;A[5]=9;a[6]=10;A[6]=11;
  a[7]=12;A[7]=13 のような値を取ることは禁止ですか?


 らすかるさんからのコメントです。(平成30年10月4日付け)

 任意の i、j に対して、 A[i]-a[i]=A[j]-a[j] であれば、特に、100、101や1差である必要は
ないですが、GAIさんの例では、2差と1差が混ざってたりすると同条件の不等式では厳しい
のではないかと思います。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年10月5日付け)

 確かに問題を作成することは難しいと思います。例えば、相異なる素数とか…… ぞわっと
しました。

 らすかるさん、DD++さんのおふたりともに私ごときが考え付かない素晴らしい華麗なアプロ
ーチをご提示いただきました。有難うございます。

 さて、用意していた素朴なアプローチをご紹介したいと思います。

不等式(8) a[1]+a[2]+A[3]+A[4]+A[5] < A[1]+A[2]+a[3]+A[6]+A[7]

不等式(9) A[1]+A[2]+a[3]+a[6]+a[7] < a[1]+a[2]+A[3]+A[4]+A[5]

不等式(10) a[3]+a[4]+a[5]+A[6]+A[7] < A[3]+A[4]+A[5]+a[6]+a[7]


 不等式(8)の左辺と不等式(9)の右辺は同じ形になっています。不等式(8)の右辺と不等
式(9)の左辺では、A[1]+A[2]+a[3]が共通で、差違が見られるのは、(8)ではA[6]+A[7]であ
るのに対して、(9)では、a[6]+a[7] となっているところです。

 この点に注意して、不等式(8)と(9)とから以下の2本の不等式が得られます。

不等式(6) a[6] < A[6]

不等式(7) a[7] < A[7]

※不等式(6)(7)が成立しなければ不等式(8)(9)は成立しません。

 次に、不等式(6)(7)に留意しながら不等式(10)を見れば、以下の3本の不等式が得られます。

不等式(3) a[3] < A[3]

不等式(4) a[4] < A[4]

不等式(5) a[5] < A[5]

 次に、不等式(4)から(7)までに留意して不等式(8)から以下が得られます。

不等式(11) a[1]+a[2]+A[3] < A[1]+A[2]+a[3]

※A[4]+A[5]はA[6]+A[7]に等しいため

 不等式(3)に留意すれば不等式(11)より以下が得られます。

不等式(1) a[1] < A[1]

不等式(2) a[2] < A[2]


#(8)(9)の組み合わせが面白いと思いました。らすかるさんが以前示唆されていた方法論
 に近いと思います。式(10)の形が違うようでしたので、あのときの応答ではあえて口を濁
 しました。以上となります。


 DD++さんからのコメントです。(平成30年10月5日付け)

 あー、なるほど。私も、ある右辺とある左辺を一致させて2つを確定し、第3の式で3つを確
定するところまでは考えたのですが、残り2つを確定させる方法がなぜか思いつかずその方
法は断念しました。

 そのまままっすぐ進んでもちゃんと答えがあったのですね……。精進します。


  以下、工事中!



                         投稿一覧に戻る