数长方形

如果数得足够仔细,能看出在一个3乘2的长方形网格中包含有18个不同大小的长方形,如下图所示:

如图 enter image description here
尽管没有一个长方形网格中包含有恰好两百万个长方形,但有许多长方形网格中包含的长方形数目接近两百万,求其中最接近这一数目的长方形网格的面积。

思路
以图中长方形为例,有4条竖线,3条横线,其中两对横线和两对竖线能组成1个长方形,横线间的差就是长方形的高度,竖线之差就是宽度。用SQL表示如下:

with x as(select level x from dual connect by level<=4),
y as(select level y from dual connect by level<=3)
select (x2.x-x1.x)width,(y2.y-y1.y)hight,count(*)
from x x1,x x2,y y1,y y2
where x2.x>x1.x and y2.y>y1.y
group by (x2.x-x1.x),(y2.y-y1.y)
order by 1,2;

WIDTH      HIGHT   COUNT(*)
----- ---------- ----------
    1          1          6
    1          2          3
    2          1          4
    2          2          2
    3          1          2
    3          2          1

分析

1x1 : (4-1)(3-1) =6
1x2 : (4-1)(3-2) =3

2x1 : (4-2)(3-1) =4
2x2 : (4-2)(3-2) =2

3x1 : (4-3)(3-1) =2
3x2 : (4-3)(3-2) =1

=(4-1)(3*2-sum(1->2))
+(4-2)(3*2-sum(1->2))
+(4-3)(3*2-sum(1->2))


=(4*3-sum(1->3))(3*2-sum(1->2))
=(12-6)*(6-3)
=18

把4 和 3 用m 和 n代替

可以推测:

对于m*n的长方形,和为
(m*(m-1)-(1+m-1)*(m-1)/2))
*(n*(n-1)-(1+n-1)*(n-1)/2))
=m(m-1)n(n-1)/4

如果把直线根数改成长方形的宽度和高度 则

和=m(m+1)n(n+1)/4
设m是宽度和高度中较大者
则和必<=(m(m+1)/2)^2且>=(n(n+1)/2)^2

面积=mn,和最接近20000,实际就是求mn的最小值

解不等式m*m+m-2sqrt(2000000)>=0
m>=方程m*m+m-2sqrt(2000000)=0的较大的根 1/2(-1+sqrt((1+4*2000sqrt(2))

SQL> select 1/2*(-1+sqrt(1+4*2000*sqrt(2)))a from dual;

         A
----------
52.6853093

所以m最小值是53,n最大值是53

with m as(select level+52 m from dual connect by level<=100),
n as(select level n from dual connect by level<=53)
select min(m*(m+1)*n*(n+1)/4-2e6) a from m,n where abs(m*(m+1)*n*(n+1)/4-2e6)<=1000;

     A
------
    -2


with m as(select level+52 m from dual connect by level<=100),
n as(select level n from dual connect by level<=53),
min_diff as(select min(m*(m+1)*n*(n+1)/4-2e6) a from m,n where abs(m*(m+1)*n*(n+1)/4-2e6)<=1000)
select m,n,m*n from m,n where m*(m+1)*n*(n+1)/4-2e6=(select a from min_diff);

     M          N        M*N
------ ---------- ----------
    77         36       2772

有些不完备的地方,
1. 不知道怎么证明-2是最接近的。要不就从1、-1开始测试。
2. m的上限怎么确定,这里100是碰巧,如果写成10就不能得到解