A7手帳、浅海散子

A7サイズの手帳。何かを書く。

格子点と正方形のクイズ

Twitterで出会ったクイズ

先日、ポテト一郎(https://twitter.com/potetoichiro:@potetoichiro)さんのクイズを目にした。とても興味深いクイズだったので、数学的、あるいはプログラム的な問題に落とし込めないか考えている。

クイズの設定はツイートおよびリプライチェーンに載っているが、一応こちらでも詳しく定義しておく。定義自体がヒントになってしまう可能性があるため、ぜひご自身で解いてみてから続きを読んでほしい。

また、リプライチェーンにクイズの答えが載っているため、答えを見たくない場合は上述のツイートだけを参照してほしい。

出題者（またはクイズを紹介している方）が解答の求め方をネタばらししてほしくないとおっしゃっているので、あくまでクイズにしっかり取り組んだ人に続きを読んでほしい。この記事の意図はクイズを解いた後の考察である。

そして最後に、この記事の続きに厳密な解法は載っていない。まだ考えている途中であり、メモ書きのようなものであることを断っておく。

これ以下よりクイズの定義や考え方を述べていく。

クイズの設定

このクイズはいわゆるひっかけ問題ではなく、正攻法で唯一解が求まるものである。

  • 4×4個の点からなる格子点に線分を引き、正方形を作る。このとき、正方形はいくつ作れるか？
  • 線分の終点は格子点の上になければならない。
  • 正方形の頂点は2つの線分の交点から成る。頂点は格子点上になくともよい。
  • 大きな正方形が別の小さな正方形を内包していても、それぞれを別として数える。
  • 合同な正方形であっても、傾きや位置が異なればそれぞれを別として数える。

できれば図で説明したいが、面倒なので置いておく。気が向いたら追記しよう。

素朴な解法

あまり深く考えずに数え上げると、出てくる答えはおそらく14個になるだろう。別の視点に気がつけば新しい4個が見つかり、さらに注意深く考えれば2個が見つかる。これらの計20個を答えるパターンが多そうに思われるが、解答は20個ではない。もっとたくさんある。

頂点が格子点上になくても構わないことに気がつけば、あとはきちんと場合分けすることで解答を求められるはずだ。

この問題を解くコツは、傾きの異なる線分を漏れだぶりなく数え上げることである。

線分の傾きの範囲を (-π/4, π/4] に限定すれば、直交する線分の傾きが一対一に対応する。各傾きの組ごとに引ける線分をすべて引き、そこから正方形をすべて数え上げれば解に至れる。

もう少し工夫するなら、[0, π/4] の範囲で線分の傾きを探索し、鏡映反転して数えてもいいだろう。ただし、傾きが0およびπ/4の場合は傾きの組が鏡映対称であるため、区別して考える必要がある。

数え上げるメソッドを考えたい

私は解く過程で傾きの探索を目視で行ってしまったが、どうやら規則性が感じられた。なんとなく有理数と素数が関係しているような気がする。

プログラムで数え上げるとしたらどんな方針がいいだろう？ 傾きごとに線分を作り、線分の組ごとに交点を求め、ユニークな交点から4点を取り出す？

今日はちょっと考えるには頭が働かないので、ぜひアイデアがあれば教えてほしい。