PUZZLEUP 2014

newkid

把你的代码贴出来？
我的结果大同小异，验证如下：

select * from g;

    FROM_P       TO_P
---------- ----------
         1          2
         1          3
         1          4
         1          5
         2          1
         2          6
         2          7
         2          8
         3          9
         3         10
         3         11
         3         12
         4         13
         4         14
         4         15
         4         16
         5         17
         5         18
         5         19
         5         20
         6          9
         6         10
         6         11
         6         12
         7         13
         7         14
         7         15
         7         16
         8         17
         8         18
         8         19
         8         20
         9          1
         9          6
         9          7
         9          8
        10          2
        10          3
        10          4
        10          5
        11         13
        11         14
        11         15
        11         16
        12         17
        12         18
        12         19
        12         20
        13          1
        13          6
        13          7
        13          8
        14          2
        14          3
        14          4
        14          5
        15          9
        15         10
        15         11
        15         12
        16         17
        16         18
        16         19
        16         20
        17          1
        17          6
        17          7
        17          8
        18          2
        18          3
        18          4
        18          5
        19          9
        19         10
        19         11
        19         12
        20         13
        20         14
        20         15
        20         16

80 rows selected.

验证：

SELECT from_p,COUNT(DISTINCT to_p) FROM (
SELECT g1.from_p
      ,g2.to_p
  FROM g g1, g g2
WHERE g1.to_p=g2.from_p
UNION ALL
SELECT * FROM g
)
GROUP BY from_p;


    FROM_P COUNT(DISTINCTTO_P)
---------- -------------------
         1                  20
         2                  20
         3                  20
         4                  20
         5                  20
         6                  20
         7                  20
         8                  20
         9                  20
        10                  20
        11                  20
        12                  20
        13                  20
        14                  20
        15                  20
        16                  20
        17                  20
        18                  20
        19                  20
        20                  20
        
        
SELECT from_p,SUM(in_cnt),SUM(out_cnt)
  FROM (
SELECT from_p,0 in_cnt,COUNT(*) out_cnt FROM g GROUP BY from_p
UNION ALL
SELECT to_p,COUNT(*),0 FROM g GROUP BY to_p
)
GROUP BY from_p
ORDER BY 1;

    FROM_P SUM(IN_CNT) SUM(OUT_CNT)
---------- ----------- ------------
         1           4            4
         2           4            4
         3           4            4
         4           4            4
         5           4            4
         6           4            4
         7           4            4
         8           4            4
         9           4            4
        10           4            4
        11           4            4
        12           4            4
        13           4            4
        14           4            4
        15           4            4
        16           4            4
        17           4            4
        18           4            4
        19           4            4
        20           4            4


X=21可以用很简单的反证法证明是不可能的，你再想想？

〇〇

newkid 发表于 2014-10-25 22:31
把你的代码贴出来？
我的结果大同小异，验证如下：

没看懂，怎么说明从每个点出来连到另一个点的路径

newkid

SELECT from_p,COUNT(DISTINCT to_p) FROM (
SELECT g1.from_p
      ,g2.to_p
  FROM g g1, g g2
WHERE g1.to_p=g2.from_p
UNION ALL
SELECT * FROM g
)
GROUP BY from_p;

第一个连接表示间接可达的所有点，UNION ALL直接可达的点，COUNT DISTINCT =20说明所有的点都可达。

peter1166

newkid 发表于 2014-10-25 22:31
把你的代码贴出来？
我的结果大同小异，验证如下：

惭愧， SQL 没弄出来。

newkid

假设X=21能够成立，那么从任何一个点出发都能得到如下的完全四叉树：


                    F
          |----B----G
          |         H
          |         I
          |
          |         J
          |----C----K
          |         L
          |         M
A --------|
          |
          |         N
          |----D----O
          |         P         
          |         Q
          |
          |         R
          |----E----W
                    T         
                    U
               

从中可以得到两个推论：
1. 不存在 P1->P2, P2->P1这样的情形。
每个点都必须连接尽可能多的不同的点，不能走“回头路”。
2. 不存在 P1->P2, P2->P3, P1->P3这样的情形。
P1到P3之间如果有近路，就不可能有另外的路径，因为P2要连接尽可能多的不同的点。

利用这两个推论可以反证X=21不成立，但是目前我的方法比较繁琐，两天前我以为找到简单的方法其实不管用。看看PETER能否想出来。

peter1166

newkid 发表于 2014-10-27 23:23
假设X=21能够成立，那么从任何一个点出发都能得到如下的完全四叉树：

谢谢， newkid 。 这个题真难，一有空就在想这个题， 尝试了几种想法都失败了，一直在想。  

newkid

我试着把证明写下来，有点烦，我怀疑有其他捷径但是一下子没找到。

假设X=21能够成立，那么从任何一个点出发都能得到如下的完全四叉树：


                    F
          |----B----G
          |         H
          |         I
          |
          |         J
          |----C----K
          |         L
          |         M
A --------|
          |
          |         N
          |----D----O
          |         P         
          |         Q
          |
          |         R
          |----E----S
                    T         
                    U
               

从中可以得到两个推论：
1. 不存在 P1->P2, P2->P1这样的情形。
每个点都必须连接尽可能多的不同的点，不能走“回头路”。
2. 不存在 P1->P2, P2->P3, P1->P3这样的情形。
P1到P3之间如果有近路，就不可能有另外的路径，因为P2要连接尽可能多的不同的点。

把上图的第三层分为四组：FGHI, JKLM, NOPQ, RSTU
推论3: 同组之间两两不可直达。这是从推论2得出的，比如F,G，如果F->G, 那么B到G就有两条通路了，这是违反推论2的。

BCDE想到达点A, 根据推论1不可能直达。比如B必须经过FGHI中的一个才能到达A。其他组亦然。
所以在第三层的点中，每组有且仅有一个直达点A。假设FJNR可以直达点A。那么，FJNR也间接可达第二层的BCDE。根据推论2, FJNR不可能直达BCDE。至此A的所有入度已满，没有其他点能直达A。

取出第三层中除FJNR之外的任意一点X。因为X不可能直达A, 所以X必须直达FJNR之中的任意一点，这样才能到达A。
因为前面已经论证过，FJNR都不能直达BCDE, 所以X要到达BCDE, 要么直达，要么通过第三层中除FJNR的其他点。
根据题目，X的出度为4, 为了到达A已经用掉了出度1, 那么剩下的三个出度要到达BCDE, 全部直达就不够用了，至少有一个出度是用来间接到达BCDE中的两个点。

至此得到推论4: 为了帮助X到达BCDE, 在FJNR之外的第三层的点中，必然至少存在一个点，它同时直达第二层(BCDE)中的两个点，或两个以上的点。

任选一个点，不妨设为G, 作为推论4中的点（其他点的证明都是等价的）。G为了到达A必须直达FJNR中的一点，根据推论3, G不能直达F。在JNR中任选一个，不妨选J, 作为G直达的点（其他点的证明都是等价的）。根据推论2, G不可直达J的上级C。根据推论1, G也不能直达B。这样第二层的BCDE已经排除了BC作为直达点，那么，因为G满足推论4, G必须同时直达D,E。DE所连接的第三层都是G间接可达的点。至此，G剩下未解决的目的地还有B,H,I,K,L,M。根据推论1，G不可直达B, 根据推论3, G不可直达H,I，因此G必须间接到达BHI。此时G已经用掉了三个出度JDE，GHI又不能直达，最后一个出度必须用在K,L,M中。在G直达的三个点J,D,E中，D,E的出度已满，而J不能够直达同组的KLM(推论3)。那么，无论G最后的一个出度选择K,L,M中的哪个，G都不可能到达剩下的两个点。因为KLM同组，根据推论3, 同组之间不可直达。

既然G不能到达所有的点，X=21的假设就是不成立的。

〇〇

newkid 发表于 2014-10-29 05:10
我试着把证明写下来，有点烦，我怀疑有其他捷径但是一下子没找到。

假设X=21能够成立，那么从任何一 ...

这是简单的还是繁琐的

lastwinner

newkid 发表于 2014-10-25 11:10
我忽然之间就想通了x=21的反证法，原来是这么简单。

抽屉原则不？

newkid

#14 Five Points

You will connect the five points given in the figure (the vertices of regular pentagon) by drawing straight lines.

-You will visit each of the points exactly one time.
-You won't lift your pencil from the paper while drawing.
-You can cross over the lines.

How many different shapes can be obtained?

Notes:
-Rotations and reflections will be counted seperately.
-A shape can not be counted as a new shape if it is obtained by just changing the direction
of the drawing between the two terminal points.

Four of shapes included in the solution are shown below.

你用直线将图中五个点（正五边形的顶点）连起来。

每个点恰好访问一次。
在画图的时候铅笔不能离开纸面。（加一句：纸张不能折叠）
线段可以交叉。

这样能得到多少个不同的图形？

注：
旋转和翻转被分开计算。
如果仅仅是改变线段端点间的画图方向，这样得到的图形不能算新图形。

答案中含有的四个图形如下所示。



http://www.puzzleup.com/2014/img/puzzle/2014/14_ek.jpg


-------------------
这不是很简单吗？