Puzzleup 2013挑战赛即将开始

piliskys

HelloWorld_001 发表于 2013-8-22 20:56
因为至少12题，而每份6题，那肯定有二份它们可能是不包含一个相同的  --这句话我同意，但如何分是我们确定 ...

嗯，是我理解有问题，

〇〇

newkid 发表于 2013-8-22 22:11
你再证明一下，图书章就归你了。

你怎么那么多章

HelloWorld_001

我睡下又爬起来证明，就为了newkid说的图书章
首先我已找到题库12道可以满足，现在只需要证明题库11道的时候不行，那么12就是最小了。
采取反证法，假设题库11道，且一道题最多10份试卷，那么 11*10/20=5 有余数。那么必然存在某张试卷只有5道题。
--接着证明只有5道题是不行的
假设有5道题的试卷叫a1,剩下的分别是a2,...a20.
a1的试题分别是b1,b2,,,b5
a1需要和任意的4张试卷有2题重复。我简化为a1和任意的4张有1题重复（再次重复这个过程就变成2题重复了）
最多有a2,a3...a10 一共9张试卷有b1这题（每题最多出现10次）
最多有a11,a12...a19 一共9张试卷有b2这题（每题最多出现10次）
由于一共20张试卷，至少存在a20这个试卷和a1重复的为b3这题。
--再来重复第二题
假设a1和a2,a3,a4,a5 重复的第二题为b4(此种情况必然存在。如果b4=b3,那么b3只能再出现8次，比如是a2-a9，那么a1和a10必然存在相同的b5.)
--所以我必然能从a2-a10中找到4个和a1重复的第二题不是b3的情况。
同理我也能在a11-a19中找出4个和a1重复的第二题不是b3的情况。记为b5
由于a1只有5题已经全部用完。那么a1,a20这样的配对只会有相同的b3.

普遍情况不会分析
我再分析下如果a2,.. 这不是到a10，而是到a9，只有8份试卷。会怎么样。
那么b3这个地方至少是2份试卷a19和a20。加上a1占了b3,最多再出现7次。符合条件的b2.../b1x ... 和之前分析一样，必然存在占b4,b5的情况。
依然推出矛盾

〇〇

HelloWorld_001 发表于 2013-8-23 00:31
我睡下又爬起来证明，就为了newkid说的图书章
首先我已找到题库12道可以满足，现在只需要证明题库11道的时 ...

能否用计算机穷举证明

HelloWorld_001

穷举证明得newkid出手了。
我睡觉了，今晚不爬起来了。
而且我明天估计下午才会去上班，不知道有没有时间写穷举

newkid

103楼的证明看不懂。首先每份卷子都必须有相同的题目数，这样当X=11时最多每份5题，而不是仅有一份5题；
接下来把b1和b2分摊在互不交叉的试卷组，这也只是特例，你得证明其他的情况。
“如果b4=b3,那么b3只能再出现8次”这个也看不懂什么意思。
另外题目说了每五份试卷“至少”有两题是公共的，不排除多于两题的情况，这个你应该没理解错吧。

newkid

验证你的12题答案：

验证所有题目出现不超过十次：
用16进制的12位表示：

WITH t AS (
          SELECT  'b1' AS test_id, '000111000111' AS problems FROM DUAL
UNION ALL SELECT  'b2' AS test_id, '000111000111' AS problems FROM DUAL
UNION ALL SELECT  'b3' AS test_id, '000111000111' AS problems FROM DUAL
UNION ALL SELECT  'b4' AS test_id, '000111000111' AS problems FROM DUAL
UNION ALL SELECT  'b5' AS test_id, '000111000111' AS problems FROM DUAL
UNION ALL SELECT  'b6' AS test_id, '011001011001' AS problems FROM DUAL
UNION ALL SELECT  'b7' AS test_id, '011001011001' AS problems FROM DUAL
UNION ALL SELECT  'b8' AS test_id, '011001011001' AS problems FROM DUAL
UNION ALL SELECT  'b9' AS test_id, '011001011001' AS problems FROM DUAL
UNION ALL SELECT 'b10' AS test_id, '011001011001' AS problems FROM DUAL
UNION ALL SELECT 'b11' AS test_id, '101010101010' AS problems FROM DUAL
UNION ALL SELECT 'b12' AS test_id, '101010101010' AS problems FROM DUAL
UNION ALL SELECT 'b13' AS test_id, '101010101010' AS problems FROM DUAL
UNION ALL SELECT 'b14' AS test_id, '101010101010' AS problems FROM DUAL
UNION ALL SELECT 'b15' AS test_id, '101010101010' AS problems FROM DUAL
UNION ALL SELECT 'b16' AS test_id, '110100110100' AS problems FROM DUAL
UNION ALL SELECT 'b17' AS test_id, '110100110100' AS problems FROM DUAL
UNION ALL SELECT 'b18' AS test_id, '110100110100' AS problems FROM DUAL
UNION ALL SELECT 'b19' AS test_id, '110100110100' AS problems FROM DUAL
UNION ALL SELECT 'b20' AS test_id, '110100110100' AS problems FROM DUAL
)
SELECT TO_CHAR(SUM(TO_NUMBER(problems,'XXXXXXXXXXXX')),'XXXXXXXXXXXX') FROM t;

AAAAAAAAAAAA

这个过关，刚好全部十次

验证所有组合都有至少两题公共的：
WITH t AS (
          SELECT  'b1' AS test_id, 000111000111 AS problems FROM DUAL
UNION ALL SELECT  'b2' AS test_id, 000111000111 AS problems FROM DUAL
UNION ALL SELECT  'b3' AS test_id, 000111000111 AS problems FROM DUAL
UNION ALL SELECT  'b4' AS test_id, 000111000111 AS problems FROM DUAL
UNION ALL SELECT  'b5' AS test_id, 000111000111 AS problems FROM DUAL
UNION ALL SELECT  'b6' AS test_id, 011001011001 AS problems FROM DUAL
UNION ALL SELECT  'b7' AS test_id, 011001011001 AS problems FROM DUAL
UNION ALL SELECT  'b8' AS test_id, 011001011001 AS problems FROM DUAL
UNION ALL SELECT  'b9' AS test_id, 011001011001 AS problems FROM DUAL
UNION ALL SELECT 'b10' AS test_id, 011001011001 AS problems FROM DUAL
UNION ALL SELECT 'b11' AS test_id, 101010101010 AS problems FROM DUAL
UNION ALL SELECT 'b12' AS test_id, 101010101010 AS problems FROM DUAL
UNION ALL SELECT 'b13' AS test_id, 101010101010 AS problems FROM DUAL
UNION ALL SELECT 'b14' AS test_id, 101010101010 AS problems FROM DUAL
UNION ALL SELECT 'b15' AS test_id, 101010101010 AS problems FROM DUAL
UNION ALL SELECT 'b16' AS test_id, 110100110100 AS problems FROM DUAL
UNION ALL SELECT 'b17' AS test_id, 110100110100 AS problems FROM DUAL
UNION ALL SELECT 'b18' AS test_id, 110100110100 AS problems FROM DUAL
UNION ALL SELECT 'b19' AS test_id, 110100110100 AS problems FROM DUAL
UNION ALL SELECT 'b20' AS test_id, 110100110100 AS problems FROM DUAL
)
,t2 (cnt,test_id,problems,all_id) AS (
SELECT 1 cnt
      ,test_id
      ,problems
      ,CAST(test_id AS VARCHAR2(20))
  FROM t
UNION ALL
SELECT t2.cnt+1
      ,t.test_id
      ,t2.problems + t.problems
      ,t2.all_id||','||t.test_id
  FROM t,t2
WHERE t2.cnt<5
       AND t2.test_id<t.test_id
)
SELECT TO_CHAR(problems),all_id FROM t2
WHERE cnt=5 AND REGEXP_COUNT(problems,'5')<2 AND ROWNUM=1;

TO_CHAR(PROBLEMS)                        ALL_ID
---------------------------------------- ------------------------
143214143214                             b20,b5,b7,b8,b9

没过关，随便找个下列组合就不行：

(a1,a2,a3, a7,a8,a9)  

(a1,a4,a5, a7,a10,a11)
(a1,a4,a5, a7,a10,a11)
(a1,a4,a5, a7,a10,a11)

(a3,a5,a6, a9,a11,a12)

HelloWorld_001

newkid找的反例我明白了
只要试卷从3组或以上抽出来，我手算的就不行了

newkid

Regions

What is the maximum number of regions into which four circles and four straight lines can divide a plane?

If the problem was asked for two circles and two straight lines, then the answer would be 14.

四个圆和四条直线，最多能把一个平面分割成几个区域？如果问的是两个圆和两条直线则答案为14。

newkid

#7 Ten Numbers

_
|_|_ _
|_|_|_|
|_|_|_|
|_|_|_|

Place each of the ten numbers between 1 and 10 in the squares so that no two adjacent squares (horizontally or vertically) should contain;

consecutive numbers,
numbers with the same parity (odd or even).

In how many different ways can this task be accomplished?

把1-10这十个数字放入图中的方格，使得不存在相邻（垂直或水平）的两个数字为连续或者具有相同的奇偶性。

这个用SQL应该很容易了吧。