検索用コード
nを自然数とする.\ 次の条件を満たす整数解の組数を求めよ.$ \\[.5zh] 格子点の個数(連立不等式の整数解の組数)}$}}}} \\\\[.5zh] 連立不等式の整数解の組数は,\ 図形的には\textbf{\textcolor{red}{不等式が表す領域内の格子点の個数}}である. \\[.2zh] よって,\ ここでは格子点の個数問題として取り扱う. \\[1zh] 格子点の個数の求め方は,\ 基本的にはワンパターンである. \\[.2zh] \textbf{\textcolor{red}{直線$\bm{x=k\ または\ y=k}$上の格子点の個数を求め,\ その和をとる($\bm{\retuwa{}{}}$計算する).}} \\[-.5zh] このとき,\ \textbf{\textcolor[named]{ForestGreen}{境界線との交点が常に格子点となる方の直線で考える}}と楽になる. \\\\\\
}{直線\ y=k}\ 上の格子点の個数は 2n-2k+1=\textcolor{red}{-\,2k+(2n+1)}$ \\[1zh] 連立不等式の表す領域内の格子点の個数は \\[.7zh] 直線x+2y=2nは,\ 2点(2n,\ 0),\ (0,\ n)を通る直線である. \\[.2zh] 本問を直線\ x=k\ で考えると,\ x+2y=2nとの交点が必ずしも格子点ではなくなる. \\[.2zh] 一方,\ \bm{直線\ y=k\ で考えると,\ x+2y=2nとの交点が必ず格子点}となる. \\[1zh] 直線\ y=k\ 上の格子点の個数は,\ \bm{直線と境界線の交点のx座標}が求まればわかる. \\[.2zh] x+2y=2n\ と\ y=k\ を連立すると,\ 交点のx座標は\ \ x=2n-2k \\[.2zh] よって,\ 直線\ y=k\ 上の格子点の個数は 2n-2k+1\ (個) \\[.2zh] \bm{y軸上の格子点もカウントするので,\ +1を忘れない}ように注意する. \\[1zh] 後は,\ \bm{kを0からnまで変化}させて,\ その和を求めればよい. \\[.2zh] つまり,\ (y=0上の格子点)+(y=1上の格子点)+\cdots\cdots+(y=n上の格子点)\ を求める. \\[.2zh] 要はΣ計算である.\ これを見越して,\ 格子点の個数はあらかじめkで整理しておいた. \\[1zh] \retuwa{k=0}{n}\ を計算するわけだが,\ Σ公式は\ k=1からk=nまでの和の公式である. \\[.8zh] そこで,\ Σが単なる和であることを利用し,\ k=0の場合を分割する. \\[.2zh] つまり,\ \bm{(k=0)+(k=1からk=nまでの和)}\ とする. \\[.2zh] k=0のとき,\ -\,2k+(2n+1)=2n+1である. \\[.2zh] 後はΣ公式を適用し,\ 整理していけばよい.\ \bm{nは定数扱い}であることに注意する.
$4点(0,\ 0),\ (2n,\ 0),\ (2n,\ n),\ (0,\ n)を頂点とする長方形を考える.$ \\[.2zh] $周上と内部にある格子点の個数は \textcolor{cyan}{(2n+1)(n+1)}$ \\[.8zh] $2点(2n,\ 0)と(0,\ n)$を結ぶ線分上にある格子点の個数は $\textcolor[named]{ForestGreen}{n+1}$ \\[1zh] 求める格子点の個数は
領域が単純な幾何的図形ならば,\ 対称性などに着目すると楽に求まることがある. \\[.2zh] 本問の領域は三角形なので,\ 長方形を利用する. \\[.2zh] このとき,\ 次の点に注意しなければならない. \\[.2zh] \bm{求める格子点の個数は,\ 長方形の周上と内部にある格子点の個数の半分ではない!} \\[.2zh] なぜなら,\ 求める格子点の個数は,\ 図の\bm{赤と緑の点の個数}だからである. \\[.2zh] \bm{対角線上の格子点をすべて含むから,\ 単純に長方形の半分ではない}のである. \\[1zh] 長方形の周上と内部の格子点の個数はすぐに求まる. \\[.2zh] このとき,\ 軸上の点も含むから,\ 2n\times n\ ではないことに注意する. \\[1zh] \bm{y座標が1増えるごとに,\ 対角線上の格子点の個数は1増える.} \\[.2zh] 軸上の点も含むことを考慮すると,\ 対角線上の格子点の個数はn+1\ (個)\ であるとわかる. \\[1zh] まず,\ \bm{(長方形)-(対角線)}\ により,\ \bm{2つの三角形の部分の格子点の個数}が求まる. \\[.2zh] \bm{これを2で割ると1つの三角形の部分の格子点の個数}となる. \\[.2zh] さらに\bm{対角線上の格子点の個数を足す}と,\ 求める格子点の個数となる. \\[1zh] \bm{(求める点)=\bunsuu{(長方形内の点)-(緑の点)}{2}+(緑の点)=(赤の点)+(緑の点)} \\[1.5zh] 次のように考えて等式を作成してもよい.\ 求める格子点の個数をNとする. \\[.2zh] \bm{2N-(n+1)=(2n+1)(n+1)} より N=\bunsuu{(2n+1)(n+1)}{2}+(n+1) \\[.2zh] \bm{2\cdot(求める格子点)-(対角線上の点)=(長方形内の点)} \\[.2zh] 求める格子点は,\ (赤の点)+(緑の点)\ である. \\[.2zh] よって,\ これを単純に2倍すると,\ 対角線上の点(緑の点)を2回加えることになる. \\[.2zh] ゆえに,\ そこから対角線上の点を1回分除くと,\ ちょうど長方形内の点になるわけである.