puzzleup 2011

newkid

续67楼证明第六题：


总点数为偶数时，用上述方法可知最小可能答案为零。
总点数为奇数时，用上述方法可知1为可能答案，现在要证明1是最小答案。

反证法：假设在总数N为奇数的情况下最小答案是0, 即任意点都至少有一个不连点。
现在要找一个反例，即在5个点中，没有任何一点和其他四点都相连。把和其他点全部相连的点称为中心点，现在的任务就是凑出这样一个5点组合，使得不存在中心点。
任取某点A,则必定有点B不与之相连。
把点AB选中。考察其他点C, 有两种情况：
1. 假设C所有不连点D既非A也非B, 则选ABCD，我们已凑足四个非中心点。
2. C的不连点在A,B中。此时C和除AB外的所有点相连。取任意点D, 则D与C相连。
   2.1 假设D的不连点E既非A也非B, 则选ABDE，我们已凑足四个非中心点。
   2.2 假设D的不连点在A,B中, 则选ABCD，我们已凑足四个非中心点。
至此我们证明了总有一种方法可以凑足四个非中心点，命名为ABCD。现在根据题意，剩下的N-4个点全部必须与ABCD同时相连，才满足任意5点中必有中心点的题设。
也就是说，剩下的N-4个点，它们的不连点总在N-4个点之中。
对剩下的N-4个点重复上述的“凑四点”步骤，直至最后，因为N为奇数，余数必定为1或者3。
当余数为1: 我们的凑四点步骤决定了剩下的点要和凑出的所有点相连，因此剩下的最后1点和N-1点都相连，破坏了最小答案为0的假设。
当余数为3: 前面的步骤决定了这3点的不连点就在此3点中，任意取前面的两个不连点，构成了5个非中心点，也破坏了题设。
因此0不是最小答案。

newkid

#11 Prime Sums

A number has the following properties:

The sum of every neighboring three numerals in this number is a prime number.

All of these sums are different than each other.

What is the largest possible value of this number?
一个数具备如下属性：它的每三位相邻数字之和为素数，而且这些素数各不相同。这个数最大可能为多少？

用纸笔比划一下：98656232011

newkid

这死鬼佬，一不小心着了他的道儿。
既然人肉出一个98开头的答案，只需检查99开头的就可以了：

WITH p AS (
SELECT rownum id,n
    FROM (SELECT LEVEL n FROM DUAL WHERE LEVEL>1 CONNECT BY LEVEL<27)
WHERE NOT EXISTS (SELECT 1 FROM DUAL WHERE LEVEL>1 AND MOD(n,LEVEL)=0 CONNECT BY LEVEL<n )
)
,t(str,path) AS (
SELECT CAST('99'||(n-18) AS VARCHAR2(20)), CAST(id AS VARCHAR2(10)) FROM p WHERE n-18 BETWEEN 0 AND 9
UNION ALL
SELECT t.str||(p.n-SUBSTR(t.str,-1,1)-SUBSTR(t.str,-2,1))
      ,t.path||p.id
  FROM t,p
WHERE INSTR(t.path,p.id)=0 AND p.n-SUBSTR(t.str,-1,1)-SUBSTR(t.str,-2,1) BETWEEN 0 AND 9
)
SELECT TO_CHAR(MAX(TO_NUMBER(str))) FROM t;
      
TO_CHAR(MAX(TO_NUMBER(STR)))
--------------------------------
99551110494

newkid

#12

Squares with Pawn

If you consider squares of all sizes, there are 204 squares on the chessboard above. How many of these squares contains an odd number of pawns?


有卒子的方块
在一个8X8的棋盘上有204个各种大小的正方形。带有奇数个卒子的正方形总共有几个？

图片：
http://www.puzzleup.com/2011/img/puzzle/2011/12.jpg

newkid

________________
|_|_|_|_|_|_|*|_|
|_|_|_|_|_|*|_|_|
|_|_|_|_|*|_|_|_|
|_|_|_|_|_|_|_|_|
|_|_|_|*|_|_|_|_|
|_|_|*|_|_|_|_|_|
|_|*|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|


WITH c AS (
SELECT x,y
  FROM (SELECT LEVEL x FROM DUAL CONNECT BY LEVEL<=8)
      ,(SELECT LEVEL y FROM DUAL CONNECT BY LEVEL<=8)
)
,sq AS (
SELECT ROWNUM id
      ,c1.x x1
      ,c1.y y1
      ,c2.x x2
      ,c2.y y2
  FROM c c1, c c2
WHERE c1.x<=c2.x AND c1.y<=c2.y AND c1.x-c2.x=c1.y-c2.y
)
,pawns AS (
SELECT 2 px,2 py FROM DUAL
UNION ALL SELECT 3,3 FROM DUAL
UNION ALL SELECT 4,4 FROM DUAL
UNION ALL SELECT 5,6 FROM DUAL
UNION ALL SELECT 6,7 FROM DUAL
UNION ALL SELECT 7,8 FROM DUAL
)
SELECT COUNT(MAX(1))
  FROM sq,pawns
WHERE px BETWEEN x1 AND x2
       AND py BETWEEN y1 AND y2
GROUP BY sq.id
HAVING MOD(COUNT(*),2)=1
;

60

〇〇

No: 12       October 12, 2011

Squares with Pawn If you consider squares of all sizes, there are 204 squares on the chessboard above. How many of these squares contains an odd number of pawns? [ You need to be a member of this site before you can submit an answer ]

来晚了，newkid已经解答了

newkid

最近几期的题目比较弱，要不一起来做做那个逻辑推理的附加题：自动猜测？

newkid

#13 Five Couples


Five married couples will sit around a round table. Although every sitting spot is marked by a name card, they do not notice the cards and sit randomly. Then, they realize that none of them is sitting on the spot marked for them or their spouses.

In how many different ways can this situation occur?

五对夫妇沿着一张圆桌入座。每个座位都有名字，但是他们没有注意到，因此入座是随机的。后来他们注意到没有一个人或者配偶的名字和座号牌能对应得上。

这样的不同情形可能有多少种？

这个题目应该隐含这样的前提：座号牌上的丈夫和妻子是紧挨着的，随机入座时丈夫和妻子也是紧挨着的。

WITH p AS (  ---- 编号并配对
SELECT n1||n2 pair,TRUNC(n1/2) pair_id
  FROM (SELECT LEVEL-1 n1 FROM DUAL CONNECT BY LEVEL<=10),(SELECT LEVEL-1 n2 FROM DUAL CONNECT BY LEVEL<=10)
WHERE n1<>n2 AND TRUNC(n1/2)=TRUNC(n2/2)
)
,s (pairs, id) AS (  ---- 五对的所有排列
SELECT CAST(pair AS VARCHAR2(10)),CAST(pair_id AS VARCHAR2(5)) FROM p
UNION ALL
SELECT s.pairs||p.pair,s.id||p.pair_id
  FROM p,s
WHERE INSTR(s.id,p.pair_id)=0
)
,t AS (
SELECT DISTINCT SUBSTR(pairs,n)||SUBSTR(pairs,1,n-1) AS pairs  ---- 去重复后得到五对排成圆环的所有坐法
  FROM (SELECT * FROM s WHERE LENGTH(id)=5)  ---- 五对的所有排列
      ,(SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=10)  ----- 循环挪动10种可能
)
SELECT (SELECT COUNT(*)
   FROM t,(SELECT '0123456789' str FROM DUAL) ------ 由于对称关系任取一种作为代表
  WHERE SUBSTR(t.pairs,1,1)<>SUBSTR(str,1,1)
        AND SUBSTR(t.pairs,2,1)<>SUBSTR(str,2,1)
        AND SUBSTR(t.pairs,3,1)<>SUBSTR(str,3,1)
        AND SUBSTR(t.pairs,4,1)<>SUBSTR(str,4,1)
        AND SUBSTR(t.pairs,5,1)<>SUBSTR(str,5,1)
        AND SUBSTR(t.pairs,6,1)<>SUBSTR(str,6,1)
        AND SUBSTR(t.pairs,7,1)<>SUBSTR(str,7,1)
        AND SUBSTR(t.pairs,8,1)<>SUBSTR(str,8,1)
        AND SUBSTR(t.pairs,9,1)<>SUBSTR(str,9,1)
        AND SUBSTR(t.pairs,10,1)<>SUBSTR(str,10,1)
       )*(SELECT COUNT(*) FROM t) AS cnt
   FROM DUAL;


       CNT
----------
  28085760

数字好像太大了一点，不知道有没有错。

〇〇

圆桌是否不考虑开始结束，一个圈上顺序相同就算一种？

newkid

题目改了：
Notes:
1. A person is not required to sit next to her / his spouse.
2. The number of different ways should be calculated given a fixed placement of name cards.
夫妻不需要坐在一起（但是不能坐在自己的名字或配偶的名字的座位）
不同情形的计算是基于给定一种座位牌的排列。
没有说转圈后重合的要算同一种。