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

newkid

从两个公式来看，要使得S20 - MAX_S15最小，就要在5000公式中尽量把大数往左边凑，因为左边的系数较大：
19*d10 + 17*d9 + 15*d8 + 13*d7 + 11*d6 + 9*d5 + 7*d4 + 5*d3 + 3*d2 + 1*d1 = 5000

算d10的上限：把d1~d9用常数1~17代入：
19*MAX_d10+81=5000
MAX_d10=258

而靠右边的几个数要尽量小。把d1~d7的最小值1～13用常数代入：

SELECT *
FROM (SELECT t.*
             ,5000-(5*(d10+d9+d8+d7+d6+d5+d4+d3)+3*d2+d1) max_s15
             ,RANK() OVER(ORDER BY 5000-(5*(d10+d9+d8+d7+d6+d5+d4+d3)+3*d2+d1) DESC) rnk
         FROM (SELECT *
                FROM (SELECT LEVEL d10 FROM DUAL WHERE LEVEL >= 19 CONNECT BY LEVEL<=258)
                    ,(SELECT LEVEL d9  FROM DUAL WHERE LEVEL >= 17 CONNECT BY LEVEL<=258-2)
                    ,(SELECT LEVEL d8  FROM DUAL WHERE LEVEL >= 15 CONNECT BY LEVEL<=258-4)
                    ,(SELECT 13 d7
                            ,11 d6  
                            ,9  d5  
                            ,7  d4  
                            ,5  d3  
                            ,3  d2  
                            ,1  d1  
                        FROM DUAL
                     )
              WHERE 19*d10 + 17*d9 + 15*d8 + 13*d7 + 11*d6 + 9*d5 + 7*d4 + 5*d3 + 3*d2 + 1*d1 = 5000
                    AND d10>d9+1
                    AND d9 >d8+1
                    AND d8 >d7+1
                    AND d7 >d6+1
                    AND d6 >d5+1
                    AND d5 >d4+1
                    AND d4 >d3+1
                    AND d3 >d2+1
                    AND d2 >d1+1
              ) t
     )
WHERE rnk=1
;

       D10         D9         D8         D7         D6         D5         D4         D3         D2      D1       MAX_S15        RNK
---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
       205         25         15         13         11          9          7          5          3       1          3540          1
       207         21         17         13         11          9          7          5          3       1          3540          1
       206         23         16         13         11          9          7          5          3       1          3540          1

15个数的两两差距之和，最大可能是3540.
这是一种耍赖的办法，也没法保证正确性。

根据上述结论构造一个例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
27
206

验证：
WITH t AS (
    SELECT 1   n FROM DUAL UNION ALL
    SELECT 2   n FROM DUAL UNION ALL
    SELECT 3   n FROM DUAL UNION ALL
    SELECT 4   n FROM DUAL UNION ALL
    SELECT 5   n FROM DUAL UNION ALL
    SELECT 6   n FROM DUAL UNION ALL
    SELECT 7   n FROM DUAL UNION ALL
    SELECT 8   n FROM DUAL UNION ALL
    SELECT 9   n FROM DUAL UNION ALL
    SELECT 10  n FROM DUAL UNION ALL
    SELECT 11  n FROM DUAL UNION ALL
    SELECT 12  n FROM DUAL UNION ALL
    SELECT 13  n FROM DUAL UNION ALL
    SELECT 14  n FROM DUAL UNION ALL
    SELECT 15  n FROM DUAL UNION ALL
    SELECT 16  n FROM DUAL UNION ALL
    SELECT 17  n FROM DUAL UNION ALL
    SELECT 18  n FROM DUAL UNION ALL
    SELECT 27  n FROM DUAL UNION ALL
    SELECT 206 n FROM DUAL
)
SELECT SUM(t2.n-t1.n) sum
  FROM t t1, t t2
WHERE t1.n<t2.n;

       SUM
----------
      5000

去掉8-13中的随便五个：

WITH t AS (
    SELECT 1   n FROM DUAL UNION ALL
    SELECT 2   n FROM DUAL UNION ALL
    SELECT 3   n FROM DUAL UNION ALL
    SELECT 4   n FROM DUAL UNION ALL
    SELECT 5   n FROM DUAL UNION ALL
    SELECT 6   n FROM DUAL UNION ALL
    SELECT 7   n FROM DUAL UNION ALL
    SELECT 13  n FROM DUAL UNION ALL
    SELECT 14  n FROM DUAL UNION ALL
    SELECT 15  n FROM DUAL UNION ALL
    SELECT 16  n FROM DUAL UNION ALL
    SELECT 17  n FROM DUAL UNION ALL
    SELECT 18  n FROM DUAL UNION ALL
    SELECT 27  n FROM DUAL UNION ALL
    SELECT 206 n FROM DUAL
)
SELECT SUM(t2.n-t1.n) sum
  FROM t t1, t t2
WHERE t1.n<t2.n;

       SUM
----------
      3540

[ 本帖最后由 newkid 于 2010-9-24 02:32 编辑 ]

〇〇

终于等到了

newkid

只是猜的谁知道对不对。

lastwinner

158楼说得没错，但针对  
“其中d10>d9>d8>....d1, 均为正整数, 且d10>=19, d9>=17, d8>=15, ... d1>=1。”
可再增加一个限制条件，即 d10>=d9+2, d9>=d9+2...d2>=d1+2


156、159楼提法不准确
156楼应说“因为每个数加同一个数不影响差的总和，因此可以假定a1=1”
159楼应说“d10的值最大可能是trunc((5000-1^2-3^2-5^2 ...17^2)/19)”，不能再加1了，否则一定会超过5000的
用excel算出来，max_d10最多是212。

newkid

原帖由 lastwinner 于 2010-9-24 00:59 发表
158楼说得没错，但针对  
“其中d10>d9>d8>....d1, 均为正整数, 且d10>=19, d9>=17, d8>=15, ... d1>=1。”
可再增加一个限制条件，即 d10>=d9+2, d9>=d9+2...d2>=d1+2


156、159楼提法不准确
156楼应说“因为每个数加同一个数不影响差的总和，因此可以假定a1=1”
159楼应说“d10的值最大可能是trunc((5000-1^2-3^2-5^2 ...17^2)/19)”，不能再加1了，否则一定会超过5000的
用excel算出来，max_d10最多是212。

是啊，你看我后来写的SQL里面有：
AND d10>d9+1
AND d9 >d8+1
............

d10的下限也可以算出来。d9~d1的上限也可以分别求出来。但是其组合数还是巨大，后来只好用填常数的无赖办法。

lastwinner

1~19和212，这20个数组成的集合，两两之差的和为4978
x20=212,x19=19,x18=18...
现在要在这几个数上做合适的变动，使得
d10,d9,d8...发生变化，记变化后的差值为e10,e9,e8...
并设a10=e10-d10, a9=e9-d9...
于是，只要找到一组合适的a10, a9...
使得
19*a10+17*a9+15*d8+...=5000-4978=22
就能使变动后的这20个数，两两之差的和为5000

这里，a10的变化与a9、a8等都无关，是独立的，而且一定是个负数
a9、a8...之间满足a9>=a8...

注意，为了满足剔除中间5个数后剩余15个数两两之差的和达到最大值
因此变动范围最多限于a10、a9、a8、a7、a6、a5和a4之间

到这里，成了类似百金买百鸡的一个问题了，即
19*a10+17*a9+15*a8+13*a7+11*a6+9*a5+7*a4=22
a10<0
a9>=a8>=a7>=a6>=a5>=a4>=0

——————————————————————————————————————————
暂时先想到这里，睡觉了

[ 本帖最后由 lastwinner 于 2010-9-24 13:13 编辑 ]

lastwinner

原帖由 newkid 于 10-9-24 01:15 发表


是啊，你看我后来写的SQL里面有：
AND d10>d9+1
AND d9 >d8+1
............

d10的下限也可以算出来。d9~d1的上限也可以分别求出来。但是其组合数还是巨大，后来只好用填常数的无赖办法。

归结到百鸡问题后，就简单许多了
这是我人脑出来的一个结果

newkid

呵呵,这个"买鸡"问题记得我小时候在很多本趣味数学题都看到过。
3540这个答案可以算是严密推理出来的吗？

lastwinner

原帖由 newkid 于 10-9-24 02:37 发表
呵呵,这个"买鸡"问题记得我小时候在很多本趣味数学题都看到过。
3540这个答案可以算是严密推理出来的吗？

不算的，呵呵
继续
——————————————————————————————————————————————————
因为S20 - MAX_S15 = 5*(d10+d9+d8+d7+d6+d5+d4+d3)+3*d2+d1
所以要使得MAX_S15最大，应保证调整后5*(e10+e9+e8+e7+e6+e5+e4+e3)+3*e2+e1最小
而调整后的e3、e2、e1与调整前的d3、d2、d1是一样的
所以我们只关注e10、e9、e8、e7、e6、e5和e4
这与166楼的关注点就接近了，借助该楼的设定a10=e10-d10...
于是，现在我们关注如何使得
Q=a10+a9+a8+a7+a6+a5+a4取得最小值

由
19*a10+17*a9+15*a8+13*a7+11*a6+9*a5+7*a4=22....................(1)
a10<0                                                                             .....................(2)
a9>=a8>=a7>=a6>=a5>=a4>=0                                  .....................(3)

由(1)可得
17*a9+17*a8+17*a7+17*a6+17*a5+17*a4>=17*a9+15*a8+13*a7+11*a6+9*a5+7*a4=22-19*a10
=>a9＋a8＋a7＋a6＋a5＋a4>=(22-19*a10)/17        ..................................(4)
不等式取极小值，记p=min(a9＋a8＋a7＋a6＋a5＋a4) ，于是(4)式变为
19*a10+17*p=22   => p=(22-19*a10)/17，此时p为关于a10的一次单调递减函数，随着a10的减小，p在增大
任取一数a10'，使其满足 a10>a10'
代入上式，可得相应的p'
则有
min(Q)=p+a10=(22-19*a10)/17+a10=(22-2*a10)/17
同样可推得  min(Q)'=p'+a10'=(22-2*a10')/17

于是有：min(Q)'-min(Q)=(p'+a10')-(p+a10)=2*(a10-a10')/17>0

可见随着a10的减小，min(Q)在单调递增，而Q>=min(Q)，从而随着a10的减小，Q也在单调递增
所以a10要尽可能的大，这样才能保证Q取到最小值
于是只要根据(1)、(2)、(3)，找出最大的a10，就能使Q最小，从而保证MAX_S15最大。


令a8=a7=a6=a5=a4=0，于是有
a10=-6时，a9=8， a10=-23时，a9=27
显然a10=-23时，MAX_S15比a10=-6时要小，故而a10的变化范围可限制在[-23,-1]
a9的变化范围在[0,27], a8的变化范围在[0,floor(22-19*(-23))/(15+17)]=>[0,14]
同理得a7的变化范围在[0,10]，a6的变化范围在[0,8]，a5的变化范围在[0,7]，a4的变化范围则在[0,6]


然后现在要做的就是开动sql去跑出min(Q)了
基本上可以推定，3540这个结果是没问题的了

lastwinner

顺带传下草稿纸，以防以后需要的时候自己找不到