|
uchinyan |
|
(考え方を少し変更しました。)
#26826の追加部分の補足 #26815のリンク先の一般式、 a(n) = 1/2 * (f(n,1) - f(n.2)) f(n,k) = Sum{(n - |x|) * (n - |y|)}, - n < x < n, - n < y < n, (x,y) = k ですが、何となく分かったように思います。なかなかうまい考え方のようです。 今回の問題では、如何に同じ点を通る直線の重複を除くががポイントになります。 その除き方ですが、次のように考えているようです。例えば、 A-----B-----C-----D-----E-----F-----G-----H となっているとします。このときは、結局は AH の 1 本だけしか意味がないのですが、これを 隣り合う二つの点からなる直線：線分 AB, BC, CD, DE, EF, FG, GH を延長した 7 本 隣り合う三つの点からなる直線：線分 AC, BD, CE, DF, EG, FH を延長した 6 本 と考えます。隣り合う二つの点からなる直線は、隣り合う三つの点からなる直線を含んでいるので、 (隣り合う二つの点からなる)意味のある直線は、7 - 6 = 1 本 になります。 ここで、隣り合う四つ以上の点からなる直線は、隣り合う二つの点からなる直線 及び 隣り合う三つの点からなる直線 に、 原理的には含まれているので、差をとれば相殺されて考える必要がない、ことになります。 なお、後で、それらを考える必要がある場合も考察します。 さて、この考えの下に、今回の問題を、傾きに注目して数えていきます。 傾きを、横方向を x、縦方向を y として、y/x と書きます。また、x と y の最大公約数をg(x,y)と書くことにします。 すると、x > 0, y >= 0 に対して、 ・0/1 = 0/2 = 0： 隣り合う二つの点からなる直線は、g(1,0) = 1 で、3 * 4 = 12 本。 隣り合う三つの点からなる直線は、g(2,0) = 2 で、2 * 4 = 8 本。 そこで、意味のある直線は、12 - 8 = 4 本になります。 実際の引き算は、横方向の四つの各直線ごとに 3 - 2 = 1 を行う必要がありますが、 最終的な本数はそれらの和なので、結局、上式に一致します。以下も同様です。 ・1/1 = 2/2 = 1： 隣り合う二つの点からなる直線は、g(1,1) = 1 で、3 * 3 = 9 本。 隣り合う三つの点からなる直線は、g(2,2) = 2 で、2 * 2 = 4 本。 そこで、意味のある直線は、9 - 4 = 5 本になります。 ・2/1 = 4/2 = 2： 隣り合う二つの点からなる直線は、g(2,1) = 1 で、2 * 3 = 6 本。 隣り合う三つの点からなる直線は、g(4,2) = 2 で、0 本。 そこで、意味のある直線は、6 - 0 = 6 本になります。 ・3/1 = 6/2 = 3： 隣り合う二つの点からなる直線は、g(3,1) = 1 で、1 * 3 = 3 本。 隣り合う三つの点からなる直線は、g(6,2) = 2 で、0 本。 そこで、意味のある直線は、3 - 0 = 3 本になります。 ・3/2 = 6/4 = 3/2： 隣り合う二つの点からなる直線は、g(3,2) = 1 で、1 * 2 = 2 本。 隣り合う三つの点からなる直線は、g(6,4) = 2 で、0 本。 そこで、意味のある直線は、2 - 0 = 2 本になります。 以上ですべてですが、実際の傾きは、x/y -> y/x, y -> -y が可能なこと、0 -> -0 は無意味なことを考慮すると、 1 * 2 * 4 + 2 * (1 * 5 + 2 * 6 + 2 * 3 + 2 * 2) = 8 + 2 * (5 + 12 + 6 + 4) = 8 + 54 = 62 本 となって、正解が得られます。 上記の場合分けを x/y -> y/x を補って#26826の追加部分と比べると、対応がつくことが分かると思います。 これ以上の詳細は冗長になるので省略しますが、一般式が導けること、少なくとも導けそうなこと、も分かると思います。 なお、a(n) の 1/2 は、傾きとしては意味がない x -> -x, y -> -y の同時変換が可能なことを補完しているものと思われます。 なお、この考え方を拡張すると、例えば、ちょうど二つの点だけを通る直線の本数も、同様に計算できます。 今求まっているのは、正確には、隣り合う二つの点からなる意味のある直線 なので、 これから、隣り合う三つの点からなる意味のある直線 を引けばいいです。 ところが、 隣り合う三つの点からなる意味のある直線 は、隣り合う四つの点からなる直線 から 隣り合う三つの点からなる直線 を引けばいい ことになります。 先ほどの議論から予想がつくと思いますが、傾きは同じにして、 隣り合う三つの点からなる直線は g(x,y) = 2 の場合で、1 * 2 * 8 + 2 * (1 * 4 + 2 * 0 + 2 * 0 + 2 * 0) = 24 本 隣り合う四つの点からなる直線は g(x,y) = 3 の場合で、1 * 2 * 4 + 2 * (1 * 1 + 2 * 0 + 2 * 0 + 2 * 0) = 10 本 そこで、隣り合う三つの点からなる意味のある直線 は、24 - 10 = 14 本となるので、 ちょうど二つの点だけを通る直線 は、62 - 14 = 48 本 になります。 これは、例の数列サイトの id A018809 http://www.research.att.com/~njas/sequences/A018809 ですね。 |
|
ネコの住む家
3月3日（金） 15:48:48
MAIL:uchi@sco.bekkoame.ne.jp 26829 |