平成２１年５月３日

[流れ星]

　　　　　第２２３回数学的な応募問題解答

　　　　　　＜解答募集期間：４月１２日〜５月３日

［三角形の個数］

先日、大学入試問題を見ていて改題しました。

問題１　ｍ，ｎを２以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である格子点
が４個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

問題２　ｍ，ｎを３以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である格子点

が９個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

問題３　ｍ，ｎを４以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である格子点

が１６個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

問題４　ｍ，ｎを５以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である格子点

が２５個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

NO1「uchinyan」 4/12 14時43分受信 更新5/3

第２２３回数学的な応募問題
［三角形の個数］ 今回も順番にやってみます。

問題１：
三角形を作るには 4 点から 3 点を選べばいいので，4C3 = 4 個以下です。
しかも，この 4 点は，そのどの 3 点も同一直線上にないので，すべてが三角形になります。
そこで，4 個です。

問題２：
三角形を作るには 9 点から 3 点を選べばいいので，
9C3 = (9 * 8 * 7)/(3 * 2 * 1) = 3 * 4 * 7 = 84 個以下です。
しかし，この 9 点のうち，次の 3 点が同一直線上に並んでしまい三角形にならないので，
これらを除く必要があります。
x 軸に平行な方向に 3C3 * 3 = 1 * 3 = 3 個
y 軸に平行な方向に 3C3 * 3 = 1 * 3 = 3 個
傾き +1 の方向に 3C3 = 1 個
傾き -1 の方向に 3C3 = 1 個
そこで，84 - 3 - 3 - 1 - 1 = 76 個です。

問題３：
三角形を作るには 16 点から 3 点を選べばいいので，
16C3 = (16 * 15 * 14)/(3 * 2 * 1) = 16 * 5 * 7 = 560 個以下です。
しかし，この 9 点のうち，次の 3 点が同一直線上に並んでしまい三角形にならないので，
これらを除く必要があります。
x 軸に平行な方向に 4C3 * 4 = 4 * 4 = 16 個
y 軸に平行な方向に 4C3 * 4 = 4 * 4 = 16 個
傾き +1 の方向に 3C3 * 2 + 4C3 = 1 * 2 + 4 = 6 個
傾き -1 の方向に 3C3 * 2 + 4C3 = 1 * 2 + 4 = 6 個
そこで，560 - 16 - 16 - 6 - 6 = 516 個です。

問題４：
三角形を作るには 25 点から 3 点を選べばいいので，
25C3 = (25 * 24 * 23)/(3 * 2 * 1) = 25 * 4 * 23 = 2300 個以下です。
しかし，この 9 点のうち，次の 3 点が同一直線上に並んでしまい三角形にならないので，
これらを除く必要があります。
x 軸に平行な方向に 5C3 * 5 = 10 * 5 = 50 個
y 軸に平行な方向に 4C3 * 4 = 4 * 4 = 50 個
傾き +1/2 の方向に 3C3 * 3 = 1 * 3 = 3 個
傾き +1 の方向に (3C3 + 4C3) * 2 + 5C3 = 5 * 2 + 10 = 20 個
傾き +2 の方向に 3C3 * 3 = 1 * 3 = 3 個
傾き -2 の方向に 3C3 * 3 = 1 * 3 = 3 個
傾き -1 の方向に (3C3 + 4C3) * 2 + 5C3 = 5 * 2 + 10 = 20 個
傾き -1/2 の方向に 3C3 * 3 = 1 * 3 = 3 個
そこで，2300 - 50 - 50 - 3 - 20 - 3 - 3 - 20 - 3 = 2148 個です。

(考察)
m, n が k 以下の自然数で格子点の個数が k^2 個でも同様に考えることができますが，
三角形にならない場合，3 点が同一直線上に並ぶ場合，を一般に求めて除くのは面倒そうです。
方針だけを書いておきます。
・まず，(k^2)C3 を求めます。
・x 軸に平行な方向な kC3 * k 個を除きます。
・y 軸に平行な方向な kC3 * k 個を除きます。
・a, b, a >= b を k-1 以下の互いに素な自然数としたときに，[ ] をガウス記号として，
　[(k-1)/a], [(k-1)/b] が共に 2 以上になる場合，
　最大 [(k-1)/a]+1 個の格子点が傾き +a/b の同一直線上に並びます。
　これと，格子点が 3 個になるまで平行に移動したものに関して，
　　�納格子点の個数が3<=i<=[(k-1)/a]+1となる傾き+a/bの直線に関する和]{iC3}
　を除きます。
・対称性より，傾き +b/a, -b/a, -a/b に関しても傾き +a/b と除く個数は同じで，
　それらを除きます。
以上を行えばいいのですが，一般には，４番目が面倒そうです。

(感想)
ナイーブに考えましたが，もう少し簡単にできないのかな．．．

NO2「kashiwagi」 4/22 14時31分受信

「kashiwagi」 4/24 07時11分受信 更新5/3

223回解答

　全ての点から3点を選ぶ組み合わせの数から3点が直線となるものを差し引くとの考えでやれば良い。

問1.

問2.

問3.

問4.　

下に示す赤丸を中心とした3点を通る赤い直線が全部で12本、そして3点を通る黒線が4本引けるので全部で4×4＝16本を引く事になる。

以　　　上．

NO3「ｽﾓｰｸﾏﾝ」 4/29 11時10分受信

目に青葉となり、動物のわたしには嬉しいシーズンです♪
超久し振りにトライしました ^^;v
これからも可能な限り（わたしには難しいことが多いです ^^;）・・・
挑戦しようと思いますのでよろしくお願いいたします m(_ _)m

問題１　ｍ，ｎを２以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である
格子点
が４個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

解答
3個の点が1直線上になることはないので、4C3=4個

問題２　ｍ，ｎを３以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である
格子点
が９個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

解答
3個の点が1直線に並ぶ場合を引けばいいので、
9C3-8=84-8=76個

「ｽﾓｰｸﾏﾝ」 4/29 22時25分受信 更新5/3

問題３　ｍ，ｎを４以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である
格子点
が１６個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

解答　　同様に考えて、、、
この場合、大な正方形の対角線の重なるものは引きすぎることになってるわけですね
^^;
だから、
16C3-10*4C3-4*1=516個

問題４　ｍ，ｎを５以下の自然数とするとき、座標平面上に座標が（ｍ，ｎ）である
格子点
が２５個ある。このうちの3点を頂点にもつ三角形の個数を求めよ。

解答　同じく、、、
同様に大きい正方形の対角線と重なってるものはカウントしないようにして、、、
ただこの場合は、2x4 の長方形の対角線も3点を通るので、この分 6*2=12 も引かな
くてはいけないので、、、
25C3-12*5C3-4*4C3-6=2300-120-16-4-12=2148
ですね♪

思ったより複雑でした...^^; Orz...

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。