😊出会いの泉😊

a,b,c,d＞0とします。
(x+y)/2=b/(2a)+d/(2c)=(ad+bc)/(2ac)
z-(x+y)/2＞0を整理すると
(ad-bc)(c-a)＞0
x＜yからad-bc＞0なので
z-(x+y)/2＞0 ⇔ c＞a
従ってaとcを比較して
aの方が大きければx寄り
cの方が大きければy寄り
となります。

らすかるさん、ありがとうございます。
どの位の位置にあるかを考えました。
b/a+(d/c -b/a)×ｃ/(a+c)=(b+d)/(a+c)
なので、ｘとｙを、ｃ：ａ　に内分する点
であることが、分かりました。
分子は影響しないのが面白いですね。

b/a< x/(a+c) <d/c (a<c)を満たすｘの必要条件を調べたら
２ｂ＜ｘ＜２ｄで、b+ｄは、ほぼ中間であることが分かりました。
例えば、3/7<x/18<6/11　のとき、
ｘ＝7，8，９，１0，１１でした。

例えば、分母が　N＝５以下の既約分数は、
1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5 で
分子の和＝１８，分母の和が＝３６という意味です。

a/bが条件を満たす既約分数なら(b-a)/bも条件を満たす既約分数であり、
この2つの分子分母それぞれの和は分子がb、分母が2bとなりますので、
1：2になると言えますね。

カタラン数C(n)の再帰的漸化式として(ただしC(0)=1 とする。)

C(n)=∑[k=0,n-1]C(k)*C(n-1-k)

C(n)=∑[k=0,n-1]binomial(n-1,2*k)*2^(n-1-2*k)*C(k)

C(n)=∑[k=1,floor((n+1)/2)](-1)^(k-1)*binomial(n+1-k,k)*C(n-k)

などがあるようです。

https://oeis.org/A000108
のサイトでの
FORMULA
の部分に掲載されています。

そこに掲載されているということは正しいということなんでしょうけど、OEIS には証明までは載っていませんね。
カタラン数が関係するなら組み合わせで証明したいところですが、(-1)^k が入った式でそれやるの、難しいんですよねえ。

式の意味を無視して式変形でやるなら、カタラン数も二項係数も階乗に直す方針になるんでしょうか？
まだやってみていませんけど。

Σ[k=0～floor((n+1)/2)]((-1)^(k-1))*C[n-k]*comb(n+1-k,k)=0
を示せばよいですね。
tの関数 f(t) をべき級数展開したときの t^n の係数を　
[t^n]f(t)と書くことにします。

Σ[k=0～floor((n+1)/2)]((-1)^(k-1))*C[n-k]*comb(n+1-k,k)
=Σ[p=floor((n-1)/2)～n]((-1)^(n-p-1))*C[p]*comb(p+1,n-p)
=Σ[p=0～∞]((-1)^(n-p-1))*C[p]*comb(p+1,n-p)
=Σ[p=0～∞]((-1)^(n-p-1))*C[p]*[t^n]( (1+t)*(t*(1+t))^p )
=((-1)^(n-1))*[t^n]( (1+t)*Σ[p=0～∞]C[p]*(-t*(1+t))^p )
=((-1)^(n-1))*[t^n]( (1+t)*(1-sqrt(1-4*(-t*(1+t))))/(2*(-t*(1+t))) )
=((-1)^(n-1))*[t^n]( (1-sqrt((1+2*t)^2))/(2*(-t)) )
=((-1)^(n-1))*[t^n](1)
=((-1)^(n-1))*0
=0.

なるほど、カタラン数は母関数で扱う方針がありましたか。

細かいですが、2行目の
> Σ[p=floor((n-1)/2)～n]
は
Σ[p=n-floor((n+1)/2)～n]
ですかね。
一般に a-floor(b) ≠ floor(a-b) ですので。
次の行以降には影響しないので、2行目だけ修正すれば3行目以降は再び正しくなります。

> Σ[p=floor((n-1)/2)～n]
>は
>Σ[p=n-floor((n+1)/2)～n]
>ですかね。

その通りですね。
ご指摘ありがとうございます。
Σ[p=ceil((n-1)/2)～n] と書かなければいけないところを、
間違って、Σ[p=floor((n-1)/2)～n]
と書いてしまっていますね。
失礼しました。

GAIさん。
2, 7, 61 の三組の底では
4759123141 までの数について
確定的に素数判定ができるとのことです。
このミツグミは優秀なんですね……

上は、
http://miller-rabin.appspot.com/
をみてたら気がついたことです。

ええそうなんですよ。
だからもう一つ追加して
[2,7,61,211]の４つの素数を底に指定して、全部の底でミラー・ラビン方式(もはや確率的ではないのでこの名は使えないか？）
がクリアーできれば、
莫大な奇数nでも合成数か素数かが正しく判定できるような気がしているんですが、その限界も
数値的確認もしてないので何とももどかしい所なんですが･･･

確か、有限個の底の組では
確率100%のミラーラビン判定ができないことが、既に証明されていると思います。
昔、調べたことがあるのですがそのことが書いてあるページがありました。
今、そのページのブクマでURLに飛んだら、
サイトが消失していました。
残念………
どこか探せばあるはずですが……

もちろん素数はそれこそ無限個あるので、全部の奇数に対して合成数か素数かを有限個の調査で調べ尽くすことは
不可能であろうことは想像できますが、ある有限の範囲以内においては、そのような判定できる組合わせはあっても
いいと思われますし、また確かにいろいろな調査で存在しています。
この組[2,7,61,211]がどこまでの範囲で大丈夫なのかは自分もわからないのですが、感じとしては相当莫大な有限の範囲を
保証できるのではないかという意味です。

GAIさん。了解いたしました。

以下のNは、ミラーラビン法により200未満の全ての素数を底にして検査した結果として
強擬素数と判定されたものです。変なところに改行がはいっていて申し訳ありませんが、
コピペミスを怖れた次第です。

N=
80383745745363949125707961434194210813883768828755
81458374889175222974273765333652186502336163960045
45791504202360320876656996676098728404396540823292
87387918508691668573282677617710293896977394701670
82304286871099974399765441448453411558724506334092
79022275296229414984230688168540432645753401832978
6111298960644845216191652872597534901

底を 211 で検査すると、ようやく合成数と判定できるようです。

Nはかなり大きな数ですね。

https://mathcrypto.wordpress.com/2014/11/23/large-examples-of-strong-pseudoprimes-to-several-bases/
を参考にいたしました。

上記のNが合成数であることを見るために、素因数分解を見つけようと試みているんですが
未だに発見できないでいます。
色々な方法の素因数分解でのアルゴリズムがあるようなんで、この方面に精通されている方で
上記を試みるとどんな因数を持っているか分かる方、お教え願います。

GAIさん。
次のふたつの素数の積なのだそうです。

2004791083197498027091532260422734265025940830205662543872531023690016085350598121358111595798609866791081582542679083484572616906958584643763990222898400226296015918301

4009582166394996054183064520845468530051881660411325087745062047380032170701196242716223191597219733582163165085358166969145233813917169287527980445796800452592031836601

（恥ずかしながら…汗…）検算はしておりません。いつもの知人に問い合わせたら、調べてくれて、結果を教わりました。

この2つの数は k と 2k-1 という関係にあるように見えます（目視確認）。
ミラーラビンテストって実は k(2k-1) という形の半素数と相性が悪かったりするんでしょうか？

GAI さんがおっしゃるに

> ええそうなんですよ。
> だからもう一つ追加して
> [2,7,61,211]の４つの素数を底に指定して、全部の底でミラー・ラビン方式(もはや確率的ではないのでこの名は使えないか？）
> がクリアーできれば、
> 莫大な奇数nでも合成数か素数かが正しく判定できるような気がしているんですが、その限界も
> 数値的確認もしてないので何とももどかしい所なんですが･･･

調べてみました。
15070413782971 = 1171*19891*647011
で合成数です。

[2,7,61,211]の４つの素数を底にミラー・ラビン判定してみたところ、
Can be prime
となるようです。強擬素数判定ですね。

■確認方法
https://planetcalc.com/8995/
で、Miller–Rabin primality test
が可能です。

integer number 欄に
15070413782971
を入力します。前後に不可視なスペースが入ると叱られます。コピペの際には気をつけましょう。

bases 欄は random ではなく list にしましょう。

list としては、スペースで区切って
底を入力します。既定値は
3 5 7 11
となっていますのでこれを、今回は
2 7 61 211
と入れ直します。３箇所の区切り以外にスペースをいれると叱られるようです。

Details はオンにしたほうが面白いです。

Calculate ボタンを押下で
判定結果が返ります。

上の操作は、スマホでのものです。
パソコンだと違う？かもしれません。
お許し下さい。

Miller–Rabin primality test
のさきほどのオンラインツールが正確なのか不安ですので、
どなたか confirm をお願いいたします。

base を211単独でやればN;337桁で初めて擬素数を返す。
(2～199までの素数すべてをbase,または197,199の2つだけでbaseとしても同様な結果が起きる。)
のに対し
2,7,61,211の組合せでは以外に小さい14桁でのN=15070413782971(=1171*19891*64701)を偽判定してしまうのですね。
確かに
1171=1170+1
19891=17*1170+1
64701=553*1170+1
と相性が悪いものの構造になっているものなんですね。

全部をチェックしていませんが、この数値の周辺を観察してみたら判定は正しくされていることは
確認できました。（但しRubyのプログラムを利用して調べています。）

GAI さん。

文脈を追えないのでお教えいただきたいのですが……

>base を211単独でやればN;337桁で初めて擬素数を返す。

336桁以下の数ならば
確定的に素数判定ができるとのおかんがえでしょうか？

勘違いしてました。
例のNは211をbaseにしてチェックすれば擬素数と返すが、それより小さいものでも擬素数の判定を出すものはあるわけですね。
あくまで[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけて出てくる擬素数がこれだ。
ということでいいでしょうか？

> "GAI"さんが書かれました:
> あくまで[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけて出てくる擬素数がこれだ。
> ということでいいでしょうか？

15070413782971 は底を 11 のみで判定すると合成数と判定されるようです。従いまして
[2,3,5,7,･･･,197,199]のすべての素数をbaseにチェックをかけても合成数と判定されると思います。何個か底を選んだときに、そのうちひとつでも合成数判定されると、底全体のテストで、合成数判定の結果を出すと思います。

また、底として、 197 または 199 のどちらかをひとつ指定しても、やはり合成数判定されます。

15070413782971 は
底として、2, 7, 61, 211 のどれかひとつを
指定すると、いずれにせよ
合成数判定されません。
2, 7, 61, 211 から何個か選んで判定しても
合成数判定されません。
今回は、2, 7, 61, 211 を底にしたときの強擬素数を探してみたのです。

とはいえ、依然として合成数である可能性は残されていますね。そこで、実際に因数分解してみたのでした。

私の解釈が間違っていなければ
C(3,m)はm=0～100に対して
1,1,2,5,5,7,12,12,15,22,
22,26,35,35,40,51,51,57,70,70,
77,92,92,100,117,117,126,145,145,155,
176,176,187,210,210,222,247,247,260,287,
287,301,330,330,345,376,376,392,425,425,
442,477,477,495,532,532,551,590,590,610,
651,651,672,715,715,737,782,782,805,852,
852,876,925,925,950,1001,1001,1027,1080,1080,
1107,1162,1162,1190,1247,1247,1276,1335,1335,1365,
1426,1426,1457,1520,1520,1552,1617,1617,1650,1717,
1717
C(4,m)はm=0～100に対して
1,1,3,5,14,14,23,30,55,55,
76,91,140,140,178,204,285,285,345,385,
506,506,593,650,819,819,938,1015,1240,1240,
1396,1496,1785,1785,1983,2109,2470,2470,2715,2870,
3311,3311,3608,3795,4324,4324,4678,4900,5525,5525,
5941,6201,6930,6930,7413,7714,8555,8555,9110,9455,
10416,10416,11048,11440,12529,12529,13243,13685,14910,14910,
15711,16206,17575,17575,18468,19019,20540,20540,21530,22140,
23821,23821,24913,25585,27434,27434,28633,29370,31395,31395,
32706,33511,35720,35720,37148,38024,40425,40425,41975,42925,
45526
のようになり、この値から式を作ると
C(3,m)=[(m+3)/3]^2+[(m+1)/3][(m+4)/3]/2
C(4,m)=[(m+4)/4](4[(m+4)/4]^2-1)/3+[(m+1)/4][(m+5)/4]^2/2+[(m+2)/4][(m+6)/4](5[(m+2)/4]+1)/6
という式で表されそうです。

投稿ありがとうございます。

自分ではこの求めるべき経路数を一つずつ作図しながら求めていたものですから
mが100までのデータは考えられもしませんでした。

nが3の時の数の並びの変化の状態から
k=m\3 (mを3で割ったときの商をk)
L=3*k+1
として置けば、通常の3×mの格子路での全経路数S=(3+m)!/(3!*m!)に対する比率が
m%3の値に依存していることが起こりそうだと思われた。
つまり
m%3==0 ==>C(3,m)=S/L
m%3==1 ==>C(3,m)=S/(L+3)
m%3==2 ==>C(3,m)=S/(L+4)

これに従いプログラムを組んで並べて行き、m=20　位までぐらいを確認していました。
（なにせ手作業で図を描いてやっと経路数を見つけていたものですから）


これで上手く行きそうだと思ってしまったので
n=4も
k=m\4 (mを4で割ったときの商をk)
L=4*k+1
として置けば、通常の4×mの格子路での全経路数S=(4+m)!/(4!*m!)に対する比率が
m%4の値に依存していることが起こりそうだと思われた。
つまり
m%4==0 ==>C(4,m)=S/L
m%4==1 ==>C(4,m)=S/(L+4)
m%4==2 ==>C(4,m)=S/(L+5)
m%4==3 ==>C(4,m)=S/(L+6)

ところがどっこい実際に起こる経路数が
m%4==2　の場合分数の値を返してきて反映してくれない。
何とかSの値は利用したかったので、実際に起こる経路数と一致させるための調整が
m%4==2 ==>C(4,m)=(S-k*(k+1)*(4*k+5)/6)/(L+4)
へ辿り着きました。
Sから除くパターンの部分がなぜかA016061に繋がっているのが不思議でした。

これを元にプログラムを組んでやはりm=20辺り位までしか確認していませんでした。
それでらすかるさんの値と比較しm=98==2(mod 4)
でも一致できていたので安心しました。

しかしこれを一つの式で表せられるなんて思ってもいませんでした。
感じとしてはnが素数である時は、例の規則で行けそうですが、nが合成数になると
途端に厄介になりそうです。

今n=6に挑戦していますが、図を描いて正解数を求めるしか手がないので
らすかるさん、前もってその配列数をm=100までを教えて貰えませんか？

C(6,m)ならm=0～100に対して
1,1,4,12,23,42,132,132,227,377,
525,728,1428,1428,2010,2803,3504,4389,7084,7084,
9097,11654,13793,16380,23751,23751,28931,35246,40356,46376,
62832,62832,73950,87143,97584,109668,141778,141778,162883,187453,
206591,228459,285384,285384,322046,364124,396510,433160,527085,527085,
586638,654240,705789,763686,910252,910252,1002037,1105317,1183487,1270752,
1489488,1489488,1625096,1776599,1890570,2017169,2331924,2331924,2525439,2740354,
2901207,3079140,3518515,3518515,3786757,4083170,4304066,4547556,5145336,5145336,
5508104,5907251,6203610,6529292,7324878,7324878,7805193,8331713,8721393,9148503,
10187344,10187344,10811692,11493880,11997356,12547920,13881945,13881945,14680520,15550580,
16191123
のようになると思います。

（追記）
https://manabitimes.jp/math/962
↑ここの「書き込み方式」に従ってプログラミングすると簡単ですよ。
対角線を越える点をカウントしないようにするだけですから、
・(幅+1)×(長さ以上)の配列を作る(幅は3,4,6など、100まで出すなら「長さ以上」は101以上)
・配列全体を0にして(0,0)要素だけ1にする
・y=0～(長さ)まで以下の処理を行う
・x=0～(幅)まで以下の処理を行う（ただしy=0のときのみx=1から）
・(長さ)×x＞(幅)×yのときxのループを抜ける（対角線を越える格子点）
・配列の(x-1,y)要素と(x,y-1)要素の和を(x,y)要素の値とする（ただしx-1やy-1が負のとき0）
これで最終的に(幅,長さ)要素に格納された値が答えです。

ヒントをもらったのでPARIのソフトで挑戦してみました。
配列がmatrixの道具しかなく、成分は[1,1]から取ってあるので
微妙に取り方をずらしながら組んでみました。

F(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M

これより
gp > F(6,10)
%813 =
[1 0 0 0 0 0 0 0 0 0 0]

[1 1 0 0 0 0 0 0 0 0 0]

[1 2 2 2 0 0 0 0 0 0 0]

[1 3 5 7 7 7 0 0 0 0 0]

[1 4 9 16 23 30 30 0 0 0 0]

[1 5 14 30 53 83 113 113 113 0 0]

[1 6 20 50 103 186 299 412 525 525 525]



gp > F(6,18)
%818 =
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

[1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

[1 2 3 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0]

[1 3 6 10 14 18 22 22 22 22 0 0 0 0 0 0 0 0 0]

[1 4 10 20 34 52 74 96 118 140 140 140 140 0 0 0 0 0 0]

[1 5 15 35 69 121 195 291 409 549 689 829 969 969 969 969 0 0 0]

[1 6 21 56 125 246 441 732 1141 1690 2379 3208 4177 5146 6115 7084 7084 7084 7084]

あの手作業が夢のようです。


またnが素数の場合は予想が当たるか確認してみた。
n=7でやってみると
F7(m)={k=m\7;L=7*k+1;S=(7+m)!/(m!*7!);}\
if(m%7==0,print(m";"S/L),m%7==1,print(m";"S/(L+7)),\
m%7==2,print(m";"S/(L+8)),m%7==3,print(m";"S/(L+9)),\
m%7==4,print(m";"S/(L+10)),m%7==5,print(m";"S/(L+11)),\
m%7==6,print(m";"S/(L+12)))
と組んで走らせると
gp > for(m=1,50,F7(m))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890
21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117
41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348

一方
G(n,m)={M=matrix(n+1,m+1,i,j,if(j==1,1,i==1&&j>1,0))};\
for(x=2,n+1,for(y=2,m+1,if(m*(x-1)<n*(y-1),next,\
M[x,y]=M[x-1,y]+M[x,y-1])));M[n+1,m+1]
から
gp > for(m=1,50,print(m";"G(7,m)))
1;1
2;4
3;12
4;30
5;66
6;132
7;429
8;429
9;715
10;1144
11;1768
12;2652
13;3876
14;7752
15;7752
16;10659
17;14421
18;19228
19;25300
20;32890
21;53820
22;53820
23;67860
24;84825
25;105183
26;129456
27;158224
28;231880
29;231880
30;278256
31;332112
32;394383
33;466089
34;548340
35;749398
36;749398
37;870922
38;1008436
39;1163580
40;1338117
41;1533939
42;1997688
43;1997688
44;2270100
45;2572780
46;2908360
47;3279640
48;3689595
49;4638348
50;4638348

予想大当たり！！！

しかしn=6の場合はS=(6+m)!/(6!*m!)
の数値から導くのは困難でした。（未だに解決できずです。）

この粘菌コンピュータ、
以前から疑問だったのですが、識者に問いたいところです。
粘菌が解いたのはNP問題ではなく、多項式時間で解ける「中国人郵便配達問題」ではなかったかと思うのですよね。そんな気がするというだけで根拠はありません。間違っていたらごめんなさい。

四色定理の五辺国の話が NP だったというのは初めて聞きますが、本当ですか？
何か参考になる文献ありますか？

念のためですが、「実際に与えられた地図をどう 4 色で塗るか」という問題ではなく、「五辺国の塗り足しのためにどのような場合分けをすればいいか」の話であってますよね。
前者の話なら NP なのは明らかですし、四色定理の証明方針を考えればおそらく P なんだろうと思います。
が、後者の話だとそもそも何を問題サイズ n とすればいいかもよくわからないので、P とか NP とかを判定する対象にそもそもできないんじゃないかと思います。

https://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86
の四色定理にこう書いてあります。ケンプの証明後11年して、5辺国に誤りが見つかって、それで、これは五色定理と呼ばれていたそうです。四色で十分かは、グラフ理論の未解決問題として残ったと書いてあります。

その後コンピュータを利用して、四色問題を「証明」したとあります。

ですからDD++様の認識でよいと思います。

そこで、五色定理はPですが、グラフ理論の未解決問題をコンピュータでしらみつぶしで「証明」したから、Pではなく、Non-Pつまり、NPじゃないかと私は、思いました。

NP 問題の NP って Non-P じゃないですよ？

はちべえさん。

話のスジがずれていたら申し訳ないですけれども。

巡回セールスマン問題において、
セールスマンが訪問すべき拠点が50箇所程度であったとして、
コンピュータがしらみつぶしに厳密解を求めるために要するに時間は、
宇宙開闢以来現在までの時間でも、とてとても足りない、お話にならないくらい桁違い、
そういうオハナシなのですよね？
くだんのNHKの番組で紹介されていた筈です。

ではひるがえって、
四色問題における不可避集合を、事実上、しらみつぶしに調べることは人間の手には余る、だからコンピューターを使った、
でもこれ、そんなに時間がかかるものだったのてをしょうか？
不可避集合の個数は2000弱。
巡回セールスマンの訪問先の50よりも遥かに多いです。
にもかかわらず、放電手続きは無事に完了しています。論文の付録に全パターンを書き下すことができました。
これ、ほんとに巡回セールスマン問題と同じくらい難しい問題なのですか？

日本語で「しらみつぶし」というイメージは私も共有しています。
しかしながら、数学における、NPは、単なるしらみつぶしではないことも、頭にいれて議論したいものです。

おまけ。
NPとは、非決定性多項式時間（Non-deterministic Polynomial time）であり、Not Pではない。 定義は、「非決定性チューリングマシンによって多項式時間で解くことができる問題」かつ、「yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題」

ええ、正確には、Non-d.... Pですよ。d....は忘れましたが・・・

Dengan kesaktian Indukmu様、こんばんは。

>NPとは、非決定性多項式時間（Non-deterministic Polynomial time）であり、

そうです。それです。

コンピュータの計算に4年かかったそうです。充分、長い時間だと思いますけれどね。
コンピュータの出力は、高さ1.2mあったそうです。つまり、論文はとてもエレファントな証明だったそうです。

たぶん、終わりがあるんだろうかという不安にさいなまれたと思いますが・・・

一晩考えてみました。
問題の大きさ n を、「n 個の領域がある任意の地図を 4 色で塗り分けるアルゴリズムは存在するか」という形で定義すれば、四色定理の証明方法が NP かどうかの議論を始められることに気付きました。
そして、コンピュータでのしらみつぶしは全体の国の数に影響されない方法での検索だったので、解の発見にかかる時間は明らかに O(n^0) です。
だから、四色定理の証明は P 問題ってことになる……で、あってますかね？

DD++様、こんばんは。

ケンプは、数学的帰納法を使っていました。n国の地図は、4色で塗れるとします。

そこで、色が塗られてないn+1国の地図を持ってきて、
１）2辺国を探します。まず、2辺国を消すと、n国の地図ですから、4色で塗れるはずですから、塗ります。
そして、2辺国を復活します。2辺国は2つの国に挟まれているので、あと2色ありますから塗れることができます。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
２）3辺国を探します。消します。すると、地図は4色で塗れます。そして、3辺国を復活します。３辺国は３つの国に挟まれているので、あと１色ありますから塗れることができます。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
３）４辺国を探します。消します。すると、地図は4色で塗れます。そして、４辺国を復活します。４辺国は４つの国に挟まれているので、もう色はありません。そこで、トリッキーなことをして、４色でぬれました。
n+1国の地図が4色で塗れました。

また、色が塗られてないn+1国の地図を持ってきて、
４）５辺国を探します。消します。すると、地図は4色で塗れます。そして、５辺国を復活します。５辺国は５つの国に挟まれているので、もう色はありません。

つまり、５辺国問題が復活するのです。P問題では、解けません。

＞問題の大きさ n を、「n 個の領域がある任意の地図を 4 色で塗り分けるアルゴリズムは存在するか」という形で定義すれば、四色定理の証明方法が NP かどうかの議論を始められることに気付きました。
そして、コンピュータでのしらみつぶしは全体の国の数に影響されない方法での検索だったので、解の発見にかかる時間は明らかに O(n^0) です。

数学的帰納法で、n国まで成り立つとしてますから、これは、問題ないでしょう？
では、n+1国のときに成り立つ証明がいるのではないでしょうか？
そうでないと、数学的帰納法が完成しません。

いやいや、数学的帰納法で簡単（P≠NP 問題の意味では）に証明できるから P 問題だという話です。

ケンプ、アッペル、ハーケンによる証明は、
「100 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「1000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「10000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
「100000000 ヶ国の地図が全て塗り分けられることの証明」でもコンピュータで 4 年、
でしょう？

今日、NHKのEテレで、午後9:30~より、「笑わない数学　ポアンカレ予想」が放送されます。

Wikipediaのポアンカレ予想より引用すると、
＊＊＊＊＊引用開始＊＊＊＊＊＊
ペレルマンは解法の説明を求められて多くの数学者達の前で壇上に立った。しかし、ほとんどの数学者がトポロジーを使ってポアンカレ予想を解こうとしており、聴講した数学者たちもほとんどがトポロジーの専門家であったため、微分幾何学を使ったペレルマンの解説を聞いた時、「まず、ポアンカレ予想を解かれたことに落胆し、それがトポロジーではなく（トポロジーの研究者にとっては古い数学と思われていた）微分幾何学を使って解かれたことに落胆し、そして、その解説がまったく理解できないことに落胆した」という。
＊＊＊＊＊引用終了＊＊＊＊＊

トポロジーとは、位相幾何学だそうです。

ポアンカレ予想は、宇宙がおおよそ丸くない場合はどういう場合があるかというサーストンの研究から、これを証明することになったと言ってました。現在の物理学の世界観では宇宙はトーラス構造だそうです。

つまり、宇宙がおおよそ丸いというのは、直接的には証明されてないようですね。

４色問題もケンプの証明後11年後間違いが発見され、チューリングのオートマトン研究から、ノイマン型コンピュータができる訳ですが、チューリングがオートマトンを研究しなければ、コンピュータもできず、ハーケンらのコンピュータを使った解決はなかったでしょうし、後100年くらいかかったかもしれませんし、永遠に未解決のだったかもしれません。

このように、未解決の問題もコンピュータというタイミングで、解決されたことからも、いつか準備が整うまで、待たされ、それから解決されるのでしょう。

また、ペレリマンの証明も、後何年かして、間違いが発見されるかもしれません。絶対はないのでしょう。

さて、来週の「笑わない数学」は、虚数だそうです。虚数の歴史ですね。

今日、NHKのEテレで午後9:30から「笑わない数学　フェルマーの最終定理」が放送されます。

フェルマーの最終定理は、早々に未解決問題になって、数学者から、見放されたのでしょう。皆、忙しいですからね。

それをひっくり返したのが、全く関係のないと思われていた谷山ー志村予想が、フライ・セールのイプシロン予想で、フェルマーの最終定理を解決するとなったのです。
wikipedia 「フェルマーの最終定理」より
＊＊＊引用開始
つまり、谷山–志村予想が証明されたならば、それはフェルマーの最終定理が証明されたことをも意味するのである(=完全証明への道がつながった)。
＊＊＊引用終了
となったのです。

今日、NHKのEテレで午後9:30から「笑わない数学　カオス理論」が放送されます。

ニューロ人工知能は、一つ一つの原子を扱う統計力学的発想ですが、この前、NHKのEテレの心の時代で、脳はカオスであるという話がありました。まあ、マクロな経験則からできた熱力学みたいなものですね。現実は、統計力学より、熱力学のほうがよく使われているようです。ニューロ人工知能もカオス理論で、大きく進展するかもしれませんね。ニューロの人工知能で、うまく行っているのはカブトガニの視覚の研究の応用である画像認識だけらしいですから・・・・

今日、NHKのEテレで午後9:30から「笑わない数学　暗号理論」が放送されます。

暗号理論は巨大な数の素因数分解が困難であることを元にしています。
そこで、素数生成式を探していると、
https://enpedia.rxy.jp/wiki/%E7%B4%A0%E6%95%B0
にたどり着きました。素数生成多項式は存在しないことが証明されているそうです。
でも、そこには、マチャセビッチの多項式が、存在しているという話です。
でも、実用性は全くないそうです。
しかし、マチャセビッチの多項式は、証明されているそうです。
矛盾してますが、・・・・・

マチャセビッチの多項式について調べてみましたが、何も矛盾しているとは思いませんでした。
はちべえさん、そろそろ「正しい」「間違っている」を自分勝手に決めつけて話すのをやめませんか。

DD++様、こんばんは。
＞はちべえさん、そろそろ「正しい」「間違っている」を自分勝手に決めつけて話すのをやめませんか。
わたしは、そんなことを言ってません。
＞素数生成多項式は存在しないことが証明されているそうです。
＞しかし、マチャセビッチの多項式は、証明されているそうです。
なので、
＞矛盾してますが、・・・・・
と感想を書いただけです・・・・・

さて、来週は、ABC予想です。これは、大変面白いので、期待してます。

余談です。

《暗号理論は巨大な数の素因数分解が困難であることを元にしています。》

んー。
「笑わない数学」では
RSA暗号しか説明しなかったのでしょうか？
公開鍵暗号は、他にもいくつかやりかたがあってですね、最近ではRSAには未来がないという考えを持つ人も増えつつあります。量子コンピュータが素因数分解を得意とするかもという懸念があるためです。その実装はまだまだ先ですが。

《暗号理論は巨大な数の素因数分解が困難であることを元にしています。》については
もうちょつと複眼的に興味を持っていただければ幸いです。

Dengan kesaktian Indukmu様、こんばんは。
ありがとうございます。

来週のABC予想は面白いですよ。
ちょっと、参考までに、
数学者は宇宙をつなげるか？ａｂｃ予想証明をめぐる数奇な物語
https://www.nhk.jp/p/special/ts/2NY2QQLPM3/blog/bl/pneAjJR3gn/bp/pzwyDRbMwp/

かけ算は簡単であるが、足し算はむつかしいということで、フェルマーの最終定理も足し算でなくて掛け算だったらたちどころに解決できるそうです。数学にはそういう問題がたくさんあって、望月さんによって、ABC予想が証明されたので、数学は大きく変わるとか・・・

あっそうだ、思い出しました。

RSA暗号で。
秘密鍵を p, q のふたつの素数とし、
公開鍵を N=p*q としたときに。
Nの素因数分解をせずに暗号文を復号し平文を求める方法がいくつか知られています。
ただし、p,q の取り方が下手くその場合にですが。

ビックリするのですが。
平文 X を暗号化したものを
此の投稿に限り、
X ^a
としましょう。
で、こうしてできた暗号文を、
さらに、公開鍵で繰り返し暗号化していきます。
(((……(X^a) ^a) ^a) ^a) ……^a
そうすると、それが
Xと等しくなってしまうことがあるそうです。
これを、繰り返し暗号化攻撃といいます。

回避するためには
秘密鍵 p,q の作り方を工夫する必要があります。特許もあるようです。

繰り返し暗号化攻撃の他にも
アタックのしかたが少なくないようで
RSAでの安全な 秘密鍵の作り方が工夫されているようです。

このリストは、
底として、2 およびに 3 だけを取ったときのものと同じになるようですね………

それはそうと、
p*(t*p-t+1)
のかたちになっているのですね。

DD++さんから、ミラーラビンは今話題にしている形での半素数に弱いのかというテーマが挙げられています。

必ずしも半素数にはならないようでしたので
以下にメモをあげます。

3215031751 は、
2, 3 をともに底としたときに
強擬素数です。
この数は
28351 * 113401
に等しく、また
113401 = 28351 * 4 -3
となっています。

私達がいま興味をもっていた形ですね。

さて、
113401 = 151*751
と素因数分解可能です。

このことから
3215031751 は半素数ではありません。

個人的には、半素数であるかどうかよりも、k と 2k-1 という値の大きさの関係を気にしていました。
その後、
・どうやら k+1 と 2k+1 という形に書いた方がよいこと
・2k+1 だけでなく mk+1 という形であれば m=2 という形かどうかはあまり重要でなさそうなこと
が見えてきていますね。

751 と 151 も、
151 = 150 + 1
751 = 5*150 + 1
ですから、同様の性質は持っていると言ってよさそうに思います。

2 と 3 とをともに含む
複数の底でミラー・ラビン判定を行い
結果が強擬素数であったとします。

この強擬素数が素数であるのか合成数であるかについてを更に調べたいと思ったとします。

この強擬素数を S とします。
まだ未証明ですが、次のような予想が成り立つとしましょう。すなわち。

S が合成数であるならば
自然数 k と m とがあって
S = (k +1)*(m*k +1) ………①
となる。

S が素数であるか合成数であるかを知りたいときに ① をあてにしてよいとするならば
単に、√S までの素数を列挙して
S をそれらで割ってみる素因数分解方法よりも速く素因数分解の結果が得られることがあるのでしょうか？

GAI さんによる 10^8 までの
強擬素数の素因数分解のリストを見るかぎり
どうやら m はかなり小さめです。

m について小さい順に調べると良いのではと思います。

①を、k についての２次方程式とみて
判別式が平方数になるかどうか検査すると
よいのではないかと山勘を働かせてみました。

さて、この方法は、本当に速く処理できるものなのでしょうか？

素因数分解できるまでの「平均時間」は圧倒的に速いと思います。
素因数分解ができるまでの「最悪の時間」はむしろ悪化すると思いますが。

つまり、最悪試さなきゃいけない候補の数は増えますが、当たりになる可能性が高いところだけを最初にピックアップして試せる感じになります。
たぶん。

DD++さん。
御意見をありがとうございました。
私の心象もそれに近いものがあります。

ここまでちょっと話を飛ばしすぎたきらいがありますので、以下では小まとめを。あとでログを見返したときにわかりやすいようにです。

2 およびに 3 を含む複数の底を使ってミラー・ラビン判定法を行います。その結果として合成数として判定されなかったものは強擬素数ですが、依然として合成数である確率がわずかながら残っています。今回はこの数を S と書くことにします。

観察によれば、S が合成数であるならば、m k を自然数として、
S = (k +1)*(m*k +1)
となることが期待されます。
なお、(k +1)、(m*k +1) については、素数であることを要請しません、念のため。
こうした m k を簡便に求められれば、
強擬素数 S が合成数であることの判定が簡便にできることとなります。 m k がみつけられなかったとしても、それは、合成数であることをこの手法では証明できなかっただけのことなので、強擬素数 S が素数であるとは限りません。

具体例をあげます。
S = 16697267137953148781
とします。
なお、この S は、底として、2, 3, 5, 7 を使ったミラー・ラビン法で強擬素数となるものです。
S = (k +1)*(m*k +1)
となる m k をみつけるために
k についての２次方程式とみたててこれを解くことを考えます。すなわち
m*k^2 +(m +1)*k +(1 -S) = 0
D = (m +1)^2 -4*m*(1 -S)
とおくと、この２次方程式の正の解は
k = (-(m +1) +√D)/(2*m)
となります。k が負の解は捨てます。
k が自然数であるための必要条件のひとつは
D が平方数であることです。
本当は、(2*m)で割っていますから、十分条件にはなっていません。
あとで確かめることにします。★★★

D = (m +1)^2 -4*m*(1 -S)
なのでしたが、これが平方数になるような m がうまく見つかるとありがたいわけです。
これまでの観察によれば、m はさほど大きな数にはならないようですので、m について、1 からはじめて順次カウントアップして探すこととします。

実際にやってみると、(プログラムが組めないので電卓でしました)
m = 6 で D が平方数となりました。
このときの D は
D = 400734411310875570769 = 20018351863^2
です。早くみつかってラッキー。この m をもとの２次方程式にほうりこんでやると
k = (-7 +√D)/(12)
= (20018351863 -7)/12
となります。
ちやんと 12 で割り切れればよいのですが……前に★★★で留意点としてあげていたことがここで確認されます。
実際に計算してみると
k = 1668195988
となります。★★★はクリアされました。
m = 6 でしたから
S は
S = (1668195988 +1)*(6*1668195988 +1)
となります。
検算すると
確かに、
S = 16697267137953148781
となります。
S は合成数と判定されました。

以上のように、比較的に簡便に合成数判定ができるケースが多くみられるのではないかとの予想をたててみています。

ミラー・ラビン判定法の補助手段として利用できたら嬉しいです。

言い忘れました。
16697267137953148781 は、底を 6 とすると合成数と判定されるそうです。
2 でも 3 でも強擬素数なのに。

k が負の整数の場合、狙っていた形とは合致しませんが S の因数分解には成功します。
ですから、排除する必要はないのではないかと思います。

また、k が整数にならない場合の心配ですが、仮にそうなっても 4mS を 2 つの因数にわけることは成功します。
m が S よりずっと小さい場合は、その場合でも（目的の式の形にはなりませんが）S の因数分解には成功するんじゃないかと思うのですが、どうなのでしょう。

> DD++さんが書かれました:
> また、k が整数にならない場合の心配ですが、仮にそうなっても 4mS を 2 つの因数にわけることは成功します。
> m が S よりずっと小さい場合は、その場合でも（目的の式の形にはなりませんが）S の因数分解には成功するんじゃないかと思うのですが、どうなのでしょう。

アドバイスを有難うございます。
D = (m +1)^2 -4*m*(1 -S)
としていましたが、これを整理すると
D = (m -1)^2 +4*m*S
この D がある自然数 T の２乗になっていると
開平が出来て嬉しいのでした。
こうした T がみつかったときには
(m -1)^2 +4*m*S = T^2
となり、これを変形すれば
4*m*S = T^2 -(m -1)^2
4*m*S = (T +(m -1))*(T -(m -1))
となります。
仰るとおりに、
《4mS を 2 つの因数にわけることは成功します。》
とわかりました。
実用の範囲内で m が十分に小さいことがわかれば、
k を求めることを行わなくても
S の合成数判定ができるのですね、
おどろきです。


> DD++さんが書かれました:
> k が負の整数の場合、狙っていた形とは合致しませんが S の因数分解には成功します。
> ですから、排除する必要はないのではないかと思います。

→
これ、意味をつかめませんでした。
よろしければご教示を賜りたくお願いいたします。

> 観察によれば、S が合成数であるならば、m k を自然数として、
S = (k +1)*(m*k +1)
となることが期待されます。

反例をようやくみつけました。
S = 196161196117261
は、底を 2, 3 としたミラー・ラビン判定法で強擬素数ですが、
S = 6602377*29710693
という半素数で、
k = 6602376
m = 29710692/6602376 = 9/2
となっています。

k が負の整数だと
S = (-101)*(-103)
みたいな形になるので、自然数の積にはなりません。
でも、これを見て自然数の積に書き直すのは容易ですよね、という話です。

> 反例

薄々そんな予感はしていましたが、やっぱり (mk+1)*(nk+1) の形も出てきましたか。
まあ、m も n も小さいという条件でなら、該当する数を探す労力はそんなに変わらないと思いますが。

その数S以前には
190131062354461,190847302523971,191212468762741,･･･
その数以降も
197201702068963,197867738963563,198675496474963,198888784469461,200262009366409,
200271411485473,200669198495977,201324851364883,･･･
等次々と見つかりますね。

その数S周辺しか調査しなかったのでもっと小さい数でも例外が見つかるような雰囲気ですね。

1150 の DD++ さん。

お返事をありがとうございます。
S = (k +1)*(m*k +1) ………①
ではなく、
S = (k -1)*(m*k -1)
の解を求められた、ということになるのですね、なるほど。


1153 の　GAI さん。
(m*k+1)*(n*k+1)
のかたちでもよいとして
m や n が大きめのものってありますかね。

最初に GAI さんにご提示いただいた
10^8 までのリストでのトップは
m = 18 , n = 1でした。

実はさきの反例
S = 6602377*29710693
は、大きな m をひたすら電卓で
さがしていてみつけたのです。
m 捜し、こちらに興味があったものですから。

(1)だと思います。
平面と垂直な直線が「法線」と定義されていますので、法線と平面のなす角は90°であり、
それから考えるとlとPのなす角は60°と考えないと矛盾が生じてしまうと思います。
（これ以外の定義は見たことがありません）
30°は「平面Pの法線と直線lのなす角度」のように言うと思います。

ありがとうございます。
やっぱり (1) でいいですよね。

ところが、先日ある場所で出会った問題に、以下のように書いてあったんです。
「ただし直線が平面に含まれるとき、両者のなす角は π/2 とします。」
実際に解く上では無関係な注釈だったので、誤植かと思って (1) の定義に従って私は解きました。
が、模範解答もどうやら (2) の方を採用している様子。

私が定義を勘違いしているのか、それとも「0 を自然数に含むか問題」のように定義が何種類かあるのか、と思って質問した次第でした。
しかし、うーん、結局どういうことだったんだろう。

> 「ただし直線が平面に含まれるとき、両者のなす角は π/2 とします。」
この文だけだと何とも言えないですね。例えば
平面Pの法線nと平面Pとの交点をOとし、Oを通るある直線と法線のなす角度をθとします。
「ただし直線が平面に含まれるとき、両者のなす角は π/2 とします。」
だとしたら「両者」が「直線と法線」を指している可能性が高いです。
もしそうであれば(1)と矛盾しませんね。

管理人さんも、調べてくださってありがとうございます。

問題文全体がないと判断しかねる感じのようなので、議論の資料とする目的で、著作権法第32条に基づいて公表された著作物の引用をします。
記事の方に転載するかどうかは管理人さんの判断に委ねます。
なお、掲示板に書く都合上、
・分数の表記方法
・全角と半角（印刷では区別がつかないため）
・アルファベットの書体
がやむを得ず変更されています。

-----引用ここから-----

問題3. xyz 空間において 2 点 ( 3, -6, 2 ), ( -11, -4, 6 ) を通る直線を l, 方程式 5x-3y+4z-11=0 で表される平面を P とします。
l と P のなす角をθ ( 0≦θ≦π/2 ) とするとき, cosθ の値を求めなさい。ただし, 直線が平面に含まれるとき, 両者のなす角は π/2 とします。

-----引用ここまで-----
（第406回 実用数学技能検定 1級 1次:計算技能検定 (c) 日本数学検定協会 より引用）

模範解答は 1/√3 だそうです。

答えが間違っているとしか言いようがないですね！

どちらかというと「問題が間違っている」ような気がします。
「直線が平面に含まれるとき, 両者のなす角は π/2 」って、どこの角度のことを言っているのか意味不明です。
（直線と「平面の法線」の角度のことを言っているのかな？と予想はできますが。）
「平面とその法線のなす角度がπ/2」が多くの人の共通認識だと思います。

問題も答えもおかしいと思うのが私だけでなくてよかったです。
数検ってこういう場合採点どうなるんだろう。

数検の結果の詳細が届きました。
√6/3 は不正解になっていました。
合格者正答率がこの問題だけ異様に低いので、私と同じように戸惑いながらも通常の定義に従って解いた人が多かったんでしょうね。

これのせいで 1 点とか 0.5 点足らなかった人がいたらかわいそう……。

A>B>C,三つの抵抗の接続の場合、
A＋B＋C＞A＋B×C＞B＋A×C＞C＋A×B＞
A×（B＋C）＞B×（A＋C）＞C×（A＋B）＞A×B×C
８個の絶対不等式が生まれます。
４個の抵抗では、何個の不等式ができるか、興味ないですか？