趙紅濤，裴四寶

（華北電力大學(xué)數(shù)理學(xué)院，北京102206）

0 引言

1977年Erd?s和Silverman提出這樣一個(gè)問題：確定最大整數(shù)f（n），使得從平面上任意n個(gè)點(diǎn)的集合中可以找到f（n）個(gè)點(diǎn)，且這些點(diǎn)中任意三個(gè)點(diǎn)不會(huì)構(gòu)成一個(gè)直角三角形.他們得到對于一個(gè) k×k的網(wǎng)格點(diǎn)中有 f（k2）≤2k－2，Erd?s證明了，并且他和Silverman猜想有.1980年H.L.Abbott在文獻(xiàn)[1]中證明了Erd?s和Silverman的猜想且有，他也指出 Erd?s和 Silverman的強(qiáng)猜想 f（k2）＝2k－2是錯(cuò)誤的，同時(shí)給出了一個(gè)反例的定理，即當(dāng)k≥5時(shí)，有f（k2＋k－4）≤2k－3.1995年Gamble B，Pulleyblank W，Reed B等人在文獻(xiàn)[2]中探究了從二維平面上的一個(gè)給定集合中尋找無直角的最大子集的復(fù)雜性，他們證明了這類問題的計(jì)算是NP-難的.2009年Gy.Elekes在文獻(xiàn)[3]中證明得到.2011年Viktor Harangi，Tamas Keleti等人在文獻(xiàn)[4]中研究了多大的Hausdorff維數(shù)保證一個(gè)給定角.隨后，關(guān)于點(diǎn)集中不出現(xiàn)直角的研究由歐氏空間轉(zhuǎn)為有限域上的討論，首先是2015年Michael Bennett在文獻(xiàn)[5]中研究了有限域上向量空間中的一些Erd?s-Falconer類問題，他證明了在有限域中不含直角的點(diǎn)集的最大基數(shù)，在有限域中過原點(diǎn)的任意兩個(gè)點(diǎn)不構(gòu)成直角的點(diǎn)集的最大基數(shù).2016年Ge和Shangguan在文獻(xiàn)[6]中利用多項(xiàng)式方法對有限域中不含直角的點(diǎn)集的最大基數(shù)給出了新的上界，并且得到此最大基數(shù)，其中n為有限域的維數(shù)，q為素?cái)?shù).

通過Erd?s和Silverman對于k×k的網(wǎng)格點(diǎn)中任意三點(diǎn)不構(gòu)成直角的最大點(diǎn)集的基數(shù)為f（k2）≤2k－2的討論，本文主要研究了m×n網(wǎng)格點(diǎn)中不出現(xiàn)直角的最大點(diǎn)集的基數(shù)，通過利用坐標(biāo)投影法和代數(shù)法分別給出了證明，并得到了此最大點(diǎn)集的構(gòu)造；最后給出了一些關(guān)于平面網(wǎng)格點(diǎn)中有待解決的新問題.

1 平面網(wǎng)格點(diǎn)中不出現(xiàn)直角的最大點(diǎn)集

Erd?s和Silverman給出：對于平面上n×n的網(wǎng)格點(diǎn)中，不出現(xiàn)直角的最大點(diǎn)集的基數(shù)為2n－2.因而，對于在平面上m×n的網(wǎng)格點(diǎn)中，是否會(huì)有類似的結(jié)果，比如不構(gòu)成直角三角形的最大點(diǎn)集的基數(shù)為m＋n－2.以下本文將用坐標(biāo)投影法和代數(shù)方法分別證明這個(gè)結(jié)果是正確的.并且令平面上m×n的網(wǎng)格點(diǎn)中不出現(xiàn)直角的最大點(diǎn)集的基數(shù)為 f（m，n）.

定理1在平面上的m×n網(wǎng)格點(diǎn)中，f（m，n）＝m＋n－2.

證明：（1）坐標(biāo)投影法

對于平面上的任意一個(gè)m×n網(wǎng)格點(diǎn)，在滿足任意三個(gè)點(diǎn)不構(gòu)成直角的條件下，一定能夠找到該網(wǎng)格點(diǎn)上大矩形的四個(gè)頂點(diǎn)中必有兩個(gè)點(diǎn)是不能取的，否則它們會(huì)出現(xiàn)直角.所以選取這兩個(gè)空點(diǎn)中任意一個(gè)點(diǎn)作為原點(diǎn)，同時(shí)以該點(diǎn)所對應(yīng)大矩形的邊為坐標(biāo)軸作一個(gè)平面直角坐標(biāo)系O－xy，如圖1所示.

圖1 平面上10×20的網(wǎng)格點(diǎn)

為了尋找網(wǎng)格點(diǎn)中無直角的最大點(diǎn)集，應(yīng)該盡量多的選擇使任意三個(gè)點(diǎn)不構(gòu)成直角的點(diǎn)，對于這類構(gòu)造得到的點(diǎn)集，可以分三種情形：1）點(diǎn)在x軸或y軸上；2）兩個(gè)及兩個(gè)以上點(diǎn)的橫坐標(biāo)或縱坐標(biāo)相同；3）其他情形的點(diǎn).對于這三種類型的點(diǎn)，在使用投影法將這些點(diǎn)投影到坐標(biāo)軸上的過程中，優(yōu)先安排第一類點(diǎn)，然后考慮第二類點(diǎn)的投影，最后進(jìn)行第三類點(diǎn)的投影.

1）點(diǎn)在x軸或y軸上

對于這種類型的點(diǎn)，仍然保持點(diǎn)的位置不變.

2）兩個(gè)及兩個(gè)以上點(diǎn)的橫坐標(biāo)或縱坐標(biāo)相同（不包含坐標(biāo)軸上的點(diǎn)）

對于這種類型的點(diǎn)，可以將這些點(diǎn)投影到坐標(biāo)軸上，而不會(huì)影響原點(diǎn)集的總個(gè)數(shù)，這是因?yàn)閮蓚€(gè)及兩個(gè)以上的點(diǎn)處于同一直線上時(shí)，它們有相同的橫坐標(biāo)或者縱坐標(biāo)，那么就不能再出現(xiàn)與它們縱坐標(biāo)或者橫坐標(biāo)相同的點(diǎn).（如圖2，兩個(gè)黑點(diǎn)確定后，白色虛點(diǎn)則不能出現(xiàn)）

圖2 平面網(wǎng)格點(diǎn)中縱坐標(biāo)相同的點(diǎn)的投影

3）其他情形的點(diǎn)

對于這種情況的點(diǎn)，要么是非坐標(biāo)軸上的單個(gè)點(diǎn)，要么點(diǎn)與點(diǎn)之間是處于對角的情形，這類點(diǎn)可以將其投影在前兩類點(diǎn)投影后的坐標(biāo)軸仍為空點(diǎn)處的位置，并且它不會(huì)影響點(diǎn)集總數(shù)的變化，這里要求任意一個(gè)點(diǎn)不與其他任一點(diǎn)處于同一條直線，否則屬于第二種情形考慮.點(diǎn)集投影示例如圖3（其中，黑點(diǎn)表示未投影或投影后點(diǎn)的位置，白色虛點(diǎn)表示投影前點(diǎn)的位置）.

圖3 平面網(wǎng)格點(diǎn)中單個(gè)點(diǎn)與對角點(diǎn)的投影

由于滿足條件的點(diǎn)都可以通過以上三種情形進(jìn)行投影，在規(guī)定的順序下最后可以將所有點(diǎn)投影到x軸和y軸上，并使每個(gè)點(diǎn)都不重復(fù)投影，投影后所得到的點(diǎn)數(shù)最多的情形如圖4.

圖4 平面網(wǎng)格點(diǎn)中投影后所得到的點(diǎn)數(shù)最多的情形

顯然，這樣所構(gòu)造的點(diǎn)都不能構(gòu)成直角三角形，并且圖4中的點(diǎn)集情形就是平面上m×n網(wǎng)格點(diǎn)中不出現(xiàn)直角的最大點(diǎn)集，又由坐標(biāo)軸上的點(diǎn)總數(shù)為m＋n－1，而原點(diǎn)為空點(diǎn)，因此有 f（m，n）＝m＋n－2.

（2）代數(shù)法

由圖1可知，建立坐標(biāo)系O－xy后，m×n網(wǎng)格點(diǎn)就是橫坐標(biāo)介于0和n－1之間，縱坐標(biāo)介于0和m－1之間的整點(diǎn)構(gòu)成的網(wǎng)格點(diǎn).那么假設(shè)，即 P 表示平面上m×n網(wǎng)格點(diǎn)中不出現(xiàn)直角的最大點(diǎn)集；

Px＝，Px表示該網(wǎng)格點(diǎn)中滿足條件且每行點(diǎn)集的點(diǎn)數(shù)大于1的所有點(diǎn)集；

Py＝，Py表示該網(wǎng)格點(diǎn)中滿足條件且每列點(diǎn)集的點(diǎn)數(shù)大于1的所有點(diǎn)集；

顯然有 Px∩Py＝?，

當(dāng) m＝2或n＝2時(shí)，m×n網(wǎng)格點(diǎn)中的最大點(diǎn)集的基數(shù)為f（m，n）＝n或f（m，n）＝m.

當(dāng)m≠2且n≠2時(shí)，m×n網(wǎng)格點(diǎn)中的每行或每列的單點(diǎn)個(gè)數(shù)必小于等于m－1或n－1，否則f（m，n）不是網(wǎng)格點(diǎn)中的最大點(diǎn)集的基數(shù)，與假設(shè)矛盾.

因此有，2f（m，n）－m－n＋2≤f（m，n），則有 f（m，n）≤m＋n－2.

綜上所述，f（m，n）＝m＋n－2.

2 結(jié)論與展望

本文主要是對二維平面網(wǎng)格點(diǎn)中不出現(xiàn)直角的最大點(diǎn)集進(jìn)行討論，得到了平面上m×n網(wǎng)格點(diǎn)中不出現(xiàn)直角的最大點(diǎn)集的基數(shù)為m＋n－2，并分別給出坐標(biāo)投影法與代數(shù)法的兩種證明；另外，如果將網(wǎng)格點(diǎn)中任意三個(gè)點(diǎn)不構(gòu)成直角的問題轉(zhuǎn)化為網(wǎng)格點(diǎn)中過原點(diǎn)而不構(gòu)成直角的問題，那么對于n×n網(wǎng)格點(diǎn)與m×n網(wǎng)格點(diǎn)中過原點(diǎn)而無直角的最大點(diǎn)集的基數(shù)分別是多少呢？這也是我們下一步將要研究的內(nèi)容.

[1]ABBOTT H L.On a conjecture ofErd?s and Silverman in combinatorial geometry[J].Journal of Combinatorial Theory，1980，29（3）：380-381.

[2]GAMBLE B，PULLEYBLANK W，REED B，et al.Right angle free subsets in the plane[J].Graphs＆Combinatorics，1995，11（2）：121-129.

[3]ELEKES G.A note on a problem of Erd?s on right angles[J].Discrete Mathematics，2009，309（16）：5253-5254.

[4]HARANGI V，KELETI T，KISS G，et al.Howlarge dimension guarantees a given angle?[J].Monatshefte Für Mathematik，2012，171（2）：169-187.

[5]BENNETTM.Extremal results regardingright angles in vector spaces over finite fields[EB/OL].[2017-03-23].https://arxiv.org/pdf/1511.08942.pdf.

[6]GE G，SHANGGUAN C.Rank counting and maximum subsets ofcontaining no right angles[EB/OL].[2017-03-23].https://arxiv.org/abs/1612.08255.