最小k x l 4つの単色点を見つけるためのグリッド

Question

Z X Zの各点がn個の色のうちの1つで色付けされているとします。

最小のkとlを見つけると、任意のk x lグリッドでは、長方形の頂点である4つの単色点を見つけることが保証されます。 N = 1の場合には

---

、最小（K、L）が（2,2）は明らかであろう

N = 2の場合には、私は4×4の着色グリッドどのを見つけましたまだ任意の単色の長方形をしていない：

$馬場\ AABB \ ABAA \ bbab $

は、それが自動的に検索させるための任意の計算方法はありますか？

私は最小のkおよびl（1と区別するために、次のL）は、このような式

が

k * L >= (k + L) * n 

ということでしょう

Answer 1

（私は参照用のみのpythonを知っている）あなたのアドバイス

が必要満足している。説明するには、可能な限り同じ色、例えば赤色のピクセルを配置するグリッド（k、L）を考えてください。 k + L - 1ピクセルが配置されると直ぐに、四角形の頂点にならずに別のピクセルを追加する余地はありません。

ので、すぐに我々は（K、L）、グリッド内の同じ色のk + Lピクセルを数えるように、少なくとも一つの、このような頂点リストが存在すると言うことは安全です。

ここでは、グリッド内に任意に2色を配置すると考えます。どんな配置でも、少なくともk * L/2ピクセルのが最も多く、の色が使用されると言えます。従って、k * L/2がk + L以上であれば、少なくとも1つのそのような矩形が最も使用される色の中に見出されると仮定することは安全である。

私たちはk * L/3と考えていますが、n色の場合はk * L/n >= k + Lとなります。