puzzleup 2021

newkid

----------基础推论：(可以从其他组拿真币做参照)
(5.1.1) 5个找1个且轻重已知：2次
(5.2.1) 5个找2个且轻重已知：3次, 假设编号12345
        第一次：12和34比较，如果平衡则两边各有一个，第二次1和2，第三次3和4
                如果不平衡，则已知一边有一个或两个为假，假设是12。第二次1和2比较，如果平衡两个都为假，如果不平衡则5为假。

(5.1.0) 5个找1个且轻重未知：3次，第一次从5取2和2个真币比较
(5.2.0) 5个找2个且轻重未知：3次，假设编号12345
        第一次：12和两个真币比较
                如果平衡：则345有两个。
                          第二次：34和两个真币比较，34中至少一个为假，此时得知轻重。
                                  第三次：3和4比较，如果平衡则34为假且轻重已知，如果不平衡则根据第二次轻重结果得知哪边为假，且5也为假
                如果不平衡：12至少一个为假，此时假B轻重已知。
                          第二次：3和4比较，
                                  如果平衡则34为真，
                                          第三次：1和2比较，如果平衡则12为假且轻重已知，如果不平衡则根据第一次轻重结果得知哪边为假，且5也为假
                                  如果不平衡, 则根据第一次得知34哪边为假，5为真。
                                          第三次：1和2比较, 肯定不平衡，根据第一次得知哪边为假                     

(10.1.1) 10个找1个且轻重已知：3次
(10.2.1) 10个找2个且轻重已知：5次, 第一次拆成5+5比较, 相等则变成两个(5.1.1)，不等则变成(5.2.1)

(10.1.0) 10个找1个且轻重未知：4次，第一次取5个和5个真币比较
(10.2.0) 10个找2个且轻重未知：6次, 前两次分别和5个真币比较

(20.1.1) 20个找1个且轻重已知：4次
(20.2.1) 20个找2个且轻重已知：7次, 第一次拆成10+10比较, 相等则变成两个(10.1.1)，不等则变成(10.2.1)

(20.1.0) 20个找1个且轻重未知：5次, 第一次取10个和10个真币比较
(20.2.0) 20个找2个且轻重未知：8次, 前两次分别和10个真币比较

-------------60找两个个的方法：分成ABC三组，每组20

第一次：比较A,B
A=B:
   则可能两枚在C, 也可能AB各一枚, 此时把A分成AA+AB(10+10)比较，
       第二次：比较AA,AB
       如果AA=AB则两枚全在C: 2+(20.2.0)=2+8=10
       如果AA<>AB则A,B各一枚。
           此时从C取10枚真币和AA比较(第三次)
           得知AA或AB有一假且轻重已知，(10.1.1) 剩余B组是：(20.1.1) 总共3+3+4=10次


A<>B
   第二次：比较A,C
   假设 A=C, 则可能A,C各一枚，或者A,C全为真两枚都在B
        此时把A分成AA+AB(10+10)互相比较，
        第三次：比较AA,AB
        如果AA=AB则两枚全在B, 根据第一次，轻重已知。(20.2.1)=7次, 总共 3+7=10次
        如果AA<>AB则A,C各一枚，根据第一次，轻重已知。AA或AB有一假且轻重已知：(10.1.1)=3次，剩余C组是：(20.1.1) =4次, 总共3+3+4=10次

   假设 A<>C, 则可能B,C各一枚，或者B,C全为真两枚都在A, 和上面路径相同

newkid

第八题：
答案等同于三种颜色，即X=16

先证明：总颜色数不限，每个点不超过两种颜色，则6个点必定出现单色三角形
假设6点为ABCDEF, 从A出发有5条线，A只能用两种颜色，则其中必定有三条线为同色。假设为AB,AC,AD，红颜色。则点B,C,D不能再用红色，一旦这几个点之间有红色，则和A构成红色三角形。这样B,C,D分别只能用一种颜色，三角形BCD必定为同色。

第二步：总颜色数不限，每个点不超过三种颜色，则17个点必定出现单色三角形
从A出发有16条线，A只能用三种颜色，则其中必定有六条线为同色。假设为AB,AC,AD,AE,AF,AG, 红颜色。则点B,C,D,E,F,G 不能再用红色，一旦这几个点之间有红色，则和A构成红色三角形。这样B,C,D,E,F,G 分别只能用两种颜色，根据第一步推论必定出现单色三角形。

〇〇

newkid 发表于 2021-10-29 21:41
----------基础推论：(可以从其他组拿真币做参照)(5.1.1) 5个找1个且轻重已知：2次(5.2.1) 5个找2个且轻重 ...

10次还是不够， 20个找2个且轻重未知要8次，然而确定一个真的就要3次

newkid

〇〇 发表于 2021-11-1 09:01
10次还是不够， 20个找2个且轻重未知要8次，然而确定一个真的就要3次

完全看不懂要表达什么。上面的(20,2,0)=8次不够？“然而确定一个真的就要3次”是什么意思？从几个里面确定一个真的？真币可不是一个一个找的，一旦到了(20,2,0)这条路径，剩下的40个全是真币。

〇〇

从3～5个确定真币要3次，见我285楼第一段

solomon_007

288 楼，

--第八题：
--先证明：总颜色数不限，每个点不超过两种颜色，则6个点必定出现单色三角形
--假设6点为ABCDEF, 从A出发有5条线，A只能用两种颜色，则其中必定有三条线为同色。
--假设为AB,AC,AD，红颜色。则点B,C,D不能再用红色，因为和A的连线已经用掉了。这样B,C,D分别只能用一种颜色，三角形BCD必定为同色。

--世界上任意6个人当中，至少有3个人相互认识，或者相互不认识
--SQL 暴力证明
with t as (select level n from dual connect by level <= 6 ),
     triangle as (
                  select t1.n A,t2.n B,t3.n C
                    from t t1,t t2,t t3
                   where t1.n < t2.n
                     and t2.n < t3.n ),
     triangle_3e as ( select x.A,x.B,x.C,y.A S,y.B E
                        from triangle x,triangle y
                       where x.A = y.A and x.B = y.B and x.C = y.C
                      union all
                      select x.A,x.B,x.C,y.B S,y.C E
                        from triangle x,triangle y
                       where x.A = y.A and x.B = y.B and x.C = y.C
                      union all
                      select x.A,x.B,x.C,y.A S,y.C E
                        from triangle x,triangle y
                       where x.A = y.A and x.B = y.B and x.C = y.C
                      ),                                                     
     edge as (
               select s,e,row_number() over(order by s,e) rno
                from (
                     select distinct A S,B E
                       from (
                             select A,B from triangle
                             union all
                             select B,C from triangle
                             union all
                             select A,C from triangle
                            )
                     )
              ),
    color as (select '0' c from dual
                union all
              select '1' from dual),
    solution (lvl,clist) as (select 1,c from color
                               union all
                              select lvl+1,
                                     s.clist||color.c
                                from solution s,color
                               where lvl < (select count(*) from edge)
                             ),
      r as (
           select clist
             from solution
            where lvl = (select count(*) from edge)
           ),
    solution_v as (
                 select clist,s,e,substr(clist,rno,1) v
                   from r,
                        edge
               )
    select clist --没有单色三角形的着色方案不存在（即所有的着色方案都存在单色三角形）
      from r
     where clist not in (
                      select --r.clist,t.A,t.B,t.C, listagg(sv.v) within group (order by r.clist,t.A,t.B,t.C,sv.s,sv.e) vlist
                             distinct r.clist
                        from r,triangle_3e t,solution_v sv
                       where sv.clist = r.clist
                         and sv.s = t.s
                         and sv.e = t.e
                       group by r.clist,t.A,t.B,t.C   
                       having listagg(sv.v) within group (order by r.clist,t.A,t.B,t.C,sv.s,sv.e) in ('000','111')        
                       --order by r.clist,t.A,t.B,t.C
                     )

newkid

〇〇 发表于 2021-11-1 23:02
从3～5个确定真币要3次，见我285楼第一段

我的方法是分大组，缩小范围，在小组内查找。我的那些基础推理是从小范围开始，因为较大的范围要用到前面的结论。所以一开始分三组，3X20, 利用我那些基础推论可以做到十次。
你说的是任取三至五个，和我的方法没有关系。

〇〇

newkid 发表于 2021-11-1 23:31
我的方法是分大组，缩小范围，在小组内查找。我的那些基础推理是从小范围开始，因为较大的范围要用到前面的 ...

知道了

〇〇

第10题
You are throwing darts at dartboard having 20 segments. Your first dart lands randomly at one of the segments. After that your each dart randomly lands at a segment left or right of your previous segment. The game finishes after all the segments have been landed and you record the number of darts thrown.

If you play this game many times, what is the average number of darts thrown at the dartboard?

您正在向划分为20 个扇形的飞镖板投掷飞镖。 您的第一个飞镖随机落在其中一个扇形上。 之后，您的每个飞镖都会随机落在上一扇形的左侧或右侧。 在所有扇形都落下飞镖并记录投掷飞镖的数量后，游戏结束。

如果你玩这个游戏很多次，投掷飞镖盘的平均飞镖数是多少？

〇〇

比如第一下投在1，第2下2或20，第3下可能是1，3，19