😊出会いの泉😊

図での
AD=a,BC=b,CD=c,AB=xとおいて,この4つが整数となれる組合せ調べたら
(a,b,c)=(1,4,7)->x=9
=(2,5,7)->x=10
=(3,6,7)->x=11
=(4,7,7)->x=12
=(5,8,7)->x=13
=(6,9,7)->x=14
=(7,10,7)->x=15
　　　　･････････････
一般に(a,b,c)=(n,n+3,7)->x=n+8 (n=1,2,3,･･･)

または
(a,b,c)=(1,6,7)->x=9
=(2,7,7)->x=10
=(3,8,7)->x=11
=(4,9,7)->x=12
=(5,10,7)->x=13
=(6,11,7)->x=14
=(7,12,7)->x=15
　　　　･････････････
一般に(a,b,c)=(n,n+5,7)->x=n+8 (n=1,2,3,･･･)

c=7と設定しておくことがポイントになりそうです。

c=13 や c=19 でも可能なのでは。
おそらく 6n+1 型素因数を少なくとも 1 つ持っていることが条件じゃないでしょうか。

確かに6*n+1型の数は

7^2=3^2+8^2-3*8
=5^2+8^2-5*8

13^2=7^2+15^2-7*15 =>(a,b,c)=(n,n+8,13)->x=n+15 (n=1,2,3,･･)
=8^2+15^2-8*15 =>(a,b,c)=(n,n+7,13)->x=n+15 (n,1,2,3,･･)が構成できる。

19^2= 5^2+21^2- 5*21 =>(a,b,c)=(n,n+16,19)->x=n+21 (n=1,2,3,･･)
=16^2+21^2-16*21 =>(a,b,c)=(n,n+5,19)->x=n+21 (n=1,2,3,･･)

25^2=25^2+25^2-25*25(これは例外）

31^2=11^2+35^2-11*35=>(a,b,c)=(n,n+24,31)->x=n+35 (n=1,2,3,･･)
=24^2+35^2-24*35=>(a,b,c)=(n,n+11,31)->x=n+35 (n=1,2,3,･･)
以下同様
37^2= 7^2+40^2-7*40
=33^2+40^2-24*40

43^2=13^2+48^2-13*48
=35^2+48^2-35*48

49^2=16^2+55^2-16*55
=39^2+55^2-39*55

･･････････

と60°の角度を有する三角形の三辺を与えていく２組を
与えてくれますね。

理論的に計算する方法はわかりませんでしたので、
プログラムを作って調べました。その結果は
人数100,1000,10000,100000,1000000,10000000,100000000人に対して
(s,w)=(24, 97),(142, 997),(1015, 9997),(7986, 99997),
(66164, 999991),(565513, 9999985),(4944199, 99999967)
となりました。

管理人さんからのコメントで
単純にくじ引きで、２４人の当選者を決めてもらった方が、並ぶ人の感情としては納
得できると思うのだが．．．。

とありましたが、せっかく早く並んでいた1,2,3あたりの人が籤で当たらなかったら、それこそ不満が溜まりそうです。
これだと比較的早く並んだ方の人が選ばれやすい傾向を持てる気がしたので、このストーリーで表現していました。

20桁だと条件を満たすものが44個もあります。
桁数の最大は25桁で、値は
3608528850368400786036725
です。

44個の中に偶数の数だけのdigitsで構成されたものはありますか？

1つだけありました。
48000688208466084040です。

ちなみに、桁数別の個数は以下のようになります。
1桁: 9個
2桁: 45個
3桁: 150個
4桁: 375個
5桁: 750個
6桁: 1200個
7桁: 1713個
8桁: 2227個
9桁: 2492個
10桁: 2492個
11桁: 2225個
12桁: 2041個
13桁: 1575個
14桁: 1132個
15桁: 770個
16桁: 571個
17桁: 335個
18桁: 180個
19桁: 90個
20桁: 44個
21桁: 18個
22桁: 12個
23桁: 6個
24桁: 3個
25桁: 1個

この数列は↓こちらにありましたが、
http://oeis.org/A143671
こちらでは1桁の「0」も入れているようで、1桁が10個になっています。

もともとこの疑問に突き当たったのが
1～９の数字を一個ずつ含む9桁の数があり
「上k桁がkの倍数」(k=1～9)
を満たすものを探すと381654729である。

という記事でした。
何とかこれをプログラムを使って探し出そうと試みて
苦心惨憺の末5分ほどの運用時間で結果が手に入った。
実行させる前に9!の全順列を準備したり、上からk桁で
切り取る作業をやらせたりと、言ってみれば全検索を
掛けた上での作業でした。

これらについて更に調べてみると、別にプログラムに頼らずとも
論理的に導けている記事もありました。

そしてそこに話題が広がり
例の偶数{0,2,4,6,8}だけを使った20桁の整数（48000688208466084040)
が紹介されていました。

はて9桁でもあんだけ候補がありながら、これが20桁ともなると
5^20 = 95367431640625
ととても全検索を掛けようにも時間がいくらあっても無理だ！

そこで例の出題になったという経緯でした。


それに対し、らすかるさんのこの結果です。
これが如何に天文学的膨大な対象を処理されているか、想像しただけでも
腰が抜けそうです。
しかも半日もかからない時間で処理済みとなっている。

コンピュータさえあれば計算はあっという間に出来るだろうと思われるかも
知れませんが、そのオーダーが25桁などの桁になれば、とてもとても時間が
かかります。

以前コンピュータが高性能なのだろうと思っていたら、らすかるさんから
普通の使用のものを使っていますとの返事を頂いているので、これは正しく
プログラム力の成せる技でしかありません。（しかし神業としか思えません。）

もしかして、論理的に出せる数値なんですか？

論理的に出すのは候補が多すぎておそらく大変だと思います。
上から1桁ずつ増やして条件に当てはまるものだけその下の桁を
処理するようにすれば、時間は大してかかりません。
1桁目は1～9の9通り
2桁目は1桁目の9通りに対して各5通りなので2桁目までで45通り
3桁目はその45通りに対して3の倍数になるものなので150通り
（最初の2桁で合計が3の倍数である
　12,18,24,30,36,42,48,54,60,66,72,78,84,90,96
　の15個は3桁目が0,3,6,9の4通り、残りの30個は3通りずつなので
　15×4+30×3=150通り）
4桁目は3桁目が偶数なら0,4,8の3通り、奇数なら2,6の2通り→375通り
5桁目は0か5なので4桁までの2倍の750通り
・・・
ちなみに私が作ったプログラムの実行時間は
全桁数全通りで約0.13秒です。

らすかるさんの全桁数全通りで約0.13秒です。
のコメントを見て、改めてプログラムを見直してみたら
全体から選ぶんじゃなく、その条件を満たす数を小さい順に構成していけばいいんだ！
という決定的にお門違いの攻め方をしていたことに気付きました。
改めてプログラムを組んでみたら（３行程度）まさに1秒もかからない時間で
各桁の個数と具体的整数をすべて計算してくれますね。
25桁までは存在し、その後は構成できないとは初めて認識できました。

1桁: 最大1個 (2,3,5,7)
2桁: 最大2個 (13,17,37,79)
3桁: 最大4個 (149,179,379)
4桁: 最大11個 (1237,1279)
5桁: 最大39個 (13789)
6桁: 最大148個 (123479)
7桁: 最大731個 (1235789)
8桁: 最大4333個 (12345769)
9桁: 最大26519個 (102345697)
10桁: 最大152526個 (1123465789)
OEISにはこんな数列も載っているのですね。
↓
http://oeis.org/A065851
ここによると11桁は最大1251724個だそうですが、
11桁以上は時間がかかりそうなのでパス。

1桁: 2, 3, 5, 7
2桁: 11, 13, 17, 37, 79
3桁: 113, 197, 199, 337
4桁: 1193, 3779
5桁: 11939, 19937
6桁: 193939, 199933
7桁～18桁: なし
19桁: 1111111111111111111
20桁～22桁: なし
23桁: 11111111111111111111111

(4) は、最初に2個ずつ以下では釣り合ったときが不可能、4個ずつ以上だと傾いたときに不可能ということは簡単にわかりますが、3個ずつの場合がなかなか際どいですね。

そして、(3) が意外と難しい。

(3) の手順を再確認していた中で次のことがわかりました。

(6) m ≦ 3^t + 1 , n = 2 * t のとき、偽物2枚を特定可能

外接円が存在する八角形で、各辺の長さ及び円の半径が全て自然数になっているもの。
……のうち最小のもの？（自信なし）

設問を読んだ瞬間に
「きっと対角線の長さがすべて整数なんだろうな」
と思って確認したらその通りでした。
見事ですね。

私の予定回答はりらひいさんの通りですが、
DD++さんが書かれたことも気になって調べました。
その結果、
「外接円が存在する八角形で、各辺の長さ及び円の半径が全て自然数になっているもの。
……のうち最小のもの」
は「外接円の半径8、辺の長さ9,9,8,8,8,2,2,2の八角形(辺は順不同)」
でした。
# これは半径が最小のもののうち、最長辺が最小であるものです。
# 半径8の解は3つあり、半径が最小のもののうち、面積が最小ならば別の解になると思います。

ただし、「外接円が存在する八角形で、各辺の長さ及び円の半径が自然数で、
対辺がそれぞれ平行であるもののうち最小のもの」であれば
最初に書いた半径65の八角形になります。

なるほど、「平行八角形」なら正解でしたか……。

ところで、辺の長さが 33,25,16 ではなく全て2倍してあるのはどういう意図だったのでしょう？
私はそこに違和感を覚えて、奇数の長さになっている線分すなわち半径が整数となっていることが何か重要なんだろうなと思っていたのですが……単にそういう八角形を探す方法上での都合でしたか？

単なる探す時の都合です。
x^2+y^2=65^2上の点として
(63,16),(33,56),(-33,56),(-63,16),(-63,-16),(-33,-56),(33,-56),(63,-16)
の8点をとり、それぞれの点間の距離を計算していたので
結果的に偶数になりました。
半径を除けば、対角線の長さも含めてすべて偶数だったので
1/2にすることもできるな、と後で思いましたが、
1/2にしてしまうと座標で書くときとか外接円の方程式とかで
少し不便になりますので、そのままにしました。

「どの3点も一直線上にないn点があり、どの2点間の距離も整数」のnに上限があるか？
というのを考えている途中経過なのですが、こういう八角形があることを考えると
上限はなさそうな気がしています。
（ただし点が増えると爆発的に長さの値が大きくなる気はしますが…）

なるほど、そういう研究の過程でしたか。
半径に制限をつけなければそのような点を同一円周上に無限に取れると思います。
任意の隣り合う頂点の間の中心角が「その半角の sin も cos も有理数になるような角度」になるように点をとっておけば、どの頂点間の中心角も「その半角の sin も cos も有理数になる角度」なわけですから、単位円周上で任意の2点間の距離が有理数になるような点を好きなだけ取れます。
ぐるっと回って戻ってきた最後の1個の中心角も条件を満たすのか、という点に関しても、全ての中心角の合計が 2π であることから問題なし。

理論的な裏付けをありがとうございます。
とりあえず、半径243061325の円に内接する192角形で
すべての辺と対角線が整数になる具体値（192個の座標）までは出しました。
裏が取れたことでこれ以上進めても無意味なので、終了することにします。

> 「外接円が存在する八角形で、各辺の長さ及び円の半径が全て自然数になっているもの。
> ……のうち最小のもの」
> は「外接円の半径8、辺の長さ9,9,8,8,8,2,2,2の八角形(辺は順不同)」
> でした。
> # これは半径が最小のもののうち、最長辺が最小であるものです。
> # 半径8の解は3つあり、半径が最小のもののうち、面積が最小ならば別の解になると思います。

八角形にこだわらなければ
半径をいろいろ変化させると、それに内接するものがいろいろ作れていくのが面白いですね。（対角線の長さは無視です。）
例えば半径を8としたら
8が等しい2辺に対し残る一辺の長さが4,11,14の二等辺三角形をそれぞれ1,1,2個で埋めると8の円に内接する四角形が納まる。
また残る一辺の長さが4,8,14の二等辺三角形なら2,3,1個で内接する六角形が納まる。(8を6個使えばこれも内接しているが･･･)

半径を9とするとこれに内接する六角形を
残る一辺長(2,9,12)->(1,3,2)個
(3,9,17)->(2,3,1)個
(6,9,14)->(2,3,1)個
当然　　　(9) ->6個

以下同様
円の半径=>残り一辺：個数
12=> 6;12;21 :2;3;1 (内接六角形)
13=> 1;22;23 :1;2;1 (内接四角形)
13=> 10;13;24 :1;3;1 (内接五角形)
13=> 1;13;22 :2;2;2
14=> 4;22;26 :1;2;1
14=> 14;22;26 :2;1;1
16=> 8;22;28 :1;1;2
16=> 4;24;31 :1;2;1
16=> 17;22;28 :1;2;1
16=> 7;16;20 :1;3;2
16=> 4;16;31 :2;3;1
16=> 8;16;28 :2;3;1
16=> 12;16;23 :2;3;1
16=> 4;16;18 :3;3;2
16=> 4;18;31 :5;2;1
17=> 16;17;30 :1;3;1
18=> 4;18;24 :1;3;2
18=> 6;18;34 :2;3;1
18=> 12;18;28 :2;3;1
19=> 11;26;37 :1;2;1
19=> 11;19;26 :1;4;1
19=> 19;26;37 :2;1;1
19=> 11;19;26 :2;2;2
20=> 10;20;35 :2;3;1
･････････････････
3タイプの二等辺三角形に限っての調査しかしなかったので、もっとタイプを増やして
いけばまた違った埋め方が出てくるのでしょうね。

なお半径10,11では適当なものが見つからなかったのですが,見落としですかね？






　　　　　　

10=> 10;12;16 :3;1;1
13=> 1;13;22 :1;4;1
13=> 13;22;23 :2;1;1
14=> 4;14;22 :2;2;2
15=> 15;18;24 :3;1;1
15=> 3;14;25 :2;2;2
15=> 14;19;25 :1;1;2
とかあるのでは？

# 11は3タイプには分けられないようです。