趣题, 第8道来了。

tree_new_bee

atgc 发表于 2012-5-8 09:47
我傻做做
完全平方数的末尾只能是 0,1,4,5,6,9
由于15+16=31，且是相邻两个数相加

傻就是聪明。。。

〇〇

tree_new_bee 发表于 2012-5-8 08:35
哈。 我家学奥数的是女儿，不是儿子。 不过奥数爹， 这个称号不错。   

既然说奥数，就在这个帖子里 ...

最大和是31，所以完全平方数最大25 ，最小4,只可能有4个，哪来15个？

〇〇

随便乱凑了一下，
8? 10 15 1 3 13 12 4 5 11 14 2 7 9 16

〇〇

凑出1个，
8必须放边上，因为 8+1=9 8+8=16 8+17=25
8 1 15 10 6 3  13 12 4 5 11 14 2 7 9 16

newkid

我人肉早不中用了，只好用SQL:
SELECT SYS_CONNECT_BY_PATH(n,'\')
  FROM (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=16)
WHERE LEVEL=16
CONNECT BY NOCYCLE n+PRIOR n IN (4,9,16,25);

tree_new_bee

前一步容易， 我教孩子的手工做法是：
先列出每个数可能相邻的数：
1  3,8,15
2  7,14
3  1,6,13
4  5,12
5  4, 11
6  3, 10
7  2, 9
8  1
9  7, 16
10 6, 15
11 5, 14
12 4, 13
13 3, 12
14 2, 11
15 1, 10
16 9

可以看到，8和16都只有一个可能邻居，所以必须在最两端。
如果从8开始的话，一开始就会碰到1和3这样有多个分支的选择， 所以最好选择从16开始。
这样，可以不必选择一直连到16 9 7 2 14 11 5 4 12 13 3
后面3面临1和6的选择，如果选择1，那么1后面只能选15（8必须在两端，所以放弃），就到16 9 7 2 14 11 5 4 12 13 3 1 15 10 6，然后就停止了。
如果选择6，就是16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8。



后一步呢？怎么没人试试。
如果是1-n, n>16, 还有没有可能得到这样的排列？
(我已经知道有，并且不少， 但对于有没有上限我不知道。)

newkid

下一个N是23, 人肉来做做看？
能否转换为图的遍历问题？有没有可能在不需要真正遍历的情况下就知道存在一条遍历所有顶点的路径？反正我是想不出来。

tree_new_bee

newkid 发表于 2012-5-8 23:07
下一个N是23, 人肉来做做看？
能否转换为图的遍历问题？有没有可能在不需要真正遍历的情况下就知道存在一条 ...

对于23， 可以先跟我上面一样找出所有的可能邻点， 这次改用SQL来找：
with t as (SELECT LEVEL n FROM DUAL CONNECT BY LEVEL<=23)
select t1.n, wm_concat(t2.n) from t t1, t t2
where t1.n<>t2.n and t1.n+t2.n in (4,9,16,25,36) group by t1.n
1    3,15,8
2    7,23,14
3    1,22,13,6
4    5,21,12
5    4,20,11
6    3,19,10
7    2,18,9
8    1,17
9    7,16
10    6,15
11    5,14
12    4,13
13    3,23,12
14    2,22,11
15    1,21,10
16    9,20
17    8,19
18    7
19    6,17
20    5,16
21    4,15
22    3,14
23    2,13


可以看出18只有唯一的邻点。
根据相邻关系可以画出一张图来。 然后其实是一个一笔画的问题， 对于23来说，这个图还不算特别复杂， 找出一条路径不是太难。 如下图，可以找到：
18，7，9，16，20，5，11，14，22，3，1，8，17，19，6，10，15，21，4，12，13，23，2



其实，稍仔细点，其它几条路径也不是太难找到。(可以从7往2走， 也可以从14那个地方往左走2的方向)

tree_new_bee

不过，再往后，手工就基本不现实了。
25的时候有20条路径(头尾颠倒算两条，以下同)
26，24条
27, 70条
28, 104条
29,  38条
30， 40条

newkid

tree_new_bee 发表于 2012-5-8 23:56
对于23， 可以先跟我上面一样找出所有的可能邻点， 这次改用SQL来找：
with t as (SELECT LEVEL n FROM  ...

如果真是一笔画问题，不是已经被欧拉解决了？这里没有要求要走遍所有的边，而是走遍所有顶点而且只能走一遍。