A fun math problem

Here is a question from the Mathematical Association of America’s American Mathematics Competitions blog (which I found through this constraint programming blog):

Let x and y be two-digit integers such that y is obtained by reversing the digits of x. The integers x and y satisfy x^2 – y^2 = m^2 for some positive integer m. What is x + y + m?

This is easily solved using Solver Foundation’s constraint programming solver. The OML model is simple:

Model[
  Decisions[
    Integers[0, 9], x1, x2, y1, y2
  ],
  Decisions[Integers[10, 100], x, y],
  Decisions[Integers[1, Infinity], m, theAnswer],

  Constraints[
    x == 10 * x1 + x2,
    y == 10 * y1 + y2,
    y == 10 * x2 + x1,
    x * x - y * y == m * m,
    theAnswer == x + y + m
  ]
]

Update 10/4/2011: reader Bruno Repetto noted the following:

  • In the declaration  
    Decisions[Integers[0, 9], x1, x2, y1, y2],
    the range should be Integers[1, 9].  If 0 is included, this declaration alone could allow for one of the numbers x or y to be single-digit.
  • In the declaration  
    Decisions[Integers[10, 100], x, y],
    the range should be Integers[10, 99], as x and y are restricted to be two-digit integers.

Of course, given the constraints of the problem, the first and second declarations will work together to ensure that the x and y numbers are only two-digit integers, but it doesn’t hurt that the declarations be tighter.

 

Advertisement

The rumored Big Ten realignment is extremely fair…and I can prove it.

Andy Katz from ESPN.com reports that the Big Ten divisions will be:

Division A Division B
Iowa Illinois
Michigan Indiana
Michigan State Ohio State
Minnesota Penn State
Nebraska Purdue
Northwestern Wisconsin

Yesterday I posted several Solver Foundation models that attempted to find a realignment that is “as fair as possible”. If you take a characterization of a program’s historical strength to be its Sagarin rating over the past twelve years, and you are looking to build two evenly matched divisions then this is an extremely fair proposal. The average Sagarin rating is almost identical:

Division A   Division B  
Iowa 77.46 Illinois 69.56
Michigan 82.98 Indiana 65.55
Michigan State 75.82 Ohio State 87.67
Minnesota 73.96 Penn State 82.03
Nebraska 83.65 Purdue 77.25
Northwestern 69.61 Wisconsin 81.59
Average A 77.25 Average B 77.27

In fact, this is the fairest possible realignment that follows these rules:

  • Six teams per division.
  • Preserve the Michigan, Ohio, and Indiana in-state rivalries. (But not Illinois.)
  • “Fairness” is measured by Sagarin rating.

No artificial rules about splitting Michigan and Ohio State are required – that happens naturally as a result of trying to find a fair split. Division A has 427 total conference wins since ‘93, Division B has 412. Division A has 724 total wins versus Division B’s 708. Note however that Nebraska is in Division A and that it had a run of near perfection in the early 90’s. The average attendance for Division A schools is 69,128 versus 74,035 in Division B; much of the difference is due to Northwestern.

Download this spreadsheet to see more details, or to create your own realignments. Follow my instructions from yesterday if you wish to use Solver Foundation to experiment with the models.

Using Solver Foundation to get a job at Facebook

Facebook has opened an office in Seattle, check it out. Unfortunately (or fortunately depending on one’s perspective) you need to solve two puzzles to get an invite to the opening party. Here is the first puzzle:

You are given a list of relationships between the letters in a single word, all of which are in the form: "The first occurrence of A comes before N occurrences of B.” You can safely assume that you have all such relationships except for any in which N would be 0. Determine the original word, then go to http://www.facebook.com/seattle/[insert-word-here] to find the second part of the puzzle.

The first occurrence of ‘e’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘n’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘i’.
The first occurrence of ‘n’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘e’ comes before 1 occurrence of ‘e’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘v’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘i’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘v’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘t’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘v’ comes before 1 occurrence of ‘s’.
The first occurrence of ‘v’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘t’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘i’ comes before 2 occurrences of ‘e’.
The first occurrence of ‘v’ comes before 1 occurrence of ‘t’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘t’.
The first occurrence of ‘v’ comes before 1 occurrence of ‘i’.
The first occurrence of ‘i’ comes before 1 occurrence of ‘t’.
The first occurrence of ‘n’ comes before 1 occurrence of ‘s’.

Here’s an OML model that solves the puzzle.

Model[

  Decisions[
    Integers[0, 8], e, e_, s, n, v, i, i_, t
  ],

  Constraints[
    e < s, 
    i < n, 
    i < i_,
    n < e, 
    e < e_,
    i < v, 
    n < i_, 
    n < v, 
    i < s, 
    t < s, 
    v < s, 
    v < e, 
    t < e,
    i < e, 
    v < t, 
    n < t, 
    v < i_, 
    i < t, 
    n < s
  ]
]

You’re welcome. (I’m banking on the fact that my readership is small enough to avoid screwing up their event.) It turns out Solver Foundation can be used to solve the second puzzle too, but I will refrain from posting a solution here. Thanks to my buddy John for the tip.

Seminar scheduling with OML

In response to my series on office space allocation models, I received an email from a reader who is trying to adapt the code to solve a related problem. Here is a reworded description of his problem:

  1. I need to assign people to tables for each week of a three-week seminar.
  2. I have 8 people.
  3. I have 4 tables / PCs.
  4. For the second week of the seminar, I don’t want the groups to be the same, and each person must not be at the same table.
  5. For the third and last week these conditions are the same, taking into account the previous two weeks.

The reader was almost able to figure it out but got stuck on the “different groups” and “different tables” constraints. Let’s work through the problem and build an OML model. I like to start by defining the sets for my problem. In this case, they are:

  • People. To be consistent with my previous posts I will call them “Entities”. There are 8 of them.
  • Tables. There are 4 of them.
  • Time periods. There are 3 of them (one week duration).

What do I want Solver Foundation to compute? The assignment of entities to tables for each period. So let’s add a 0-1 integer decision called “assign[e, t, p]” that is 1 if and only if Entity e is assigned to Table t for Period p. If I have this decision then it is easy to write two constraints which are not explicitly stated in the problem description, but which must hold:

  • Assign all: Each entity is assigned to exactly one table for each time period.
  • Two per table: there are two entities per table.

Now I’ve got to handle the “different tables” and “different groups” constraints. It seems natural to use the Unequal operator – this operator forces all of the arguments inside to be different. For “same table” what I want to say is “for each entity, the entity is assigned to a different table over all time periods.” But the “assign” decision is not very helpful; instead I want a decision “table[e, p]” which evaluates to the table that entity e is assigned to for period p. But using a modeling trick I can actually get values for this “table” decision by summing over assign[e, t, p] for a fixed entity and time period and multiplying each by “t”.

The last constraint is the “same group” constraint. This is a bit tricker. Suppose Adam and Bonnie are assigned to table 4 during week 1. I need to make sure that Adam and Bonnie are not assigned to the same table (it doesn’t matter which one) for all other weeks. To model this, I can compute what amounts to a hash (called “group”) for each entity and period. Let’s define group[e, p] to be the sum of all the entity IDs at the same table as Entity e for Period p. If I have this hash then I can simply say that group[e, p] must be different for each period p.

The OML model is below. If you want to try it out, open Excel, flip to the Solver Foundation tab, click on the “Model” tab, change to “Manual” mode, paste the OML, and click Solve.

Two more notes:

  • I need to specify that there are 8 people, 4 tables, and 3 time periods. I do this by specifying ranges in the “assignAll” constraint. This implicitly establishes the values for the Entities, Tables, and Periods sets.
  • The Unequal operator can only be used in Constraint Programming models. CP models cannot contain any real-valued parameters or decisions. It is also possible (I think) to write a mixed integer programming model for this problem but it’s messier.
Model[
  Parameters[Sets[Integers], Entities, Tables, Periods],
  Decisions[Integers[0, 1],
    assign[Entities, Tables, Periods]
  ],
  Decisions[Integers[0, Infinity], 
    table[Entities, Periods], group[Entities, Periods]
  ],

  Constraints[
    assignAll -> Foreach[{e, 0, 8}, {p, 0, 3}, 
        Sum[{t, 0, 4}, assign[e, t, p]] == 1
    ],

    twoPerTable -> Foreach[{p, Periods}, 
      Foreach[{t, Tables},
        Sum[{e, Entities}, assign[e, t, p]] == 2
      ]
    ],

    whichTable -> Foreach[{e, Entities}, {p, Periods}, 
      table[e, p] == Sum[{t, Tables}, t * assign[e, t, p]]
    ],

    differentTables -> Foreach[{e, Entities},
      Unequal[Foreach[{p, Periods}, table[e, p]]]
    ],

    whichGroup -> 
      Foreach[{e1, Entities}, {p, Periods},
        group[e1, p] == Sum[{t, Tables}, 
          assign[e1, t, p] * Sum[{e2, Entities}, e2 * assign[e2, t, p]]]
      ],

    differentGroups -> Foreach[{e, Entities}, 
      Unequal[Foreach[{p, Periods}, group[e, p]]]
    ]
  ]
]