puzzleup 2011

newkid

趁脑子还没糊涂把证明记录下来。
首先N=4不是最小值，从上面35个反例中任选一个即可。
现在来证明N=5的时候，不管如何分布，总能找到两行两列的交叉点为同一颜色。
分三种情况：
1. 当里面至少有一行全为黑色；
2. 当里面至少有一行有一格红色+四格黑色；
3. 当里面至少有一行有两格红色+三格黑色；
其余情况无需证明，因为红黑是对称的，比如 三格红色+两格黑色其实就是第三种情况。

1. 当里面至少有一行全为黑色，设为B
   1.1如果其他四行里至少有一行的黑色格子数>=2，则根据抽屉原理，该行和B至少有两列同为黑色，构成了四个黑色交叉点；
   1.2否则，其他四行的黑色<2, 则四行的红色均>=4, 任取其中两行构成了四个红色交叉点。
   
   把两种颜色颠倒一下，#1的证明也适用有一行全红色的情况。

2. 假设#1不满足，但是至少有一行有一格红色+四格黑色，设为B
   2.1如果其他四行里至少有一行的黑色格子数>=3，则根据抽屉原理，该行和B至少有两列同为黑色，构成了四个黑色交叉点；
   2.2否则，其他四行的黑色<3, 则四行的红色均>=3

      取出红色>=3的三行，设为R1,R2,R3
      根据抽屉原理,R1和R2至少有一列同为红色。
      五列划分三个区：1区为R1的红色列，2区为R2的红色列，3区为公共红色列。
      考察R3的三个红色列，在三个区的分布情况。
      落在同一区：假设1区则和R1构成四个红色交叉点，2区则和R2构成四个红色交叉点，3区则和R1或R2都能构成四个红色交叉点。
      落在两个区：必定有两列在同一区。假设这两列在1区则和R1构成四个红色交叉点，2区则和R2构成四个红色交叉点，3区则和R1或R2都能构成四个红色交叉点。
      落在三个区：取出落在1,3区的两列，和R1构成四个红色交叉点。
      
      此证明同样适用于三行的黑色格子数>=3的情形。

   2.2的证明同样适用于"至少有一行有一格黑色+四格红色"的情形
   
3. 假设#1,#2都不成立，则五行全部仅有两种可能：(A)两格红色+三格黑色，或者(B)两格黑色+三格红色
   3.1 两格红色+三格黑色(A) 占了三行或三行以上：见2.2证明；
   3.2 否则，有两格黑色+三格红色(B)必定占了三行或三行以上，同样适用2.2证明。

〇〇

newkid 发表于 2011-11-18 04:16
趁脑子还没糊涂把证明记录下来。
首先N=4不是最小值，从上面35个反例中任选一个即可。
现在来证明N=5的时 ...

nice

〇〇

newkid 发表于 2011-11-17 22:47
嵌套表在这里是没有必要的，用传统的拼接、解析字符串就可以：

WITH b AS (

利用前缀删除和0，1等价能减少测试次数
比如0011和0010必然是符合的，就预先排除，
0000和1111等价，那么只要测试1半,0111就够了

newkid

你来改改？
但是现在已经够快的了。

〇〇

newkid 发表于 2011-11-21 22:40
你来改改？
但是现在已经够快的了。

把题目改成n*n的矩阵里面，求无论怎么放，最大的一个m*m矩阵，其各个元素都是同一个数

〇〇

SQL> SQL> select :n from dual;

        :N
----------
         8

已用时间:  00: 00: 00.00
SQL> 15            
SP2-0226: 行号  无效
SQL> WITH b AS (
  2    SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') str
  3     FROM (SELECT 1 n FROM DUAL UNION ALL SELECT 0 FROM DUAL)
  4     WHERE LEVEL=:N
  5     CONNECT BY LEVEL<=:N
  6  )
  7  ,t(lvl,all_str,str) AS (
  8  SELECT 1,CAST(str AS VARCHAR2(30)),str FROM b
  9  UNION ALL
10  SELECT t.lvl+1
11        ,t.all_str||b.str
12        ,b.str
13  FROM t,b
14  WHERE t.lvl<:N
15        AND t.str<b.str and substr(t.str,1,2)<>substr(b.str,1,2)
16        AND NOT EXISTS (SELECT 1
17                         FROM DUAL
18                         WHERE NVL(REPLACE(LPAD(SUBSTR(t.all_str,(LEVEL-1)*:N+1,:N)+b.str,:N,'0'),'1'),'0')
19                               NOT IN ('0','2','20','02')
20                         CONNECT BY LEVEL<=t.lvl
21                       )
22  )
23  SELECT all_str FROM t WHERE lvl=:N;


未选定行

已用时间:  00: 00: 01.96
SQL> SQL> WITH b AS (
  2    SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') str
  3     FROM (SELECT 1 n FROM DUAL UNION ALL SELECT 0 FROM DUAL)
  4     WHERE LEVEL=:N
  5     CONNECT BY LEVEL<=:N
  6  )
  7  ,t(lvl,all_str,str) AS (
  8  SELECT 1,CAST(str AS VARCHAR2(30)),str FROM b
  9  UNION ALL
10  SELECT t.lvl+1
11        ,t.all_str||b.str
12        ,b.str
13  FROM t,b
14  WHERE t.lvl<:N
15        AND t.str<b.str --and substr(t.str,1,2)<>substr(b.str,1,2)
16        AND NOT EXISTS (SELECT 1
17                         FROM DUAL
18                         WHERE NVL(REPLACE(LPAD(SUBSTR(t.all_str,(LEVEL-1)*:N+1,:N)+b.str,:N,'0'),'1'),'0')
19                               NOT IN ('0','2','20','02')
20                         CONNECT BY LEVEL<=t.lvl
21                       )
22  )
23  SELECT all_str FROM t WHERE lvl=:N;


未选定行

已用时间:  00: 00: 03.22

〇〇

为什么少了17行
SQL> WITH b AS (
  2    SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') str
  3     FROM (SELECT 1 n FROM DUAL UNION ALL SELECT 0 FROM DUAL)
  4     WHERE LEVEL=:N
  5     CONNECT BY LEVEL<=:N
  6  )
  7  ,t(lvl,all_str,str) AS (
  8  SELECT 1,CAST(str AS VARCHAR2(30)),str FROM b
  9  UNION ALL
10  SELECT t.lvl+1
11        ,t.all_str||b.str
12        ,b.str
13  FROM t,b
14  WHERE t.lvl<:N
15        AND t.str<b.str and substr(t.str,1,2)<>substr(b.str,1,2)
16        AND NOT EXISTS (SELECT 1
17                         FROM DUAL
18                         WHERE NVL(REPLACE(LPAD(SUBSTR(t.all_str,(LEVEL-1)*:N+1,:N)+b.str,:N,'0'),'1'),'0')
19                               NOT IN ('0','2','20','02')
20                         CONNECT BY LEVEL<=t.lvl
21                       )
22  )
23  SELECT all_str FROM t WHERE lvl=:N;


ALL_STR
------------------------------------------------------------------------------------------------------------------------------------
0011011010001101
0011010110001110
0011010010011110
0011011010011100
0011010110011100
0011010110011110
0010010110011100
0010010110011110
0010011110011100
0011011010101100
0011011010101101
0001011110101100
0001011010101100
0001011010101101
0011010110101100
0011010010101101
0010010110111100
0001011010111100

已选择18行。

已用时间:  00: 00: 00.01

〇〇

原来没考虑
01
01
这种

newkid

M>2就麻烦多了，不能够用两两相加一下子判断出来，要把以前的1行，两行，... M-1行的所有组合中有M位相同的都保存起来。单用SQL恐怕搞不出来。

newkid

#18 Right Triangles on a Square

Four right triangles are drawn superimposed on the four edges of a square.  The conditions are:

.Each triangle has a common edge with the square.
.The four triangles have different areas.
.All of the edges have integer lengths.
What is the possible minimum value for the length of an edge of the square?


四个直角三角形叠放在一个正方形的四条边上。条件是：
每个三角形和正方形共享一条边。
四个三角形的面积各不相同。
所有的边长都是整数。

正方形的边长最小可能是多少？

这个很老套了：
WITH nums AS (
SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=100
)
,tri AS (
SELECT n1.n a,n2.n b, SQRT(n1.n*n1.n+n2.n*n2.n) c
  FROM nums n1,nums n2
WHERE n1.n<=n2.n
       AND MOD(SQRT(n1.n*n1.n+n2.n*n2.n),1)=0
)
SELECT *
  FROM tri t1,tri t2,tri t3,tri t4
WHERE t1.a*t1.b<t2.a*t2.b AND t2.a*t2.b<t3.a*t3.b AND t3.a*t3.b<t4.a*t4.b
       AND (t1.a IN (t2.a,t2.b,t2.c) AND t1.a IN (t3.a,t3.b,t3.c) AND t1.a IN (t4.a,t4.b,t4.c)
            OR t1.b IN (t2.a,t2.b,t2.c) AND t1.b IN (t3.a,t3.b,t3.c) AND t1.b IN (t4.a,t4.b,t4.c)
            OR t1.c IN (t2.a,t2.b,t2.c) AND t1.c IN (t3.a,t3.b,t3.c) AND t1.c IN (t4.a,t4.b,t4.c)
           )
ORDER BY t1.a,t1.b
;


         A          B          C          A          B          C          A          B          C          A          B          C
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
         5         12         13          9         12         15         12         16         20         12         35         37
         7         24         25         10         24         26         18         24         30         24         32         40
         7         24         25         10         24         26         18         24         30         24         45         51
         7         24         25         10         24         26         18         24         30         24         70         74
         7         24         25         10         24         26         24         32         40         24         45         51
         7         24         25         24         32         40         24         45         51         24         70         74
         7         24         25         10         24         26         24         45         51         24         70         74
         7         24         25         18         24         30         24         32         40         24         45         51
         7         24         25         18         24         30         24         32         40         24         70         74
         7         24         25         18         24         30         24         45         51         24         70         74
         7         24         25         10         24         26         24         32         40         24         70         74
         9         12         15          8         15         17         15         20         25         15         36         39
         9         40         41         24         32         40         30         40         50         40         75         85
         9         40         41         24         32         40         30         40         50         40         96        104
         9         40         41         24         32         40         40         42         58         40         75         85
         9         40         41         40         42         58         40         75         85         40         96        104
         9         40         41         24         32         40         40         75         85         40         96        104
         9         40         41         30         40         50         40         42         58         40         75         85
         9         40         41         30         40         50         40         42         58         40         96        104
         9         40         41         30         40         50         40         75         85         40         96        104
         9         40         41         24         32         40         30         40         50         40         42         58
         9         40         41         24         32         40         40         42         58         40         96        104
        10         24         26         18         24         30         24         32         40         24         45         51
        10         24         26         24         32         40         24         45         51         24         70         74
        10         24         26         18         24         30         24         45         51         24         70         74
        10         24         26         18         24         30         24         32         40         24         70         74
        11         60         61         25         60         65         32         60         68         45         60         75
        11         60         61         60         63         87         60         80        100         60         91        109
        11         60         61         25         60         65         32         60         68         60         80        100
        11         60         61         25         60         65         32         60         68         60         91        109
        11         60         61         25         60         65         36         48         60         32         60         68
        11         60         61         25         60         65         36         48         60         45         60         75
        11         60         61         25         60         65         36         48         60         60         63         87
        11         60         61         25         60         65         36         48         60         60         80        100
        11         60         61         25         60         65         36         48         60         60         91        109
        11         60         61         25         60         65         45         60         75         60         63         87
        11         60         61         25         60         65         45         60         75         60         80        100
        11         60         61         25         60         65         45         60         75         60         91        109
        11         60         61         25         60         65         60         63         87         60         80        100
        11         60         61         25         60         65         60         63         87         60         91        109
        11         60         61         25         60         65         60         80        100         60         91        109
        11         60         61         32         60         68         45         60         75         60         63         87
        11         60         61         32         60         68         45         60         75         60         80        100
        11         60         61         32         60         68         45         60         75         60         91        109
        11         60         61         32         60         68         60         63         87         60         80        100
        11         60         61         32         60         68         60         63         87         60         91        109
        11         60         61         32         60         68         60         80        100         60         91        109
        11         60         61         36         48         60         32         60         68         45         60         75
        11         60         61         36         48         60         32         60         68         60         63         87
        11         60         61         36         48         60         32         60         68         60         80        100
        11         60         61         36         48         60         32         60         68         60         91        109
        11         60         61         36         48         60         45         60         75         60         63         87
        11         60         61         36         48         60         45         60         75         60         80        100
        11         60         61         36         48         60         45         60         75         60         91        109
        11         60         61         36         48         60         60         63         87         60         80        100
        11         60         61         36         48         60         60         63         87         60         91        109
        11         60         61         36         48         60         60         80        100         60         91        109
        11         60         61         45         60         75         60         63         87         60         80        100
        11         60         61         45         60         75         60         63         87         60         91        109
        11         60         61         45         60         75         60         80        100         60         91        109
        11         60         61         25         60         65         32         60         68         60         63         87
        12         16         20         15         20         25         20         21         29         20         48         52
        12         16         20         20         21         29         20         48         52         20         99        101
        12         16         20         15         20         25         20         48         52         20         99        101
        12         16         20         15         20         25         20         21         29         20         99        101
        13         84         85         36         77         85         40         75         85         51         68         85
        13         84         85         35         84         91         63         84        105         80         84        116
        14         48         50         20         48         52         36         48         60         48         55         73
        14         48         50         20         48         52         36         48         60         48         64         80
        14         48         50         20         48         52         36         48         60         48         90        102
        14         48         50         20         48         52         48         55         73         48         64         80
        14         48         50         20         48         52         48         55         73         48         90        102
        14         48         50         20         48         52         48         64         80         48         90        102
        14         48         50         36         48         60         48         55         73         48         64         80
        14         48         50         36         48         60         48         55         73         48         90        102
        14         48         50         36         48         60         48         64         80         48         90        102
        14         48         50         48         55         73         48         64         80         48         90        102
        15         20         25         20         21         29         20         48         52         20         99        101
        15         36         39         27         36         45         36         48         60         36         77         85
        16         63         65         25         60         65         33         56         65         39         52         65
        16         63         65         33         56         65         39         52         65         65         72         97
        16         63         65         25         60         65         39         52         65         65         72         97
        16         63         65         25         60         65         33         56         65         65         72         97
        18         24         30         16         30         34         30         40         50         30         72         78
        18         24         30         24         32         40         24         45         51         24         70         74
        18         80         82         48         64         80         39         80         89         80         84        116
        18         80         82         48         64         80         39         80         89         60         80        100
        18         80         82         48         64         80         60         80        100         80         84        116
        18         80         82         39         80         89         60         80        100         80         84        116
        20         48         52         36         48         60         48         55         73         48         64         80
        20         48         52         48         55         73         48         64         80         48         90        102
        20         48         52         36         48         60         48         64         80         48         90        102
        20         48         52         36         48         60         48         55         73         48         90        102
        21         72         75         30         72         78         54         72         90         65         72         97
        21         72         75         30         72         78         54         72         90         72         96        120
        21         72         75         54         72         90         65         72         97         72         96        120
        21         72         75         45         60         75         40         75         85         75        100        125
        21         72         75         30         72         78         65         72         97         72         96        120
        24         32         40         30         40         50         40         42         58         40         75         85
        24         32         40         40         42         58         40         75         85         40         96        104
        24         32         40         30         40         50         40         75         85         40         96        104
        24         32         40         30         40         50         40         42         58         40         96        104
        25         60         65         32         60         68         45         60         75         60         63         87
        25         60         65         60         63         87         60         80        100         60         91        109
        25         60         65         32         60         68         45         60         75         60         91        109
        25         60         65         32         60         68         60         63         87         60         80        100
        25         60         65         32         60         68         60         63         87         60         91        109
        25         60         65         32         60         68         60         80        100         60         91        109
        25         60         65         33         56         65         39         52         65         65         72         97
        25         60         65         36         48         60         32         60         68         45         60         75
        25         60         65         36         48         60         32         60         68         60         63         87
        25         60         65         36         48         60         32         60         68         60         80        100
        25         60         65         36         48         60         32         60         68         60         91        109
        25         60         65         36         48         60         45         60         75         60         63         87
        25         60         65         36         48         60         45         60         75         60         80        100
        25         60         65         36         48         60         45         60         75         60         91        109
        25         60         65         36         48         60         60         63         87         60         80        100
        25         60         65         36         48         60         60         63         87         60         91        109
        25         60         65         36         48         60         60         80        100         60         91        109
        25         60         65         45         60         75         60         63         87         60         80        100
        25         60         65         45         60         75         60         63         87         60         91        109
        25         60         65         45         60         75         60         80        100         60         91        109
        25         60         65         32         60         68         45         60         75         60         80        100
        27         36         45         24         45         51         28         45         53         45         60         75
        30         40         50         40         42         58         40         75         85         40         96        104
        30         72         78         54         72         90         65         72         97         72         96        120
        32         60         68         45         60         75         60         63         87         60         80        100
        32         60         68         60         63         87         60         80        100         60         91        109
        32         60         68         45         60         75         60         80        100         60         91        109
        32         60         68         45         60         75         60         63         87         60         91        109
        36         48         60         32         60         68         45         60         75         60         63         87
        36         48         60         32         60         68         45         60         75         60         80        100
        36         48         60         32         60         68         45         60         75         60         91        109
        36         48         60         32         60         68         60         63         87         60         80        100
        36         48         60         32         60         68         60         63         87         60         91        109
        36         48         60         60         63         87         60         80        100         60         91        109
        36         48         60         45         60         75         60         63         87         60         80        100
        36         48         60         45         60         75         60         63         87         60         91        109
        36         48         60         45         60         75         60         80        100         60         91        109
        36         48         60         48         55         73         48         64         80         48         90        102
        36         48         60         32         60         68         60         80        100         60         91        109
        45         60         75         60         63         87         60         80        100         60         91        109
        48         64         80         39         80         89         60         80        100         80         84        116

143 rows selected.

Elapsed: 00:00:01.39

最小边长=12