最大値の最小値 with Mathematica
ー東大入試を １行で   解くー

2018 年12月 2日　  Cabri研究会　生越　茂樹

「最大値の最小値」を求めるときのポイント．（「最小値の最大値」も同様．)
以下,　 y=(Subscript[f, a])(x) について．少なくとも3つの方法がある．(個人的にはC→B→Aの順に発見した．)
プログラムはA<B<Cの順に長い．速度はC>B>A,C>A>B,A>B>C,A>C>B などまちまち．

方法A.　「 (Subscript[f, a])(x) の最大値の最小値≧k⇔∀a{∃x (Subscript[f, a])(x)≧k} 」
             「 (Subscript[f, a])(x) の最小値の最大値≦k⇔∀a{∃x (Subscript[f, a])(x)≦k} 」
             或いは否定を取って
             「 (Subscript[f, a])(x) の最大値の最小値≦k⇔∃a{∀x (Subscript[f, a])(x)≦k} 」
             「 (Subscript[f, a])(x) の最小値の最大値≧k⇔∃a{∀x (Subscript[f, a])(x)≧k} 」
             
             さらに
             「 (Subscript[f, a])(x) の最大値の最大値≦k⇔∀a{∀x (Subscript[f, a])(x)≦k} 」
             「 (Subscript[f, a])(x) の最小値の最小値≧k⇔∀a{∀x (Subscript[f, a])(x)≧k} 」
             或いは否定を取って
             「 (Subscript[f, a])(x) の最大値の最大値≧k⇔∃a{∃x (Subscript[f, a])(x)≧k} 」
             「 (Subscript[f, a])(x) の最小値の最小値≦k⇔∃a{∃x (Subscript[f, a])(x)≦k} 」
             
             ∃,∀と不等号の並べ方が (2^3)=8通りあり，その全てが最大，最小値と対応している.
             
             
             
方法B.  「(Subscript[f, a])(x) の最大値の最小値が≧k⇔∃{x,a} ((Subscript[f, a])(x)==k&&∀x  (Subscript[f, a])(x)≦k) 」を使う．

　　　　　　【注】後半の「∀x  (Subscript[f, a])(x)≦k」はaを固定して考えていて kがあるaについて最大値である事を表す．
　　       ∃{x,a} ((Subscript[f, a])(x)==k)&&(∀x  (Subscript[f, a])(x)≦k) とすると，∃{x,a} ((Subscript[f, a])(x)==k)　を考える時のa の値と,
             (∀x  (Subscript[f, a])(x)≦k) のa の値が異なるので駄目．


方法C. 「(Subscript[最大値M, a]) の計算」と「(Subscript[M, a]) の最小値の計算」の2段階に分ける．
　　       最大値(Subscript[M, a])  はきちんと2式(∀x (Subscript[f, a])(x)≦M と ∃x (Subscript[f, a])(x)≦M )で定義しその間を&&で結ぶ．
　　　　　（この場合は 2式に分けても，1式にまとめても同じ)
　　       (Subscript[M, a])  の最小値を求めるときは存在記号を使った方が解り易い．
　　　　　　即ち ∃{a,M}  M==k&&(上のステップで求めたMの条件式). ←∃{a} としないこと．
　　       
　　　　　　【注】 もし全称記号を用いるなら，∀a ∃M M≧k&&(Mの条件式) とする．
　　       「　Mの最小値が1以上である事を示せ」のような時は ∀a (Mの条件式)=> M≧1 とできる．
　　　　　　( ∀a (Mの条件式)&&M≧1　は駄目.通常はFalse になる)
            これを　∀a (Mの条件式)=> M≧k　とすると，「Mの条件式が偽」または「M≧k」となりうまく行かない．

「最大値の最小値」 （３つの中の最大値）

(Subscript[f, a])(x) の最大値の最小値≧k⇔∀a{∃x (Subscript[f, a])(x)≧k} 
 (Subscript[f, a])(x) の最大値の最小値≦k⇔∃a{∀x (Subscript[f, a])(x)≦k}

a={5,0};b={0,12};c={-9,0};H={x,y};
dis[x_]:=Total[x*x]; dis[x_,y_]:=dis[x-y]; (*dis=(distance^2)*)

dis[a, H] ≡ (((x - 5))^2)+(y^2),  dis[b, H] ≡ (x^2)+(((y-12))^2),   dis[c, H] ≡ (((x +9))^2)+(y^2)
 の最大値M(x,y) の最小値を求めればよい.

ForAll[{x,y},(dis[a,H]≥m)∨(dis[b,H]≥m)∨(dis[c,H]≥m)];
Resolve[%,Reals]//Timing

Exists[{x,y},(dis[a,H]<=m)∧(dis[b,H]<=m)∧(dis[c,H]<=m)];
Resolve[%,Reals]//Timing

「最大値の最小値」 （無数のxに対する最大値）

(Subscript[f, a])(x) の最大値の最小値≧k⇔∀a{∃x (Subscript[f, a])(x)≧k} 
 (Subscript[f, a])(x) の最大値の最小値≦k⇔∃a{∀x (Subscript[f, a])(x)≦k}

ClearAll["Global`*"];

【方法A】

ForAll[k,Exists[x,-1≤x≤1&&Abs[x^3-3 k x]≥m]];
Resolve[%,Reals]//Timing

ClearAll["Global`*"];
Exists[k,ForAll[x,-1≤x≤1\[Implies] Abs[x^3-3 k x]<=m]];
Resolve[%,Reals]//Timing

「最大値の最小値」

この問題は方法によって時間の違いが非常に大きく  A(9秒) > B(12秒) ≫ C(200秒) の順に速い．

【方法A】

ClearAll["Global`*"];
ForAll[{a,b},Exists[x,-1≤x≤1&&Abs[x^2+a x+b]≥k]];
Resolve[%,Reals]//Timing

Exists[{a,b},ForAll[x,-1≤x≤1\[Implies]Abs[x^2+a x+b]≤k]];
Resolve[%,Reals]//Timing

「最小値の最大値」 （図形問題）

(Subscript[f, a])(x) の最小値の最大値≤k⇔∀a{∃x (Subscript[f, a])(x)≤k} 
 (Subscript[f, a])(x) の最小値の最大値≥k⇔∃a{∀x (Subscript[f, a])(x)≥k}

ClearAll["Global`*"];　
sqr:=ImplicitRegion[Abs[x-a]≤1/2&&Abs[y-b]≤1/2,{x,y}];

【方法A】A (7 秒)>C (20 秒)≫B (75 秒) の順に速い．

prop1=ForAll[{a,b},(a-2)^2+(b-1)^2==1\[Implies]Exists[{x,y},{x,y}∈sqr&&x^2+y^2≤k]];
prop2=Exists[{a,b},(a-2)^2+(b-1)^2==1&&ForAll[{x,y},{x,y}∈sqr\[Implies]x^2+y^2≥k]];
Resolve[prop1,Reals]//Timing
Resolve[prop2,Reals]//Timing

「最小値の最大値」 （整数問題）

(Subscript[f, a])(x) の最小値の最大値≤k⇔∀a{∃x (Subscript[f, a])(x)≤k} 
 (Subscript[f, a])(x) の最小値の最大値≥k⇔∃a{∀x (Subscript[f, a])(x)≥k}

仮定より r の範囲は,        ∀k ∃(m,n) ((|2m-5n-k|)/(Sqrt[29]))≦r       となるから, QE では,

ForAll[k,Exists[{m,n},(m|n)∈Integers&&Abs[2m-5n-k]≤r]];
Resolve[%,Reals]

しかし整数問題なので（上の出力の通り) QEはうまく動かない．そこで意味を考えてみると...
kを固定して，m, nが動くときの|2m-5n-k|の最小値を f (k) としたとき， 「f (k) の最大値」を求めると良い．

(2m-5n)は任意の整数値を取れるので|2m-5n-k|の最小値 f(k)=min{x,1-x}  (但し x はk の整数部分). 
  よって f(k)の最大値は1/2 . 故に　 「(1/(2(Sqrt[29])))≦r」 となる．
  
  即ち，逆に論理式を「最小値の最大値」に直す事ができれば，そんなに難しくない．
  
  結局「∀a∃x f(a,x)」型の問題は 「最小値の最大値」などに翻訳するのが定石か？（私は知らなかったが...)
  逆に「最小値の最大値」問題は「∀a∃x f(a,x)」型の問題に書き直すと少し難しく見える.

● 実はこの問題で 「最小値の最大値」が 「∀a∃x」 の形に書けることに気が付いた．私にとっては思い出深い問題．