Puzzleup 2010 比赛快开始了，大家用SQL解答啊

newkid

原帖由 〇〇 于 2010-8-16 06:19 发表
pdf

先下载，希望能看懂。

newkid

都是只有结论，看不到论文内容。

lastwinner

原帖由 〇〇 于 10-8-16 06:19 发表
pdf

别光写个pdf啊
要说明是干嘛用的，有没有跟哪个题目相关的

newkid

它只是提到：
There are only 31 numbers that cannot be expressed as the sum of distinct squares: 2, 3, 6, 7, 8, 11, 12, 15,
18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128 (Sloane's
A001422; Guy 1994; Savin 2000).

似乎有三篇论文：
http://www.research.att.com/~njas/sequences/A001422

Guy, R. K. "Sums of Squares" and "Squares with Just Two Different Decimal Digits." §C20 and F24 in Unsolved Problems in
Number Theory, 2nd ed. New York: Springer-Verlag, pp. 136-138, 147, and 262, 1994.

Savin, A. "Shape Numbers." Quantum 11, 14-18, 2000.

找不到内容，最多只有摘要。

lastwinner

估计要看得花钱

这个题我的思路是用数学归纳法去证明
但怎么证我就不知道了

newkid

如果你认识哪个留学生，可以让他替你查，大学查论文是免费的。

newkid

Sixteen Numbers
You are going to place all numbers from 1 to 16 on a 4x4 chessboard such that all consecutive number pairs (1-2, 2-3, ..., 15-16) will be on the neighboring cells (left-right-top-down).

In how many different ways can this be done?

If the question was asked for a 2x2 chessboard, the answer would be 8.

把1-6放在8X8的棋盘上，使得所有相邻的数对(1-2,2-3,..., 15-16)在位置上也相邻(上下左右)。有多少种摆法？
以2X2为例，答案是8:
12
43

41
32

34
21

23
14

14
23

21
34

32
41

23
14

newkid

WITH t (pos,n,res) AS (
  SELECT ROWNUM,1,SUBSTR('                ',1,ROWNUM-1)||'A'||SUBSTR('                ',ROWNUM+1) FROM DUAL CONNECT BY ROWNUM<=16
  UNION ALL
  SELECT rn,n+1,SUBSTR(t.res,1,rn-1)||CHR(ASCII('A')+n)||SUBSTR(t.res,rn+1)
    FROM t,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=16)
   WHERE SUBSTR(t.res,rn,1) = ' '
         AND (t.pos NOT IN (4,8,12,16) AND rn=t.pos+1
              OR t.pos NOT IN (1,5,9,13) AND rn=t.pos-1
              OR t.pos NOT BETWEEN 13 AND 16 AND rn=t.pos+4
              OR t.pos NOT BETWEEN 1 AND 4 AND rn=t.pos-4
              )
         AND n<16
   )
SELECT COUNT(*) FROM t WHERE n=16;         

  COUNT(*)
----------
       552

lastwinner

Sixteen Numbers的意思其实就是将数字顺时针或者逆时针摆放？

newkid

原帖由 lastwinner 于 2010-8-19 09:58 发表
Sixteen Numbers的意思其实就是将数字顺时针或者逆时针摆放？

那是仅仅2X2的情况，4X4复杂些，任何位置都可以是起点，四个方向都可以拐弯。


我随便拿了一个答案：
KLOP
JMNA
IFEB
HGDC

因为超过两位，我用字母A-P来表示。你可以想像为一条蛇把身体盘成奇怪的形状占领整个棋盘。