搜索

I saw this problem online recently.

Passenger distribution on a train

Not a terribly difficult problem to solve. But it was mildly interesting to find a solution using MATLAB. Perhaps just as interesting is the post analysis of the problem to understand what is happening, and why any unique solution exists at all for one specific car.

The question is, we have a passenger train with 11 cars in it. Feel free to number them 1 through 11. We know that 381 passengers boarded the train. Every passenger is in one of the cars, but all we know is there are exactly 99 passengers in every set of three consecutive cars. Now the question becomes, how many passengers are in car number 9?

One might say at first this is impossible to know. Surely there are many ways the passengers may be arranged, but is that true? Could it be impossible to solve?

First, before we go any further, a few tests seem important. Logically, we might think to distribute 33 passengers in every car. Would that work? So we would have a passenger distribution of

X1 = repmat(33,11,1)

X1 =
    33
    33
    33
    33
    33
    33
    33
    33
    33
    33
    33

While that satisfies the requirement of every 3 consecutive cars having 99 passengers, it fails the total count requirement, since we can see the sum of all passengers would be 363. This yields too few total passengers, with only a combined load of 363 passengers, and we need 381.

At the other end of the spectrum is another extreme case. We might have this distribution:

X2 = zeros(11,1);
X2(1:3:11) = 99
X2 =
    99
     0
     0
    99
     0
     0
    99
     0
     0
    99
     0

Again, it meets the requirement that the sum of passengers in any 3 consecutiuve cars will be 99. But that case yields too many total passengers at 396. Somewhere in the middle must/might/may be a solution, right? At least it is good to see that we can have more or less than 381 total passengers. But how can we find a solution using MATLAB?

There is one other problem with the X2 attempt at a solution, in that had I chosen a different first car to place the 99 passengers, we need not have a unique result in car number 9.

X3 = zeros(11,1);
X3(2:3:11) = 99;

X4 = zeros(11,1);
X4(3:3:11) = 99;

Each of those schemes would put 99 passengers in every set of 3 consecutive cars.

[X2,X3,X4]
ans =
    99     0     0
     0    99     0
     0     0    99
    99     0     0
     0    99     0
     0     0    99
    99     0     0
     0    99     0
     0     0    99
    99     0     0
     0    99     0

But car number 9 would have very different numbers of passengers, depending on the choice made, either 0 or 99 passengers.

An obvious solution is to look for a code that can solve such a problem for us. INTLINPROG stands out as the perfect tool, as this is a linear problem, with everything being in the form of a sum. The unknowns will be how many passengers are sitting in each car. There are 11 cars. So there are 11 unknowns. The bounds are simple.

lb = zeros(1,11); % There cannot be less than zero passengers in any car.
ub = repmat(99,1,11); % since the sum of any three consecutive cars is 99, we cannot have more than 99 people in any one car.

All of the unknown car counts must be integer. That is, we cannot have a fractional number of people in a car, unless this is part of an Agatha Christie murder mystery.

intcon = 1:11;

What constraints apply? First, the sum of all passengers on the train must be 381.

As well, we know that in every 3 consecutive cars, the sum must be 99. Both constraints will take the form of exact linear equality constraints. We can encode all of that into the matrix Aeq, and the vector Beq.

Aeq = [ones(1,11);triu(tril(ones(9,11),2))]; % A tricky way to create the matrix Aeq
Beq = [381;repmat(99,9,1)];

If X is a potential solution that satisfies the bound constraints, it must satisfy the matrix equation Aeq*X==Beq.

We can see for example, the potential solutions I posed above as X1,...X4, all fail to satisfy the requirement on the total number of passengers, since while the sums for consecutive cars are correct, the total sum is not.

Aeq*[X1,X2,X3,X4]
ans =
   363   396   396   297
    99    99    99    99
    99    99    99    99
    99    99    99    99
    99    99    99    99
    99    99    99    99
    99    99    99    99
    99    99    99    99
    99    99    99    99
    99    99    99    99

Finally, there are no linear inequality constraints.

A = [];
B = [];

At this point, you might be wondering how we can formulate this as a linear programming problem at all. What would be the objective function? What could we hope to minimize? As it turns out, linear programming tools are pretty simple in that respect. We could pose just about any objective we want. For example, this is sufficient:

f = ones(1,11);

Effectively, we are just using intlinprog to see if a FEASIBLE integer solution exists that satisfies all of the bounds, as well as the equality constraints. This is why the objective can be the same as one of the equality constraints. Once INTLINPROG finds any solution, it will be done.

And now we can throw the problem into INTLINPROG, hoping something intelligent falls out.

[X,~,EXITFLAG] = intlinprog(f,intcon,A,B,Aeq,Beq,lb,ub)
P:                Optimal objective value is 381.000000.                                           

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

X =
     0
    84
    15
     0
    84
    15
     0
    84
    15
     0
    84
EXITFLAG =
     1

intlinprog has found a solution,

isequal(Aeq*X,Beq)
ans =
  logical
   1

The solution satisfies all of the constraints. Effectively, we see the repeating sub-sequence [0 84 15] in consecutive cars. And of course, as long as we repeat that sequence, it does satisfy all requirements. How many people are sitting in car number 9? 15 people.

Symmetry would suggest that car number 3 must have the same number of people, since we could as easily have numbered the cars starting from either end. And of course, X(3) was also 15.

Thankfully our intuition works there. It would seem we are done now. Or are we?

For some of you, you might be wondering if any other solutions can possibly exist. And some of you might be wondering if any of those solutions can have some other number of passengers than exactly 15 in cars number 3 and 9.

NULL is the MATLAB function to come to the rescue here.

This is essentially a linear algebra question. We wish to know the solutions of the problem Aeq*x==Beq. Here, Aeq is a 10x11 matrix, so it has rank at most 10. That means there is a vector Y, such that Aeq*Y == 0.

Y = double(null(sym(Aeq)))
Y =
    -1
     1
     0
    -1
     1
     0
    -1
     1
     0
    -1
     1

What does that tell us? If we have some particular solution (X) to the non-homogeneous problem Aeq*X==Beq, then the set of all possible solutions will be of the general form

syms t
X + t*Y
ans =
    -t
t + 84
    15
    -t
t + 84
    15
    -t
t + 84
    15
    -t
t + 84

You may see that this generates all solutions to the general problem. We can see a few of them in this array:

[X-1*Y, X - 2*Y, X - 3*Y, X - 84*Y]
ans =
     1     2     3    84
    83    82    81     0
    15    15    15    15
     1     2     3    84
    83    82    81     0
    15    15    15    15
     1     2     3    84
    83    82    81     0
    15    15    15    15
     1     2     3    84
    83    82    81     0

We see now there are 85 such possible integer solutions, all of the form X-k*Y, where k can be any positive integer from 0 to 84 inclusive. INTLINPROG found one of them. But as importantly, do you see that since the elements

Y([3 6 9])
ans =
     0
     0
     0

are all identically zero, that those elements in the solution can never change? Those cars must always contain exactly 15 passengers for all of the constraints to be satisfied. I'll be honest, it is not at all obvious as to why it works out that way, at least not initially in my eyes. That leaves my intuition wanting, just a bit.

How might we analyze this problem in a different way? Perhaps a different approach would yield a more satisfying solution. Suppose we chose a passenger partitioning that is strictly repetitive? For example, choose three non-negative integers u,v,w, such that u+v+w=99.

Now, fill the cars using the sequence

syms u v w
X = [u v w u v w u v w u v];

Surely you would agree that any subset of 3 consecutive cars adds to 99, as long as u+v+w=99. But then the sum of all 11 cars in that sequence must be 4*u+4v+3*w. And this leaves us with now two equations in three unknowns. We have

EQ1 = sum(X) == 381;
EQ2 = u + v + w == 99;

The rest is easy now, as we can do

EQ1 - 3*EQ2
ans =
u + v == 84

So if a solution in this form exists, we can see that u+v=84, and therefore w=99-u-v=15. (Remember that w was the number of passengers in car number 9, but also in cars numbered 3 and 6.) Any combination of non-negative integers that sums to 84 will work for u and v though.

This constructive approach does not insure it is the ONLY solution, since I built it from the sequence in the vector X. Perhaps a solution exists that is not simply repetitive as I created it. In fact, the previous analysis using null told us the whole story.