puzzleup 2020 11月开始

newkid

#3 POOL OF PROBLEMS

Using a pool of problems, 16 tests will be formed.

-Every test should have the same number of problems.
-Any problem should be included in at most 8 tests.
-For every 4 tests, there should be at least 1 problem common to all of them.
-Within a test a single problem cannot be used more than once.
-Some tests may be formed of exactly the same problems.

What can be the minimum number of problems in this pool?

If the problem was asked for 8 tests, any problem to be included in at most 4 tests and at least 1 problem common to every 2 tests then the answer would be 6:

(1-2-6), (1-3-5), (1-3-5), (1-4-6), (2-3-6), (2-4-5), (2-4-5), (3-4-6)



利用一个题库，将形成16份考题。

-每份考题 都应该有相同数量的问题。
-任何一个问题最多出现在8份考题中。
-每4份考题中，至少有一个问题是在所有这些考题中都共同出现的。
-在一份考题中，一个问题不能被使用超过一次。
-有些考题可能由完全相同的问题组成。

在这个题库中，问题的最少数量是多少？

如果问的是8份考题，任何问题最多包含在4份考题中，并且每2份考题中至少有1个共同的问题，那么答案是6：
(1-2-6), (1-3-5), (1-3-5), (1-4-6), (2-3-6), (2-4-5), (2-4-5), (3-4-6)

--------
这个题目2013年出过了，没有人解出来：
http://www.itpub.net/thread-1804282-3-1.html
第五题，89楼

〇〇

这都记得，什么记性

solomon_007

我瞎猜的，是不是需要 18 道题啊，16份考题，每份 9 道题，下面是我的推理数字：
1 : (1,4,6,8,10,12,14,16,  18)
2 : (1,3,6,8,10,12,14,16,  17)
3 : (1,3,5,8,10,12,14,16,  17)
4 : (1,3,5,7,10,12,14,16,  17)
5 : (1,3,5,7,9 ,12,14,16,  17)
6 : (1,3,5,7,9 ,11,14,16,  17)
7 : (1,3,5,7,9 ,11,13,16,  17)
8 : (1,3,5,7,9 ,11,13,15,17  )
9 : (2,3,5,7,9 ,11,13,15,  18)
10: (2,4,5,7,9 ,11,13,15,  18)
11: (2,4,6,7,9 ,11,13,15,  18)
12: (2,4,6,8,9 ,11,13,15,  18)
13: (2,4,6,8,10,11,13,15,  18)
14: (2,4,6,8,10,12,13,15,  18)
15: (2,4,6,8,10,12,14,15,  18)
16: (2,4,6,8,10,12,14,16,17  )

由上到下是16套考题，由括号组成，1-8套，先放第1题，9-16套放第2题；第3题由第二套题开始放，放完8次，再放第4题，最后一个第3题就循环，放到第一套，
后面都这样左一个数字，依次循环，(1,3,5,7,9 ,11,13,15) 和  (2,4,6,8,10,12,14,16） 没有任何一题相同，只要再放入17，使得这两组有这个题相同，
其他任意组合或相邻的4组都至少有一题相同。  所以结果就是要至少 18 道题！

newkid

我写了个SQL来验证你的答案，随便就找出很多不满足的四个组合：


WITH t AS (
SELECT 1  id, POWER(2,1)+POWER(2,4)+POWER(2,6)+POWER(2,8)+POWER(2,10)+POWER(2,12)+POWER(2,14)+POWER(2,16)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 2  id, POWER(2,1)+POWER(2,3)+POWER(2,6)+POWER(2,8)+POWER(2,10)+POWER(2,12)+POWER(2,14)+POWER(2,16)+POWER(2,17) q FROM DUAL
UNION ALL SELECT 3  id, POWER(2,1)+POWER(2,3)+POWER(2,5)+POWER(2,8)+POWER(2,10)+POWER(2,12)+POWER(2,14)+POWER(2,16)+POWER(2,17) q FROM DUAL
UNION ALL SELECT 4  id, POWER(2,1)+POWER(2,3)+POWER(2,5)+POWER(2,7)+POWER(2,10)+POWER(2,12)+POWER(2,14)+POWER(2,16)+POWER(2,17) q FROM DUAL
UNION ALL SELECT 5  id, POWER(2,1)+POWER(2,3)+POWER(2,5)+POWER(2,7)+POWER(2,9 )+POWER(2,12)+POWER(2,14)+POWER(2,16)+POWER(2,17) q FROM DUAL
UNION ALL SELECT 6  id, POWER(2,1)+POWER(2,3)+POWER(2,5)+POWER(2,7)+POWER(2,9 )+POWER(2,11)+POWER(2,14)+POWER(2,16)+POWER(2,17) q FROM DUAL
UNION ALL SELECT 7  id, POWER(2,1)+POWER(2,3)+POWER(2,5)+POWER(2,7)+POWER(2,9 )+POWER(2,11)+POWER(2,13)+POWER(2,16)+POWER(2,17) q FROM DUAL
UNION ALL SELECT 8  id, POWER(2,1)+POWER(2,3)+POWER(2,5)+POWER(2,7)+POWER(2,9 )+POWER(2,11)+POWER(2,13)+POWER(2,15)+POWER(2,17) q FROM DUAL
UNION ALL SELECT 9  id, POWER(2,2)+POWER(2,3)+POWER(2,5)+POWER(2,7)+POWER(2,9 )+POWER(2,11)+POWER(2,13)+POWER(2,15)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 10 id, POWER(2,2)+POWER(2,4)+POWER(2,5)+POWER(2,7)+POWER(2,9 )+POWER(2,11)+POWER(2,13)+POWER(2,15)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 11 id, POWER(2,2)+POWER(2,4)+POWER(2,6)+POWER(2,7)+POWER(2,9 )+POWER(2,11)+POWER(2,13)+POWER(2,15)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 12 id, POWER(2,2)+POWER(2,4)+POWER(2,6)+POWER(2,8)+POWER(2,9 )+POWER(2,11)+POWER(2,13)+POWER(2,15)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 13 id, POWER(2,2)+POWER(2,4)+POWER(2,6)+POWER(2,8)+POWER(2,10)+POWER(2,11)+POWER(2,13)+POWER(2,15)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 14 id, POWER(2,2)+POWER(2,4)+POWER(2,6)+POWER(2,8)+POWER(2,10)+POWER(2,12)+POWER(2,13)+POWER(2,15)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 15 id, POWER(2,2)+POWER(2,4)+POWER(2,6)+POWER(2,8)+POWER(2,10)+POWER(2,12)+POWER(2,14)+POWER(2,15)+POWER(2,18) q FROM DUAL
UNION ALL SELECT 16 id, POWER(2,2)+POWER(2,4)+POWER(2,6)+POWER(2,8)+POWER(2,10)+POWER(2,12)+POWER(2,14)+POWER(2,16)+POWER(2,17) q FROM DUAL
)
,r(id,cnt,q,path) AS (
select id,1,q,TO_CHAR(id) from t
union all
select t.id,r.cnt+1,BITAND(r.q,t.q),r.path||','||t.id
  from r,t
where r.id<t.id and r.cnt<4
)
select path from r where cnt=4 and q=0 and rownum<10;

PATH
-------------
1,2,3,9
1,2,3,10
1,2,3,11
1,2,4,9
1,2,4,10
1,2,4,11
1,2,4,12
2,3,4,10
2,3,4,11

newkid

我猜题库至少70题，每份试卷35题。

验证：
WITH U as (
SELECT SYS_CONNECT_BY_PATH(gid,',') path,POWER(2,ROWNUM-1) b,ROWNUM qid
  FROM (SELECT LEVEL gid FROM DUAL CONNECT BY LEVEL<=8)
WHERE LEVEL=4
CONNECT BY LEVEL<=4 AND gid>PRIOR gid
)
,u2 AS (
SELECT REGEXP_SUBSTR(path,'[^,]+',1,LEVEL) gid,b,qid
  FROM u
CONNECT BY path=PRIOR path AND LEVEL<=4 AND PRIOR SYS_GUID() IS NOT NULL
)
,t AS (
SELECT id,SUM(b) q,LISTAGG(qid,',') WITHIN GROUP(ORDER BY qid) qid
FROM (
       SELECT 2*gid-1 id,b,qid FROM u2
       UNION ALL
       SELECT 2*gid id,b,qid FROM u2
      )
GROUP BY id
)
---- SELECT id,qid FROM t ORDER BY id ------ 查看每份试卷的题目分布
,r(id,cnt,q,path) AS (
select id,1,q,TO_CHAR(id) from t
union all
select t.id,r.cnt+1,BITAND(r.q,t.q),r.path||','||t.id
  from r,t
where r.id<t.id and r.cnt<4
)
select path from r where cnt=4 and q=0;

no rows selected ----- 表示所有都满足条件q>0

solomon_007

newkid 发表于 2020-11-19 22:54
我写了个SQL来验证你的答案，随便就找出很多不满足的四个组合：WITH t AS (SELECT 1  id, POWER(2,1)+POWER ...

是啊，这些4套的组合都没有共同的题。。。

solomon_007

newkid 发表于 2020-11-20 04:23
我猜题库至少70题，每份试卷35题。验证：WITH U as (SELECT SYS_CONNECT_BY_PATH(gid,',') path,POWER(2,RO ...

要 70 题啊，需要这么多吗？   如果这题每个要求设成变量，那是不是应该有个公式?

newkid

我总结的公式：
所有试卷数量T=16
每题可共享次数S=8
要求出现同题的群组大小G=4 (每4份必须出现一道共同题目)

则题库大小=C(T/(S/G),G)=C(16/(8/4),4)=C(8,4)=70

这个公式对作者所举的简化例子也成立。

这里面的S/G, 意思是一道题出现在S份试卷中，把这些试卷分成G组，得到的一个单位（本题中S/G=2即每两份试卷一个单位）。所有16份试卷分成8个这种单位。然后在这这些单位中取组合（4个一组），总共是C(8,4), 每个这样的组合要用掉一道题。我那个验证SQL就是基于这种思路来分配题目的。理论上很容易证明这种分配方法能够满足每G份题都会有一道共同的题目。但是要反证这种分配法得到的是最小答案，难度比较大。

solomon_007

newkid 发表于 2020-11-20 22:29
我总结的公式：所有试卷数量T=16每题可共享次数S=8要求出现同题的群组大小G=4 (每4份必须出现一道共同题目) ...

NIUBILITY!

newkid

#4 CANDIES

There are two boxes each having 10 candies. You will randomly (with equal probability) select a box and eat one candy from that box. Then the places of the boxes will be changed randomly. You will continue this process until you eat the last candy in a box. When you stop what is the probability that the other box has exactly 5 candies?

Enter your answer as a simplified fraction. Example:12/23


有两个盒子，每个盒子里有10颗糖果，你将随机（以相同的概率）选择一个盒子，然后从那个盒子里吃一颗糖果。然后盒子的位置会随机改变。你将继续这个过程，直到你吃完一个盒子里的最后一颗糖。当你停下来的时候，另一个盒子里正好有5颗糖果的概率是多少？

将你的答案以简化分数输入。例：12/23