二つの梯子で道幅計測
一定の道幅を持つ道路の両隣には２つの垂直な壁が立ちはだかり
今両壁に二本の梯子（長さをx,yとする。)が交差する形で立てかけられて
いるものとし、その交差している場所の道路からの高さをhとしたとき
これらから道路の幅wを算出するものとする。(梯子は道の両端からそれぞれ反対側の壁に掛けられているとする。)
1≦<x<y≦200であるx,yとhが全て整数である時、道幅ｗも整数で決定できる整数
(x,y,h)の組合せを探し出してほしい。
一例
(x,y,h)=(70,119,30)の時w=56で求まる。
更に
1≦x<y≦1000の条件x,yの整数で
そしてhの値も整数である時、道幅wが整数となれる異なるwの値は何通り可能か？
プログラムが正しければ
1≦x＜y≦200では
(x,y,h,w)=(70,119,30,56),(74,182,21,70),(87,105,35,63),(100,116,35,80),(119,175,40,105)
の5組 (wも5通り)
1≦x＜y≦1000では 組合せは77通り、wは53通り
ついでに
1≦x＜y≦10000では 組合せは1440通り、wは632通り
1≦x＜y≦100000では 組合せは18612通り、wは6423通り
(追記)
ちなみに形を考えてhとwの比に注目してみると
100000まででh/wが最大であるものは
(57739,87989,34713,6061) (h/w≒5.73)
100000まででw/hが最大であるものは
(10817,23999,206,10815) (w/h=52.5)
後者は梯子が10.817mとして道幅との差が2mmなので
実際には無理そうですね。
また
100000まででy/xが最大であるものは
(169,7081,118,119) (y/x≒41.9)
最小であるものは
(83259,83358,2378,83160) (y/x≒1.0012)
となっていました。
自分なりに調査して、正解はこうかな？
の状態で出題してるので、らすかるさんからの解答と同じものでやっとほっとします。
5/5=1
53/77=0.68831168831･･･
632/1440=0.43888888888･･･
6423/18612=0.34509993552･･･
で割合いが減少していくんだな。
解を眺めると、最小解の定数倍のものが多く本質的に異なる解ではないので
gcd(x,y,h,w)=1の解に限ると
200まで: 組合せ5通り、道幅5通り
1000まで: 組合せ28通り、道幅23通り
10000まで: 組合せ263通り、道幅221通り
100000まで: 組合せ1613通り、道幅1283通り
のようになっていました。
1000までの組合せは以下の通りです。
(x,y,h,w)=(87,105,35,63),(100,116,35,80),(70,119,30,56),(119,175,40,105),(74,182,21,70),
(182,210,45,168),(156,219,44,144),(113,238,14,112),(175,273,90,105),(104,296,35,96),
(175,364,80,140),(58,401,38,40),(273,420,80,252),(187,429,72,165),(425,442,70,408),
(375,500,144,300),(195,533,120,117),(286,561,90,264),(533,650,90,520),(87,663,55,63),
(663,689,168,585),(365,715,176,275),(625,750,126,600),(275,814,70,264),(583,825,210,495),
(845,870,306,600),(429,915,275,165),(697,986,126,680)
確かに最小解の定数倍のものもカウントされてしまっていますね。
gp > 23/28.
%210 = 0.82142857142857142857142857142857142857142857142857
gp > 221/263.
%211 = 0.84030418250950570342205323193916349809885931558935
gp > 1283/1613.
%212 = 0.79541227526348419094854308741475511469311841289523
で逆に同じwに対する2通りのパターン数の比率は余り変わらないのかも。
1000までの範囲では
w=63には(x,y,h)=(87,105,35),(87,663,55)
w=105には(x,y,h)=(119,175,40),(175,273,90)
w=165には(x,y,h)=(187,429,72),(429,915,275)
w=264には(x,y,h)=(275,814,70),(286,561,90)
w=600には(x,y,h)=(625,750,126),(845,870,306)
がそれぞれ2通りのパターンが起こるんですね。
w=63の2パターンは87も共通で興味深いです。
