空論上の砂、楼閣上の机。

The Castle of Indolence

整数の離散性と同値変形 (1991年東大理系第5問)

整数は幅 $1$ で均一に分布し、それを整数の離散性という……何を今更当たり前のことを、と思うかもしれません。ところがいざ問題を解くとなるとこの性質を適切に使うことができていない説明や解答が大半なのです。

問題. (1991東大理系第5問) $xy$ 平面上、$x$ 座標、$y$ 座標がともに整数であるような点 $(m,n)$ を格子点とよぶ。各格子点を中心として半径 $r$ の円がえがかれており、傾き $\dfrac{2}{5}$ の任意の直線はこれらの円のどれかと共有点をもつという。このような性質をもつ実数 $r$ の最小値を求めよ。

氏の解答は少し解説的なので詳しくはそちらを参照してもらうとして、論理関係をスッキリ書きたければ次のようにすれば良いでしょう。

まず、仮定から $m$, $n$ は整数なので $2m-5n$ は整数値以外の値をとらず、逆に整数 $N$ を用いて $(m,n)=(3N,N)$ とおくと $2m-5n=N$ となるので $2m-5n$ は任意の整数値を取り得ます。

f:id:all_for_nothing:20200722202344p:plain

3行目の同値変形こそが整数の離散性です。日本語に直せば「数直線上のどんな点を選んでも、その点を中心とする幅 $2\sqrt{29}r$ の区間の中に必ず整数が存在する」ということですから、整数が幅 $1$ で均一に分布することを考えると当然 $2\sqrt{29}r$ が $1$ 以上であることと同値になります。この程度の述語論理の翻訳や整数の離散性の適用は、本来は1行目で使うような点と直線の距離の公式より難しいはずなのですが……

ヒント. 「任意の○○に対してある××が存在して△△になるような○○の最大値」のような量化子がたくさん出てくる文章は、2人ゲームの勝敗に言い換えると(最善を尽くすことが量化子を表現する能力を持っているため)大幅に量化子を削減できてわかりやすくなります。