Ponder This Challenge - December 2016 - Fair rope pulling

Ponder This Challenge:

The European Union's General Data Protection Regulation (GDPR) is bolstering privacy protection in general and for biometric features in particular.

We would like to hold a competition, but to make it fair we'd like to have all the participants be of similar strength.

Let's assume (for the sake of the challenge) that all the men can apply exactly the same force in a rope-pulling contest, and all the women can apply a different force, but again, same for all.

We want to make sure that all the participants have the same gender.

The simple way to do that (asking for gender in the application form) is not an option (since it might be regarded as a biometric feature), so instead we use a rope-pulling contest.

We have time for four such contests, where we can chose any two equal-sized disjoint subsets of participants and let them compete. If any of these four contests ends not in a tie (i.e., one group wins) then, of course, we've proved that our group is not mono-gender.

We need to find four contests that can prove that all the N participants have the same gender.

For example, here is such a solution for a group of N=16 people:

A ; B

A B ; C D

A B C D ; E F G H
A B C D E F G H ; I J K L M N O P

The challenge, this month, is to find a solution for N at least 27. Bonus '*' for bigger Ns. Use "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" to mark the participants.

Solution

• Click here to view the solution

  All the solutions we present are built on splitting the N persons into groups and running the rope-pulling contest in subsets of these groups.

  Here's an N=27 solution:

  • ABCDEFGHI WXY Z ; JKLMNOPQ RSTUV
  • ABCDEFGHI Z 0 ; JKLMNOPQ WXY
  • ABCDEFGHI ; RSTUV WXY Z
  • JKLMNOPQ Z ; RSTUV WXY 0

  An N=30 solution:

  • ABCD EFGHI JKLMNO ; PQRSTUV WXYZ0123
  • ABCD PQRSTUV ; EFGHI JKLMNO
  • JKLMNO PQRSTUV ; EFGHI WXYZ0123
  • ABCD WXYZ0123 ; EFGHI PQRSTUV

  To verify that the last solution works, you need to show that the integer solutions for the following equation set

      ( 1  1  1 -1 -1 ) (x4)   (0)
      ( 1 -1 -1  1  0 ) (x5)   (0)
      ( 0 -1  1  1 -1 ) (x6) = (0)
      ( 1 -1  0 -1  1 ) (x7)   (0)
                        (x8)
  

  are multiple of (4,5,6,7,8), which means that all the participants are from the same gender as required.

  An N=114 solution for five rope-pulling contests can be achieved by

       1 -1 -1  1 -1  1
      -1  1  0  1 -1  0
       1  1  0 -1 -1  1
       1  0  1  1 -1 -1
       1  1 -1  0  1 -1
  

  with the only integer solution as follows:
  9 12 20 22 25 26

Solvers

• ***Bert Dobbelaere (03/12/2016 11:08 PM IDT)
• ***Arthur Vause (06/12/2016 04:46 PM IDT)
• ***Luke Pebody (07/12/2016 01:20 AM IDT)
• ***Tamir Ganor & Shouky Dan (08/12/2016 09:14 AM IDT)
• ***Jesse Rearick (09/12/2016 05:37 AM IDT)
• ***Aviv Nisgav (12/12/2016 02:54 PM IDT)
• ***Jamie Jorgensen (12/12/2016 05:54 PM IDT)
• ***Uoti Urpala (13/12/2016 05:21 AM IDT)
• ***Liubing Yu (13/12/2016 10:01 AM IDT)
• ***Mtv Europe (13/12/2016 04:15 PM IDT)
• ***Radu-Alexandru Todor (14/12/2016 01:46 AM IDT)
• ***Jim Roche (14/12/2016 06:01 AM IDT)
• ***Shirish Chinchalkar (16/12/2016 02:32 AM IDT)
• ***YanWu-He (16/12/2016 01:32 PM IDT)
• ***Tomáš Jurík (22/12/2016 02:27 PM IDT)
• ***Todd Will (22/12/2016 09:56 PM IDT)
• ***Pål Hermunn Johansen (23/12/2016 08:54 PM IDT)
• *Tyler Mullen (25/12/2016 02:24 PM IDT)
• *Aradesh (27/12/2016 02:39 PM IDT)
• ***Zusheng Ji (27/12/2016 04:05 PM IDT)
• ***David Greer (28/12/2016 05:19 PM IDT)
• ***Siddharth Joshi (28/12/2016 06:30 PM IDT)
• ***Vladimir Dorofeev (29/12/2016 06:47 PM IDT)
• ***Kang Jin Cho (30/12/2016 11:21 AM IDT)
• ***Hao Wu (30/12/2016 11:35 PM IDT)
• ***George W Barnett (31/12/2016 12:15 AM IDT)