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

nlrte13

再论这个结果 = 128 的题

首先手工（或机工）验证 [0, 172] 中，最大的不能表示成若干不同平方数和的值是128，

易知，
N = 12 时，若
[N^2, N^2 + 128] 都能表示成若干不同平方数之和，则
[N^2, N^2 * 2 - 1] 也都能表示成若干不同平方数之和。

且当 N >= 13 时，（N^2 * 2 - 1 > (N+1)^2 ）
[(N+1)^2, (N+1)^2 + 128] 都能表示成若干不同平方数之和。

因此，F(N) = [ N^2, (N+1)^2 ]，对于 N >= 12 的值，都能表示成若干不同平方数之和。

（补充：因当 N >= 13 时，有 N^2 * 2 - 1 > (N+1)^2 + 128 ）

[ 本帖最后由 nlrte13 于 2010-9-25 16:43 编辑 ]

newkid

原帖由 nlrte13 于 2010-9-25 16:40 发表
再论这个结果 = 128 的题

首先手工（或机工）验证 [0, 172] 中，最大的不能表示成若干不同平方数和的值是128，

易知，
N = 12 时，若
[N^2, N^2 + 128] 都能表示成若干不同平方数之和，则
[N^2, N^2 * 2 - 1] 也都能表示成若干不同平方数之和。

且当 N >= 13 时，（N^2 * 2 - 1 > (N+1)^2 ）
[(N+1)^2, (N+1)^2 + 128] 都能表示成若干不同平方数之和。

因此，F(N) = [ N^2, (N+1)^2 ]，对于 N >= 12 的值，都能表示成若干不同平方数之和。

（补充：因当 N >= 13 时，有 N^2 * 2 - 1 > (N+1)^2 + 128 ）

兄弟真是太猛了！以后就叫你奥数哥吧！

newkid

原帖由 nlrte13 于 2010-9-25 16:40 发表
再论这个结果 = 128 的题

首先手工（或机工）验证 [0, 172] 中，最大的不能表示成若干不同平方数和的值是128，

易知，
N = 12 时，若
[N^2, N^2 + 128] 都能表示成若干不同平方数之和，则
[N^2, N^2 * 2 - 1] 也都能表示成若干不同平方数之和。

且当 N >= 13 时，（N^2 * 2 - 1 > (N+1)^2 ）
[(N+1)^2, (N+1)^2 + 128] 都能表示成若干不同平方数之和。

因此，F(N) = [ N^2, (N+1)^2 ]，对于 N >= 12 的值，都能表示成若干不同平方数之和。

（补充：因当 N >= 13 时，有 N^2 * 2 - 1 > (N+1)^2 + 128 ）

[N^2, N^2 * 2 - 1] 也都能表示成若干不同平方数之和。
这个推论适用于所有N是怎么得来的？

当 N >= 13 时，
[(N+1)^2, (N+1)^2 + 128] 都能表示成若干不同平方数之和。
这又是怎么推断出来的？

nlrte13

原帖由 newkid 于 2010-9-26 02:52 发表


[N^2, N^2 * 2 - 1] 也都能表示成若干不同平方数之和。
这个推论适用于所有N是怎么得来的？

当 N >= 13 时，
[(N+1)^2, (N+1)^2 + 128] 都能表示成若干不同平方数之和。
这又是怎么推断出来的？

基本思想是基于数学归纳法
有个小失误，应该首先手工（或机工）验证 到[0, 297] ，不是[0,172] ：P
写下具体验证过程吧，如下：

F(K) = [ K^2, K^2 + 128 ]
M(K) = [ K^2, K^2 * 2 - 1 ]

当 K >= 13时，F(K) = [ 169, 297 ]，由于手工验证过，显然成立。
对于 M(K) = [ 169, 169 + 168 ]，由于 297 > 168 > 128，
则 168 可以表示成若干不同平方数之和，且不包含 13^2，
所以 M(K) 也成立。

且当 K >= 13 时，有 K^2 * 2 - 1 > (K+1)^2 + 128
所以 F(K+1) = [ (K+1)^2, (K+1)^2 + 128 ] 在 M(K) 范围之内，
（ (K+1)^2 > K^2， (K+1)^2 + 128 < K^2 * 2 - 1 ）
所以 F(K+1) 必然也是成立的，

而对于 M(K+1) = [ (K+1)^2, (K+1)^2 + (K+1)^2 - 1 ]，
因为有 K^2 * 2 - 1 > (K+1)^2 - 1 > 128，
所以 M(K+1) 也必然成立。

由此可以搭建出符合数学归纳法的模式，
当 K >= 13，且 F(K) 成立时（此时 M(K)必然成立），
则 F(K+1) 一定成立（此时 M(K+1) 也必然成立，达到所求目的）。

这样一来，就可以说 [ 13^2, 14^2 ] 成立（其实只要 [13^2, 13^2 + 128]，即最初手工验证的 [ 169, 297 ]），
那么[ 14^2, 15^2 ] 就成立，然后 [ 15^2, 16^2 ] 就成立，接着 [ 16^2, 17^2 ] 就成立……
直到 [ N^2, (N+1)^2 ] 也成立。。。

nlrte13

那个“上上上题”题有思路了，从高位到低位尝试着一个个逆推^^

nlrte13

首先要尝试 38x，98x 的情况，这样探索出 387 这个初始值要花的时间还是不算长的。

只是这样做，时间复杂度对“运气”有一定依赖性，
还好 38x 最终把所有数字都用进去了，使我们可以确定最后的结果是正确的，
不然，还要继续用 37x，97x 尝试下去。。。

严谨的话，还应该对照着3位数的“变换表”

[ 本帖最后由 nlrte13 于 2010-9-26 11:19 编辑 ]

newkid

原帖由 nlrte13 于 2010-9-26 08:34 发表



基本思想是基于数学归纳法
有个小失误，应该首先手工（或机工）验证 到[0, 297] ，不是[0,172] ：P
写下具体验证过程吧，如下：

F(K) = [ K^2, K^2 + 128 ]
M(K) = [ K^2, K^2 * 2 - 1 ]

当 K >= 13时，F(K) = [ 169, 297 ]，由于手工验证过，显然成立。
对于 M(K) = [ 169, 169 + 168 ]，由于 297 > 168 > 128，
则 168 可以表示成若干不同平方数之和，且不包含 13^2，
所以 M(K) 也成立。

且当 K >= 13 时，有 K^2 * 2 - 1 > (K+1)^2 + 128
所以 F(K+1) = [ (K+1)^2, (K+1)^2 + 128 ] 在 M(K) 范围之内，
（ (K+1)^2 > K^2， (K+1)^2 + 128 < K^2 * 2 - 1 ）
所以 F(K+1) 必然也是成立的，

而对于 M(K+1) = [ (K+1)^2, (K+1)^2 + (K+1)^2 - 1 ]，
因为有 K^2 * 2 - 1 > (K+1)^2 - 1 > 128，
所以 M(K+1) 也必然成立。

由此可以搭建出符合数学归纳法的模式，
当 K >= 13，且 F(K) 成立时（此时 M(K)必然成立），
则 F(K+1) 一定成立（此时 M(K+1) 也必然成立，达到所求目的）。

这样一来，就可以说 [ 13^2, 14^2 ] 成立（其实只要 [13^2, 13^2 + 128]，即最初手工验证的 [ 169, 297 ]），
那么[ 14^2, 15^2 ] 就成立，然后 [ 15^2, 16^2 ] 就成立，接着 [ 16^2, 17^2 ] 就成立……
直到 [ N^2, (N+1)^2 ] 也成立。。。

终于看懂了，多谢！

〇〇

当 K >= 13 时，有 K^2 * 2 - 1 > (K+1)^2 + 128
k^2-2k-130>0
=>(k-1)^2>131
=>k〉sqrt(131)+1

[ 本帖最后由 〇〇 于 2010-9-27 10:16 编辑 ]

nlrte13

哈哈，不客气，互相交流学习嘛^^

最近逛了逛这个版，发现马利奥阁下可是非常热心的人呐

等那本《破冰》出炉，俺也得请回家拜读下。。。

newkid

这题比较简单：

#12 Binary System

How many digits are needed to write down all the numbers from 0 to 9999 in binary system?

If the same question was asked for numbers from 0 to 5, the answer would be 12 (0, 1, 10, 11, 100, 101 --> a total of 12 digits).

SELECT SUM(TRUNC(ROUND(LOG(2,LEVEL),20))+1)+1
  FROM DUAL
CONNECT BY LEVEL<=9999;


123618