Ponder This: Sous Chefs

Solve the IBM Ponder This Challenge for November 2016 and discover the answer to the ultimate question of life, the universe, and everything!

The Challenge

12 chefs (one for each month of the year) each has N sous chefs. The chefs divide the sous chefs into three shifts: N1, N2 and N3 where N=N1+N2+N3 and no two numbers are the same. After this partition, the three sets of sous chefs are randomly assigned to prepare the three daily meals (morning, lunch, and dinner). For each meal, the chef who has more sous-chefs wins. If both chefs chose the same number - the result is a draw. When comparing two chefs, the one who won more meals wins.

For example: if N=9 and January's chef decided to split to 1,2,6 and February's chef decided to split to 2,3,4 then there are six possible permutations:

Jan      Feb    meals winner    overall winner
1 2 6 vs 2 3 4  Feb, Feb, Jan   Feb
1 6 2 vs 2 3 4  Feb, Jan, Feb   Feb
2 1 6 vs 2 3 4  Draw, Feb, Jan  Draw
2 6 1 vs 2 3 4  Draw, Jan, Feb  Draw
6 1 2 vs 2 3 4  Jan, Feb, Feb   Feb
6 2 1 vs 2 3 4  Jan, Feb, Feb   Feb

So the end result is that February wins. On the other hand, if the March chef chose 0,4,5, then he will win against February, but will lose to January.

IBM's Chef Watson analyzed the situation as a restaurant critic, and found that in every duel, the chef who wins is the one whose month appears first after a random date, i.e., when the June and July chefs are competing, June will win, but April will lose to December. In the event of a tie (like April and October), the culinary match ends with a tie as well.

Find the minimal N and a possible choice of the 12 chefs that can allow such a situation to occur. Supply your answer as a set of 12 triplets of integers.

The Rules

function Team(breakfastShiftSize, lunchShiftSize, dinnerShiftSize) {
  this.a = parseInt(breakfastShiftSize);
  this.b = parseInt(lunchShiftSize);
  this.c = parseInt(dinnerShiftSize);
  if (this.a === this.b || this.b === this.a || this.a === this.c) {
    throw new Error('shift sizes cannot be equal');
  }
  Object.freeze(this);
}
Team.prototype = {
  toString: function() {
    return '(' + this.a + ', ' + this.b + ', ' + this.c + ')';
  },
  playGame: function(other, x) {
    return this[x] > other[x] ? 1 : this[x] < other[x] ? -1 : 0;
  },
  playSet: function (other) {
    var score = 0;
    score += this.playGame(other, 'a');
    score += this.playGame(other, 'b');
    score += this.playGame(other, 'c');
    return score > 0 ? 1 : score < 0 ? -1 : 0;
  },
  playMatch: function(other) {
    var score = 0;
    score += this.playSet(new Team(other.a, other.b, other.c));
    score += this.playSet(new Team(other.a, other.c, other.b));
    score += this.playSet(new Team(other.b, other.a, other.c));
    score += this.playSet(new Team(other.b, other.c, other.a));
    score += this.playSet(new Team(other.c, other.a, other.b));
    score += this.playSet(new Team(other.c, other.b, other.a));
    return score > 0 ? '>' : score < 0 ? '<' : '=';
  }
}
function compete(teams) {
  var i, j, team1, team2,
    winLossRecord, standings = [];
  for (i = 0; i < teams.length; i++) {
    winLossRecord = [];
    team1 = teams[i];
    for (j = 0; j < teams.length; j++) {
      team2 = teams[j];
      winLossRecord.push(team1.playMatch(team2));
    }
    standings.push(winLossRecord);
  }
  return standings;
}

Arrange Shifts (editable)

function getTeams(teamCount, teamSize) {
  var i, a, b, c,
      n = parseInt(teamCount), // number of chefs
      m = parseInt(teamSize),  // number of sous chefs
      teams = [];
  for (i = 0; i <= n/2 - 1; i++) {
    c = n/2 + i;     /* J.P.S. */
    b = 1 + n/2 + i;     /* J.P.S. */
    a = m - (b + c);
    teams.unshift(new Team(a, b, c));
  }
  for (i = n/2; i <= n - 1; i++) {
    c = i - (n/2);   /* J.P.S. */
    b = 1 + n + i - n/2; /* J.P.S. */
    a = m - (b + c);
    teams.unshift(new Team(a, b, c));
  }
  return teams;
}

function getTeams(teamCount, teamSize) {
  var i, a, b, c,
      n = parseInt(teamCount), // number of chefs
      m = parseInt(teamSize),  // number of sous chefs
      teams = [];
  for (i = 0; i <= n/2 - 1; i++) {
    c = 0;           /* to do */
    b = 1;           /* to do */
    a = m - (b + c);
    teams.unshift(new Team(a, b, c));
  }
  for (i = n/2; i <= n - 1; i++) {
    c = 0;           /* to do */
    b = 1;           /* to do */
    a = m - (b + c);
    teams.unshift(new Team(a, b, c));
  }
  return teams;
}

Headcount Target (editable)

function getMinTeamSize(teamCount) {
  var n = parseInt(teamCount);
  return 3*n + n/2; /* J.P.S. */
}

function getMinTeamSize(teamCount) {
  var n = parseInt(teamCount);
  return 3;         /* to do */
}

Sous Chefs per Chef

(goal is to minimize)

Number of Chefs

Teams

Standings

---

Questionable Logic

(Some steps are left as exercises for the non-Ramanujanian reader.)

Let a = b mean a equals b.
Let a <> b mean a does not equal b.
Let a >= b mean a is greater than or equal to b, etc.

Without the constraint that no two number may be the same:

When comparing teams for two months, the order of the members of a team doesn't matter, because every permutation of one team's members is compared against every permutation of the other team's members, and the outcomes carry equal weight. So for a given team (a, b, c), the members of the team may be ordered such that a >= b >= c. A team ordered this way may represent all other orderings of the same team members for comparison sake. So for the remainder of this discussion, let the members of a team be ordered (left to right) from largest to smallest value.

First, consider the case where two competing months must tie. (In the present case where there are 12 months, examples include Jan vs. Jul, Feb vs. Aug, etc. In a more general case where there are n months, n being even and greater than zero, arranged in an array and i is an index in [0, 1, ..., n-1], competing months that must tie are months[i] vs. months[(i+n/2) modulo n)].) Let (a, b, c) be the team for one of the two months, Mi, and (x, y, z) be the team for the other month, Mj. If a = x, b = y, and c = z, then Mi and Mj tie, of course. But that won't do generally speaking, since one of the teams must beat all the months in between and the other must lose to all of the months in between; and that can't happen if the two teams have the same members. So either (a > b > c and x > y >= z) or (a >= b > c and x > y >= z), where b <> c or y <> z. In the former case, Mi and Mj tie. In the latter, Mi beats Mj. So when two moths tie, the members of the teams must be such that a > b > c and x > y >= z, where a+b+c = x+y+z, per the rules of the game.

Empirical evidence, deduction, intuition, or some combination thereof leads to the conclusion that a minimal solution to the more general problem (n months, where n is even and greater than zero) must be "congruent" to the following solution described in terms of a "first half" and a "second half" of teams (a, b, c), where the first half describes the partitioning of sous chefs for months M0 to Mi, where i = n/2 - 1; the second half describes the partitioning of sous chefs for months Mi+1 to Mn-1; m is the minimal number of sous chefs; and each team in one half must tie the corresponding team in the other half:

First half:

M0: (m-(b+c), n/2, n/2)
M1: (m-(b+c), n/2 + 1, n/2 + 1)
...
Mi: (m-(b+c), n/2 + (n/2 - 1), n/2 + (n/2 - 1))

Second half:

Mi+1: (m-(b+c), n, 0)
Mi+2: (m-(b+c), n + 1, 1)
...
Mn-2: (m-(b+c), n + (n/2 - 2), n/2 - 2)
Mn-1: (m-(b+c), n + (n/2 - 1), n/2 - 1)

In the final team, Mn-1, the minimal value of a = m-(b+c) that will work is b+1 (as discussed above).

So: m = 3n + n/2 - 2.

Or:

Mi: (a, b, c)
Mi: (m-(b+c), n/2 + i, n/2 + i) for 0 <= i <= n/2 - 1
Mi: (m-(b+c), n + i - n/2, i - n/2) for n/2 <= i <= n-1
Where m = 3n + n/2 - 2
and in the case of 12 months:
    M0 corresponds to Dec, ..., M11 corresponds to Jan

With the constraint that no two numbers may be the same:

Mi: (a, b, c)
Mi: (m-(b+c), 1 + n/2 + i, n/2 + i) for 0 <= i <= n/2 - 1
Mi: (m-(b+c), 1 + n + i - n/2, i - n/2) for n/2 <= i <= n-1
Where m = 3n + n/2