S2T2

Jim Randell 5:45 pm on 2 November 2021 Permalink Reply
Tags: by: Christopher Higgins ( 7 ), by: Hugh Bradley ( 7 )   

• 

  Jim Randell 5:46 pm on 2 November 2021 Permalink | Reply

  See also: Brain-Teaser 25.

  If the total number of participants is N, and the 7 regions of the Venn Diagram are: B, T, F, BT, BF, TF, BTF, then we have:

  N = B + T + F + BT + BF + TF + BTF
  N/4 = B + BT + BF + BTF
  N/3 = T + BT + TF + BTF
  N/2 = F + BF + TF + BTF
  B + T + F = BTF²

  Summing the middle three, and then replacing (B + T + F) using the last equation:

  (13/12)N = (B + T + F) + 2(BT + BF + TF) + 3BTF
  (13/12)N = BTF² + 2(BT + BF + TF) + 3BTF
  ⇒ 2(BT + BF + TF) = (13/12)N − 3BTF − BTF²

  And from the first equation:

  (BT + BF + TF) = N − (B + T + F) − BTF
  ⇒ (BT + BF + TF) = N − BTF − BTF²

  equating these:

  2N − 2BTF − 2BTF² = (13/12)N − 3BTF − BTF²
  (11/12)N = BTF² − BTF
  ⇒ N = (12/11)BTF(BTF − 1)

  So for a given value of BTF we can calculate the corresponding value for N.

  This Python program considers increasing (BTF, N) values, and looks for an example viable arrangement by calculating values for the remaining areas of the Venn diagram. When it finds an N value that is 50% more than a previously determined value it stops.

  It runs in 54ms.

  Run: [ @replit ]

  from enigma import (irange, inf, div, decompose, sq, Matrix, as_int, printf)
  
  # generate viable configurations
  def solve():
    # consider values for the number that watch all 3 sports
    for BTF in irange(2, inf):
      # calculate N
      N = div(12 * BTF * (BTF - 1), 11)
      if N is None: continue
      BTF2 = sq(BTF)
      if BTF + BTF2 > N: continue
      
      # choose values for BT, BF, TF
      for (BT, BF, TF) in decompose(N - BTF - BTF2, 3, increasing=0, sep=0, min_v=0):
  
        # determine the remaining variables
        eqs = [
          # B  T  F BT BF TF BTF = k
          ((1, 1, 1, 1, 1, 1, 1), N), # B + T + F + BT + BF + TF + BTF = N
          ((4, 0, 0, 4, 4, 0, 4), N), # B + BT + BF + BTF = N/4
          ((0, 3, 0, 3, 0, 3, 3), N), # T + BT + TF + BTF = N/3
          ((0, 0, 2, 0, 2, 2, 2), N), # F + BF + TF + BFT = N/2
          ((1, 1, 1, 0, 0, 0, 0), BTF2), # B + T + F = BTF^2
          ((0, 0, 0, 0, 0, 0, 1), BTF), # BTF
          ((0, 0, 0, 1, 0, 0, 0), BT), # BT
          ((0, 0, 0, 0, 1, 0, 0), BF), # BF
          ((0, 0, 0, 0, 0, 1, 0), TF), # TF
        ]
  
        try:
          (B, T, F, BT, BF, TF, BTF) = Matrix.linear(eqs, valid=(lambda x: as_int(x, "0+")))
        except ValueError:
          continue
  
        yield (N, B, T, F, BT, BF, TF, BTF)
        break # only need one example for any N
  
  # record results by N
  seen = set()
  for (N, B, T, F, BT, BF, TF, BTF) in solve():
    N_ = 2 * N // 3
    printf("N={N}; B={B} T={T} F={F} BT={BT} BF={BF} TF={TF} BTF={BTF} [(2/3)N={N_}]")
    if N_ in seen: break
    seen.add(N)
  

  Solution: The number of participants in the first poll was 2160.

  And there were 3240 in the second poll.

  Here are example arrangements:

  N=2160; B=495 T=585 F= 945 BT=0 BF=0 TF= 90 BTF=45
  N=3240; B=755 T=865 F=1405 BT=0 BF=0 TF=160 BTF=55

  (There are many possibilities for (BT, BF, TF), but for each (N, BTF) pair they sum to the same value).

  ---

  There are many possible arrangements that satisfy the conditions, but there are fewer that have an N value that is 1.5× a smaller N value.

  The program stops when it finds the first solution, but there are further solutions, although they don’t really qualify as “a small sample”:

  N=211680; B=52479 T=53361 F=88641 BT=0 BF=0 TF=16758 BTF=441
  N=317520; B=78840 T=79920 F=132840 BT=0 BF=0 TF=25380 BTF=540

  N=2032553520; B=508095215 T=508181545 F=846940465 BT=0 BF=0 TF=169293130 BTF=43165
  N=3048830280; B=762154704 T=762260436 F=1270398816 BT=0 BF=0 TF=253963458 BTF=52866

  N=199169502480; B=49791948335 T=49792802905 F=82987719985 BT=0 BF=0 TF=16596603970 BTF=427285
  N=298754253720; B=74688040115 T=74689086745 F=124481462365 BT=0 BF=0 TF=24895141180 BTF=523315

  LikeLike

• 

  Hugh Casement 6:30 pm on 2 November 2021 Permalink | Reply

  BTF must be a multiple of 11, or 1 more than that, for N to be an integer.

  For any BTF, N pair there are many possible values for BT, BF, and TF.
  But the sum of those three is determined, as shown in the third grey block of Jim’s analysis,
  and it also equals N/12 – 2BTF.

  It turns out to be negative is BTF is too small.

  LikeLike

• 

  GeoffR 8:02 pm on 2 November 2021 Permalink | Reply

  It is easy just to use Jim’s five basic equations in a MiniZinc solution as constraints, although fixing the ranges of variables was not easy to pre-determine.

  The programme took under 2 sec to find the answer, but nearly 2 minutes to exhaust all the subsequent searching with the Chuffed Solver.

  % A Solution in MiniZinc
  include "globals.mzn";
  % re-using Jim's basic equations
  % using upper case variables for the first survey
  % ..and lower case variables for the second survey
  
  var 1..1000:B; var 1..1000:b;
  var 1..1000:T; var 1..1000:t;
  var 1..2000:F; var 1..2000:f;
  var 0..500:BT; var 0..500:bt;
  var 0..500:BF; var 0..500:bf;
  var 0..1000:BTF; var 0..1000:btf;
  var 0..500:TF; var 0..500:tf;
  var 3..5000:N; var 3..5000:n;
  
  % First Survey - main equations
  constraint N == B + T + F + BT + BF + TF + BTF;
  constraint N == 4 * (B + BT + BF + BTF);
  constraint N == 3 * (T + BT + TF + BTF);
  constraint N == 2 * (F + BF + TF + BTF);
  constraint B + T + F == BTF * BTF;
  
  % Second Survey
  % For second survey,  people questioned increased by 50%
  constraint 2 * n == 3 * N;
  
  % Second survey - main equations
  constraint n == b + t + f + bt + bf + tf + btf;
  constraint n == 4 * (b + bt + bf + btf);
  constraint n == 3 * (t + bt + tf + btf);
  constraint n == 2 * (f + bf + tf + btf);
  constraint b + t + f == btf * btf;
  
  solve satisfy;
  
  output [ "People questioned in the first poll = " ++ show(N) ];
  
  % People questioned in the first poll = 2160
  % ----------
  % ==========
  
  
  

  LikeLike