puzzleup 2018

newkid

#10

SCALE

There are X balls that look identical. All balls except one has the same weight. The different ball is either lighter or heavier than the others.

You have a balance scale with two plates and you can only use it to compare the weights of the balls. With each use you can put any number of balls in each plate and as a result find out which side is heavier or if the two sides have the same weight.

You can guarantee finding the different ball and whether it is lighter or heavier by using the scale at most 4 times. What is the maximum possible X satisfying this condition?

有X个球，看起来完全相同。除了一个球之外，其他所有的球具有相同的重量。这个不同的球可能比其他球更轻或更重。

你有一个带有两托盘的天枰，你只能用它来比较球的重量。每次使用时，你可以在每个托盘上放置任意数量的球，从而找出哪一侧较重，或两侧是否重量相同。

通过使用最多4次天枰，你可以保证找到这个不同的球，以及它是更轻或更重。满足这个条件的最大可能X是多少？
------------
这题是有现成答案的，普通智力题都是称三次，更多的情况人脑就处理不来了。

solomon_007

newkid 发表于 2018-10-3 22:40
#10

SCALE

初步估计，如果知道轻重，X 最大 81；不知道轻重，感觉X最大 27

newkid

solomon_007 发表于 2018-10-4 22:38
初步估计，如果知道轻重，X 最大 81；不知道轻重，感觉X最大 27

不止27, 还差挺多。

〇〇

以前好像12个称3次就够
https://blog.csdn.net/gogdizzy/article/details/7686004
https://blog.csdn.net/gogdizzy/article/details/7686023

newkid

第十题的现成答案：
https://zh.wikipedia.org/zh-cn/% ... 3%E5%95%8F%E9%A1%8C

公式是 (3^N-3)/2
当N=4, 答案是 39

newkid

#11
CORDED TRIANGLES

There are X trees in a garden. No three of them are collinear. You have many cords colored yellow, red or blue and you will connect every tree pair with a cord. Cords connecting three trees form triangles and you will receive a penalty point for each triangle that consists of three cords of the same color.

What is the maximum value of X that allows you to place the cords without receiving any penalty points.

花园里有X棵树。其中没有任何三棵是同在一条线上。你有很多绳索，颜色为黄，红或蓝，你用绳索把所有的树两两之间连接起来。连接三棵树的绳索构成三角形，每当一个三角形由三条相同颜色的绳索构成，你就会被扣一分。

允许你放置的绳索不会被扣分的最大X值是什么？

-----------
这道题以前出过了。

solomon_007

#11

--不扣分的有效着色方案有多少种，理论上，找不到方案，N-1就是X的最大值
  --N = 3, 24
        4, 450
        5, 17136
        6, ...

（下面的SQL很蠢，先小试一下，S应该先修枝）
with t as (select level n from dual connect by level <=5),
     triangle as (select t1.n x,t2.n y,t3.n z
                    from t t1,t t2,t t3
                   where t1.n < t2.n
                     and t2.n < t3.n),
     triangle_3e as (select x,y,z, x a1,y b1,x a2,z b2,y a3,z b3 from triangle),
     all_edges as (select rownum rn,a,b
                     from ( select distinct a,b
                             from (
                                  select a1 a,b1 b from triangle_3e
                                   union all
                                  select a2,b2 from triangle_3e     
                                   union all
                                  select a3,b3 from triangle_3e
                                  )
                             order by a,b
                         )
                   ),
     c as (select 'R' color from dual
             union all
            select 'Y' from dual
             union all
            select 'B' from dual),
     s(lvl,color_list) as (select 1, color
                                 from c
                                                        where color = 'R'
                            union all
                           select s.lvl + 1,
                                  s.color_list||c.color
                             from s,c
                            where s.lvl < (select count(rn) from all_edges)
                          )
select 3*count(*)
  from (                     
         select v.color_list
           from (
                   select x,y,z,
                          (select rn from all_edges where a=a1 and b=b1) e1,
                          (select rn from all_edges where a=a2 and b=b2) e2,
                          (select rn from all_edges where a=a3 and b=b3) e3
                     from triangle_3e  
                ) u,
                ( select color_list
                    from s  
                   where lvl = (select count(rn) from all_edges)
                ) v
          where   substr(v.color_list,e1,1)
                ||substr(v.color_list,e2,1)
                ||substr(v.color_list,e3,1) not in ('BBB','RRR','YYY')
          group by v.color_list
         having count(*) = (select count(*) from triangle_3e)
        )

newkid

solomon_007 发表于 2018-10-15 22:50
#11

--不扣分的有效着色方案有多少种，理论上，找不到方案，N-1就是X的最大值

暴力法行不通的，跑几层就跑不动了。除非你有办法把那些拓扑等价的排除掉？

solomon_007

改进 157楼：

今天可以算出 N=6 了，1130346

with t as (select level n from dual connect by level <=6),
     triangle as (select t1.n x,t2.n y,t3.n z
                    from t t1,t t2,t t3
                   where t1.n < t2.n
                     and t2.n < t3.n),
     triangle_3e as (select x,y,z,
                            x a1,y b1,
                            x a2,z b2,
                            y a3,z b3
                       from triangle),
     all_edges as (select rownum rn,a,b
                     from ( select distinct a,b
                             from (
                                  select a1 a,b1 b from triangle_3e
                                   union all
                                  select a2,b2 from triangle_3e     
                                   union all
                                  select a3,b3 from triangle_3e
                                  )
                             order by a,b )
                   ),
      valid_3e as (
                    select
                          (select rn from all_edges where a=a1 and b=b1) e1,
                          (select rn from all_edges where a=a2 and b=b2) e2,
                          (select rn from all_edges where a=a3 and b=b3) e3
                     from triangle_3e),
     c as (select 'R' color from dual
             union all
            select 'Y' from dual
             union all
            select 'B' from dual),
     s(lvl,color_list) as (select 3, c1.color||c2.color||c3.color
                             from c c1,c c2,c c3
                            where c1.color = 'R'
                            union all
                           select s.lvl + 1,
                                  s.color_list||c.color
                             from s,c
                            where s.lvl < (select count(*) from all_edges)
                              and not exists (
                                    select null
                                      from valid_3e
                                     where   substr(s.color_list||c.color,e1,1)
                                           ||substr(s.color_list||c.color,e2,1)
                                           ||substr(s.color_list||c.color,e3,1) in ('RRR','YYY','BBB')
                                   )
                          )
  select 3*count(color_list)
    from s  
   where lvl = (select count(*) from all_edges)

newkid

还差得远呢，你慢慢加。

http://www.itpub.net/thread-1324198-8-4.html
293楼。