2022 PUZZLEUP

newkid

#8 FIVE-LETTER CODE 新思路：

从小的情形开始推理。假设这个代码只有两位，则总共只能5个。假如有第六个，根据抽屉原理，它的第一位必定已经出现过，和那个出现过的一比，最多就只有一位不同了。

三位的即上述情形追加一位，这新的一位最多五种取值，每种取值不能超过上述两位的五种，所以最多就是5*5=25种。
同理，四位最多5^3，五位最多5^4=625种

下面就来凑出这625种，并且验证它满足题目条件：
CREATE TABLE R8 (s varchar2(5));

declare
  type tc is table of varchar2(10) index by pls_integer;
  type tc2 is table of tc index by pls_integer;
  v_tc tc2;
  v_cnt number;
begin

  v_tc(21)(1):='AA';
  v_tc(22)(1):='BB';
  v_tc(23)(1):='CC';
  v_tc(24)(1):='DD';
  v_tc(25)(1):='EE';


  FOR i IN 3..5 LOOP
      v_cnt :=0;
      for j in 1..5 loop
          -- dbms_output.put_line('i='||i||' j='||j);
          for k in 1..v_tc((i-1)*10+j).count loop
              v_cnt := v_cnt+1;
              v_tc(i*10+1)(v_cnt):='A'||v_tc((i-1)*10+j)(k);
          end loop;
      end loop;

      for j in 2..5 loop
          for k in 1..v_cnt-power(5,i-3) loop
              v_tc(i*10+j)(k):=CHR(64+J)||substr(v_tc(i*10+j-1)(k),2,1) || substr(v_tc(i*10+j-1)(k+power(5,i-3)),-(i-2));
          end loop;

          for k in v_cnt-power(5,i-3)+1..v_cnt loop
              v_tc(i*10+j)(k):=CHR(64+J)||substr(v_tc(i*10+j-1)(k),2,1) || substr(v_tc(i*10+j-1)(k-v_cnt+power(5,i-3)),-(i-2));
          end loop;

      end loop;
  END LOOP;

      for j in 1..5 loop
          for k in 1..v_tc(50+j).count loop
              dbms_output.put_line(v_tc(50+j)(k));
              insert into r8 values(v_tc(50+j)(k));
          end loop;
      end loop;
end;
/

验证：

with r as (
select r8.s
      ,n
      ,SUBSTR(r8.s,n,1) c  
from r8,(select level n from dual connect by level<=5)
)
select r1.s
      ,r2.s
  from r r1, r r2
where r1.s<>r2.s
       and r1.n=r2.n
group by r1.s,r2.s
having count(case when r1.c<>r2.c then 1 end)<2
ORDER BY 1,2;

no rows selected

jihuyao

On #13, forget condition 3 for now and assume condition 4 means {abc} can only occur once in all groups.  Now consider 2 member group given 4 people.  C(2,4)= 6 is the maximum number of groups (3 in art and 3 in sport).  (C(2,4)*C(2,2))/(2!)=3, so minimum is 4 (take 1 among 3, eg, {ab} and {cd} for art, and take a different one among 3, eg, {ac} and {bd}.  It seems that no solution can be obtained by adding condition 3.  Let us go on 3 member given 6 people.  For maximum, C(6,3)=20, for minimum, C(6,3)*C(3,3)/2!=10, take 2 among 10 for art and take another 2 among 10 for sport (ensure both groups meet condition 2 (abcdef at least appear once in both).  So 4 is possible solution when adding condition 3.  If not, take the 3rd among 10 for art and take the 4th among 10 for sport.  If still no solution, go on until all 10 are used up.  In comparison to 20 as all candidates, perform brutal fore process.  Without really playing it, I would think only take the 10 candidates has a good chance to find a solution.  But certainly I have no prove for this.

jihuyao

Continue on #13.  Without seeing the result from 3-member groups and 6 people class, it would be crazy to do it in following way.  But it works.  First, take abc in group I which needs 3 (ab_,ac_,bc_) in group II to match.  Fill in d,e,f in the 3 above ( abd, ace, bcf) (greedy approach) which needs (ad, bd, ae, ce, bf, cf) in group I to match in turn.  Combine ad and ae to form ade which covers ad and ae while leads de_ in group II to match the new born ade in group I.  Similarly, bdf to cover bd and bf with df being left, and cef to cover ce and cf with ef being left.  Now, with de, df, ef being left for matching, form def in group II which exactly matches de, df, ef needed to close the processing loop.  The result is, abc/ade/bdf/cef in group I, and abd/ace/bcf/def in group II.  This is the same result by newkid after switching e/f.  I will try to expand the way to 3-member and 9/12 people class.

newkid

把你的思路写出来看看如何？
注意你上面说的 d,e,f 可能重叠，它们可能是一个点，两个点，或三个点。
我觉得12点的答案就是6点X2, 即8*2=16个三角形。

六个点图示：考虑一个类似金字塔的四面锥体，底部是四边形ABEF, 顶点是C
四个侧面三角形，按照两种颜色错开。
另外一个一样的锥体，底部也是ABEF, 顶点是D, 四个三角形侧面也是两种颜色错开，两个锥体倒扣在一起。
两个锥体的三角形的颜色在底部的同一条边错开。比如底部的AB边，一面是三角形ABC为蓝色，另一面就是ABD为红色。一个锥体的颜色是红蓝红蓝，另外一个则是蓝红蓝红。

jihuyao

There is a clear pattern for 3-member group and 3*m (m>1) people.  For 6 people, 4*2 groups, 9 people (1+2*3)*2 groups, 12 people, (1+3*3)*2 groups in total.  Answers meet condition 3 though there is not theoretical prove but practical prove narrows much work amount comparing to the complete brutal force process.  I think, in stead of greedy approach, introduce one new person along with each processing step could be used as general way for m-member group and n people (with some simple rule being followed in each step).  Below is the answer for 9 people, art (abc/ade/bdf/cef/dgh/egi/chi), sport (abd/ace/bcf/deg/dfh/efi/ghi) .  The pattern is so obvious I skip the 12 people.  Basically, if it is 4 step for 3-member group and 6 people, repeat step2/3 once for 9 people and twice for 12 people.  I did not try brutal force since it must be very time consuming with increasing people.  Maybe I should upload the hand writing paper work for each step but 1st step states the main logic for following steps, eg, starts with ONE group ABC in art, and there must THREE groups in sport to match it in order to meet condition 3 (ABx, ACy, BCz where xyz can be any for a valid group being generated).  For greedy purpose, take as many as new ones, D, E, F (because ABC already picked)).

newkid

你认为12人的答案是20? 可是我把他们分成不相干的两组，每组六人，总共也才8*2=16？

jihuyao

No no no. My first one is just overall analysis with no idea on condition 3.  After seeing your result for 6 people I started focus on the later approach.  I tried upload or copy/paste my hand writing paper work but failed somehow.  Here I give the result for 12 people.  Art (ABC/ADE/BDF/CEF/DGH/EGI/FHI/GJK/HJL/IKL), sport(ABD/ACE/BCF/DEG/DFH/EFI/GHJ/GIK/HIL/JKL).  6 appear twice and 6 appear trice. 6*2+6*3=30=10*3.

jihuyao

Yes, 20 is the minimum for 12.  Little bit confused.  Although no prove it must be the minimum but I can take a general approach (rather than greedy approach) in step2/3, eg for abc to be matched by abX/acX/bcX which will quickly increases the total group number in art and sport and reaches 20 even before all people have participated at least once.  This way will still much faster than brutal force (I believe).  There are 3 choices in step 2, (ABx/ACx/BCx) or (ABx/ACx/BCy) or (ABx/ACy/BCz).  The option1/2 will quickly increase the total group number in art and sport even before the whole process end (with or without a valid solution obtained).

newkid

你的最小答案是20, 但是16不是一个明显更小的答案吗？只需把六个人简单加倍，因为是两个互相独立的群体。

他的第三个条件还是有点不清楚：
-For any pair of students, the number of arts groups and the number of sports groups that both students are members are the same.
这两个数字是不是允许都为零？
如果都必须大于零，那么6个人的答案也不是8了。

jihuyao

It is true.  My mind had such flash but somehow forgotten when 6 people is processed in this approach.  Basically close the loop at step 4 after abcdef is picked.  Then repeat step 1-4 using GHIJKL and close the 2nd loop.  Good catch!  It makes process even simpler.  Without theoretical prove or brutal force, it is hard to tell the real minimum value but at least narrow down the range to search.  For 6 people, eg, we know the possible minimum is 2+2, and we also know 4+4 is a valid candidate.  Can we prove 3+3 is not minimum for 6 people?  Easy in brutal force.  But also easy to see it in this approach.  3+3=6 is impossible to meet condition 3 for 6 people.  For your thought on all pairs >0, have you checked the possible maximum with 10 in art and another 10 in sport?  Does it meet condition 3?  Really need doing more homework before ask this.  Sorry for such lazyness.