Draw a Clock (DrawClock)

Run LPL Code  ,  PDF Document

Problem

This model draws a clock. It is the template for the following simple puzzle: “Divide the clock with a straight cut into two parts such that the sum of the numbers in both parts are equal ?”. Can you see the solution at once?

Modeling Steps

The key idea here is: Link the numbers 12 with 1, 11 with 2, 10 with 3, 9 with 4, 8 with 5, and 7 with 6 each by a straight line. The sum of the 6 pairs of matched numbers is always 13. Cut the clock into two parts between the 3-rd and 4-th line. On each side, the sum of the numbers is 3 ⋅ 13 (see Figure 2). Puzzle solved!

To prove that this is the unique solution, we must show that there is not another consecutive sequence of numbers on the clock face that sums to the half of all numbers. Let’s choose two numbers 1 ≤ x < y ≤ 11. The sum of all numbers on the face from y + 1 to x in clockwise direction is the sum from y + 1 to 12 plus the sum from 1 to x (note that the sum of the numbers from 1 to n is given by n(n + 1)∕2):

This quantity must be half of all numbers from 1 to 12, that is it must be . Simplifying leads to:

As y -x < y + x + 1, we conclude that y + x + 1 = 13 and y -x = 6. Resolving for x and y gives: y = 9 and x = 3. Hence the unique solution is a consecutive sequence from 10 to 3 in clockwise direction.

Solution

This innocent simple problem can also be formulated as a mathematical model. It is a Knapsack problem with additional conditions. Given the set i ∈{1,…, 12}, let’s introduces a binary variable x_i, where x_i = 1 if the number i is on one side of the cutting line, and x_i = 0 if it is on the other side.

1. Certainly, we must have that the sum of the numbers on one side must by half of the sum of all numbers, that is:

   

   This is in fact a Knapsack condition.

2. However, there is an additional requirement that the numbers on the two sides must be consecutive. We can express this by the following observation: take two consecutive numbers (modulo 12, that is, the next number of 12 is 1, etc.). There are 12 of such tuples, namely (1, 2), (2, 3), …, (12, 1). Exactly for 2 of these tuples the condition holds that the variables x_i and the next consecutive variable, expressed as x_{i mod 12+1}, are different. This is the case when the cutting line passes. This fact can be expressed as a logical condition as follows:

   

3. Solving the model gives x₁ = 1 for i ∈{4,…, 9}, as expected.

Hence, the complete model is as follows:

The model implemented in LPL is straightforward :

  model solveIt; 
 
    set i:=1..12; 
 
    binary variable x{i}; 
 
    constraint A: sum{i} i*x = (sum{i} i)/2; 
 
    constraint B: exactly(2){i} (x[i] <> x[i%#i+1]); 
 
    solve; 
 
    Write('The numbers%3d are on one side' n',{i|x} i); 
 
  end;

Further Comments

Of course, one also can enumerate all possibilities. How many are their? 12 for cutting one number, 11 for cutting 2 (consequtive) numbers, 10 for cutting 3 (consequtive numbers, etc. That is,

We could quickly eliminated most possibilities! However, the zest is to have a systematic procedure, and yes modeling is fun. No?

References