Evolton
方針
格子辺は格子点を除いた単位の縦横線分なので、曲線が縦の格子線または横の格子線を格子点以外で通過した回数を数える。格子点を通ると、その点自体は格子辺に含まれないため、縦線・横線の両方の数え上げから除く。(1)は直線上の内部格子点数を から求める。(2)は内部の整数 で も整数になる点数 を、既約分母 の 乗が を割る条件で分類する。
解答
(1)
点 を通る直線 は原点も通るので である。したがって直線は である。 の範囲にある縦の格子線は の629本である。また の範囲にある横の格子線は の5399本である。
ただし、直線が格子点を通る場合、その点は格子辺から除かれているので、縦の格子辺との交点にも横の格子辺との交点にも数えない。直線上の内部格子点を数える。 であり、 と は互いに素であるから、原点と の間の格子点は の89個である。
よって縦の格子辺と交わる回数は 、横の格子辺と交わる回数は である。したがって求める個数は である。
(2)
曲線 が点 を通るので であり、 である。この曲線は で単調に増加するので、縦格子線と横格子線をそれぞれ1回ずつ横切る。ただし内部格子点を通る場合は、(1)と同じく縦・横の両方から除く。
内部の格子点数を とする。縦格子線は629本、横格子線は5399本なので、求める個数は である。
内部格子点を数える。 で整数 をとり、 と既約分数で表す。すると 、 は の約数である。曲線上の 座標は である。 と は互いに素なので、 が整数であるための条件は である。
素因数分解すると である。 のとき、 となる は の約数である。このとき可能な既約分数 は、 を既約化して得られるものすべてであり、個数は29個である。したがって で、交わる格子辺の個数は である。 のとき、 となる は の約数である。同様に、可能な既約分数は を既約化して得られる5個である。したがって で、交わる格子辺の個数は である。 のとき、 を満たす は存在しない。したがって内部格子点はなく、 である。よって交わる格子辺の個数は である。
以上より、答えはである。
別解
解法2
方針
単調曲線が横切る内部の縦格子線629本と横格子線5399本を先に数える。曲線上の内部格子点では格子辺と交わらないので2回ずつ差し引き、既約分母 の条件 から内部格子点数を分類する。
解答
(1)
原点と の間にある内部格子点の個数はである。直線は内部の縦格子線629本、横格子線5399本をそれぞれ1回横切るが、内部格子点は格子辺の端点であって格子辺には含まれない。従ってその89点では縦・横の両方を除き、個である。
(2)
曲線はで、区間内で狭義増加する。内部格子点数を とすれば、同じ理由で交わる格子辺数はである。
を既約分数で表す。 が整数となる必要十分条件はである。 では可能な分母は30の約数であり、区間 の異なる既約分数はを既約化して得られる29個である。従って 。
では可能な分母は6の約数で、同様に である。 では は存在せず、 となる。よって答えは
総評
格子辺の定義を正確に扱う数え上げ問題で、想定時間は28分程度。曲線や直線が格子点を通ると、その点は格子辺の端点であって格子辺そのものには含まれないため、縦・横の両方から除く必要がある。(2)では、 として内部格子点だけを分類するのが中心で、既約分母 に対して が必要十分になる理由を丁寧に書きたい。 で分母の候補が急に減る点がこの問題の山である。