CTK Insights

The US Constitution mandates fair and equitable distribution of seats among the member states. Starting with 1790, the population census has been conducted every tenth year. Several methods (algorithms, one can say) for the seat distribution (known as apportionment) have been considered; some tried at different times bringing to light curious inconsistencies. Needless to say that from the very beginning the choice of the method for apportionment was more a political than a mathematical problem.

After the census of 1920 the Congress had to choose between two methods: Webster’s (WW) and the Huntington-Hill (HH). As the Congress failed to agree on any one method, no apportionment has been affected 1921. Fortunately, in 1931, the two methods produced the same distribution so that the vote has been postponed till 1941. At which time, the two methods disagree and the decision had to be made. The choice of the method would affected two states: Arkansas and Michigan. Under the HH method, Arkansas would receive 7 seats to Michigan’s 17. Under the WW method, Arkansas would receive 6 seats to Michigan’s 18. As it happened, Arkansas was a solidly Democratic state while Michigan usually voted Republican. Naturally, the discussion went along the party line. The arguments presented were quite fascinating.

Among others, J. Bayard Clark from North Carolina opined

The House would not want to let some mathematical formula result in an inequity or an injustice …

Ed Gossett from Texas put his colleagues at ease

We should not go into the intricate mathematical and geometrical formulas necessary to understand these various methods …

Eventually, a National Academy of Science committee was put in place that produced a report in favor of the HH method.

References

1. George G. Szpiro, Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present, p. 150

Years ago I came across a problem of flipping several items simultaneously:

There are 7 glasses on a table–all standing upside down. It is allowed to turn over any 4 of them in one move. Is it possible to reach a situation where all the glasses stand right side up.

The solution is rather obviously in the negative: at all times the number of the upright glasses is even and hence can’t be 7.

At the time of my first encounter with the problem, I wrote a Java simulation that worked for numbers other than 7 and 4 and left a remark to the effect that the problem is solvable if and only if the number of glasses to be inverted on a single move is odd. I did not include a proof and do not remember now if I even had one.

More recently, while perusing a popular problem collection by C. W. Trigg, I chanced on a related problem (#22):

It is desired to invert the entire set of N upright cups by a series of moves in each of which N-1 cups are turned over. Show that this can always be down if N is even, but never if N is odd.

The proof is simple. Every cup is assigned a number – either +1 or -1. For N-1 even, the product of all the the numbers associated with all the cups is invariant under any move. Since, for N odd, the product of the all-upright configuration is 1 whilst the product of the inverted configuration is -1; if so, the problem is unsolvable in this case.

For the case where N is even, observe that there are N combinations of N-1 terms out of N and each term appears exactly in N-1 such combinations. Importantly, N-1 is an odd number. It follows that applying all N moves associated with with N such combinations, we shall turn each of the cups exactly N-1 times, thus ending up with all the cups inverted the wrong side up.

This problem fits nicely into the generalization but the solution does not appear to be easily adaptable to a more general case. The upside of the situation is that I recovered a simply looking, nice problem with unknown solution. The downside was that my old writeup seemed to intimate otherwise. I decided it was the right time to patch up my old claim.

Thus the problem is this. There are N items that may be in one of two positions, say, up and down. A move consists in flipping M items simultaneously, M < N. Originally, all the items are in the up position. Is it possible with a series of moves and, if so when and how, bring all the items to the down position? Let’s call this a P(N, M) problem.

A couple of rather obvious observation are in order. If G = gcd(N, M), then P(N, M) is solvable if and only if P(N/G, M/G) is solvable, meaning that it is sufficient to consider only the problem for N and M mutually prime.

Second, we may assume that M < N < 2M. The first inequality is a natural requirement: one can’t flip more than a present number of items. The second inequality is a tidy-up condition. If N is too large, it is always possible to keep flipping groups of M distinct items until the number of the up items goes below 2M, forgetting from then on about the items that have just been turned over.

Proof →

References

1. D. Fomin, S. Genkin, I. Itenberg, Mathematical Circles (Russian Experience), AMS, 1996
2. C. W. Trigg, Mathematical Quickies, Dover, 1985, #22.

Proof

If M is even then, since gcd(N, M) = 1, N is odd. However the number of down items is always even.

Let {U, D}, U + D = N, denote a position with U up and D down items. Let T_{a, b}, a + b = M, designate a move which inverts a up and b down items. For T_{a, b} to be applicable to {U, D} one needs a ≤ U and b ≤ D. Assuming that,

Suppose first that N = 2n + 1 and M = 2m + 1. Then the following sequence of moves solves the problem:

Starting with the configuration {N, 0} these moves produce successively the following configurations:

For the second move to be applicable we need the inequality 2m + 1 > 3m – n + 1 to hold. This inequality is equivalent to n > m, which is a consequence of N > M.

The remaining case where N = 2n and M = 2m + 1 is more complex. Before we proceed, let’s record a couple of obvious properties of the T operators.

Lemma 1

1. T_{a, b}T_{b, a} = 1, the identity transform.
2. If T_{a, b}{U₁, D₁} = {U₂, D₂} then T_{a, b}{D₂, U₂} = {D₁, U₁}.

Also, for convenience, let R = T_{m, m+1} and S = T_{m+1, m}.

R{U, D} = {U + 1, D – 1} and S{U, D} = {U – 1, D + 1}.

In Cartesian coordinates, for a fixed N, all possible configurations lie on the diagonal U + D = N (shown for N = 14):

Under our assumptions, M < N < 2M, the first move T_{M, 0}{N, 0} = {N – M, M} always overshoots the midpoint {n, n} because M > n. There are now two possibilities: operator R may or may not be applicable to the new position {N – M, M}.

If it is, one application of R will move the configuration along the diagonal one step closer to the midpoint. This happens, for example, with N = 14 and M = 9. The step can be repeated until the midpoint is reached.

If it is not, as in case N = 14 and M = 11, the operator T_{U, M-U} will shorten the distance to the midpoint.

For M = 11, T_{3, 8}{3, 11} = {8, 6}. Let’s see how it works in general. Assume U < n < D and U < m. Then

T_{U, M-U}{U, D} = {M – U, D – M + 2U}.

What can be said about this move? First of all, it moves {U, D} in the direction of {n, n} because U < M – U, or, equivalently, U ≤ m. But we assumed that U < m. It follows that, if M – U < n, then {M – U, D – M + 2U} is indeed closer to {n, n} than {U, D}. On the other hand, if the move overshoots {n, n}, making M – U > n, then still
(M – U} – n < n – U for it is equivalent to M < 2n = N.

We could similarly handle the case where U > n and D < m. One way or another it is possible to move nearer to the midpoint {n, n}. We shall continue this process until it becomes possible to apply one of the operators R or S to move 1 step at a time to make sure that eventually we’ll get to the midpoint {n, n}. Once there, we first record the sequence of moves from the initial point {N, 0} and then apply them in reverse order, thus forming a palindromic sequence of moves from {N, 0} to {0, N}. (The palindromic sequence will work due to the second property in Lemma.)

Of course it is not necessary to use the one-step operators R and S; the sequence of moves may be shortened if several such moves are combined into one. I have only introduced them to make is clear that it is always possible to land on the midpoint: there is no way to pass it with 1 step moves. Let’s have a couple of examples.

N = 20, M = 13

We only need 4 moves: T_{13, 0}, T_{5, 8}, T_{5, 8}, T_{13, 0}. Here are the consecutive configurations: {20, 0}, {7, 13}, {10, 10}, {13, 7},
{0, 20}.

N = 20, M = 17

Now we need 8 eight moves: T_{17, 0}, T_{3, 14}, T_{11, 6}, T_{8, 9}, T_{8, 9}, T_{11, 6}, T_{3, 14}, T_{17, 0}. These generate a sequence of configurations: {20, 0}, {3, 17}, {14, 6}, {9, 11}, {10, 10}, {11, 9}, {6, 14}, {17, 3}, {0, 20}.

Find an integral arithmetic progrssion with an arbitrary large number of terms such that no term is a perfect rth power for r = 2, 3, …, n.

Trigg gives two solutions. One is trivial, with the first term a non-power and the difference 0. The second solution is by Azriel Rosenfeld. It is quite simple, a one-liner in fact, but by no means trivial.

References

1. C. W. Trigg, Mathematical Quickies, Dover, 1985, #64.

Solution

Observe that a power of an odd integer is odd, whereas a rth power (with r > 1) of an even integer is divisible by at least 4. It follows that the sequence {4k + 2} contains no integer powers.

Charles Lutwidge Dodgson – better known to broad public as Lewis Carroll – has developed an algorithm to calculate the exact date of Easter Sunday for every year until 2499. In this he bested the great Carl Friedrich Gauss who also found it a sufficiently important occupation. Gauss devised a formula that gave the correct date but only up to 1999. Beating Gauss by 500 years was a remarkable achievement were it not for a small glitch. Dodgson’s algorithm refused to work for the year 1954. Failing to find an explanation he had to admit that he “cannot in the least, account for this curious anomaly.” (George G. Szpiro, Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present, p. 102.)

A lot of things happened during that 1954 year. An absolutely unique event in the history of the mankind was a 8.5 pound meteorite crashing through the roof of Mrs. Elizabeth Hodges, Sylacauga, Alabama. The incident gave her a bad bruise (this is the first known modern case of a human being hit by a space rock).

Three ropes have been fastened to a horizontal plunk, tangled a little as if one tried to make a braid and, lastly, loosely attached to an auxiliary plank to keep them braided.

Down below there is a third plank. The task is to attach three additional ropes to the first ones at one end and to the third plank at the other. Is it possible to perform that feat so that when the provisional plank is removed the ropes come undone?

Solution →

Solution

Reflect the whole picture in the auxiliary plank. This will show how to attach the two sets of ropes. This is a fantastic exercise even for little kids.

This solution can be verified with real ropes, or with the shuttle puzzle.

References

1. C. W. Trigg, Mathematical Quickies, Dover, 1985, #39.

I found a remarkable talk given by Robert Lang pointed to at the Math Frolic! blog. Dr. Robert J. Lang is an American physicist who is also one of the foremost origami artists and theorists in the world. Among other achievementsm he is known for having proved the completeness of Huzita–Hatori axioms and developing paper folding algorithms. This is what his 16-minute 2008 TED Talk is about:

As often happens in math and art, Robert remarked, the pursuit of beautiful leads to practically useful discoveries. As an example, he helped design a folded of a solar battery that was to provide power to a deep space explaration craft. He concludes his talk by expressing a belief that sooner or later origami will be instrumental in saving human lives.

The formula for the sum of the consecutive cubes of integers is one of the most elegant in elementary mathematics:

Taking into account a better known formula for the sum of plain integers

the formula for cubes can be rewritten succinctly as

The sum of the cubes is a square of a triangular number.

There are general approaches that lead to summation formulas for other powers of integers, or, as they are called, power series. Here I’ll use a straightforward induction argument.

For n = 1, the identity is trivial: Assume it holds for and let

Thus, this proof by induction is reduced to establishing the following identity

Indeed, with a little effort, it could be verified that both sides are equal to

Now, as an application of the summation formula, let’s solve the following problem (C. W. Trigg, Mathematical Quickies, Dover, 1985, #51): Solve the equation in positive integers

Solution →

Adding 1 to both sides of the equation

gives

or, taking into account the summation formula for the cubes,

Taking the square root

with a unique and obvious solution

In a related post I have shown that Without resorting to this proof, I am going to show that

Let and Then

which gives us a third degree equation in : By direct verification is one of the roots of that equation. Factoring gives The second factor which is a quadratic polynomial is always positive because and, therefore has no real roots. However, is clearly real and is then the only real root of the cubic equation which is 1. Of necessity and we are done.

Reference

1. C. W. Trigg, Mathematical Quickies, Dover, 1985, #35

A human hand carries five fingers; two hands have ten of them. Undoubtedly, this fact is responsible for the universal adoption of the decimal system.

Children learn to count by counting fingers, first to 5 on one hand and then to 10 on two hands. However, there is a simple way to count to 10 with just 5 fingers of one hand and to 100 using both hands.

This is how:

one	two	three	four	five

six	seven	eight	nine

A folded fist may stand for 10 if you do not plan to use the second hand, or for 0 if you do:

	ten/zero

The second hand is used in the same manner but for counting 10s:

	ten	eleven

	twenty six	fifty five

George G. Szpiro, author of Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present is a mathematician and journalist living in Switzerland.

Numbers Rule focuses on key figures in the development of democracy and on the mathematics of voting, elections, and apportionment that they developed. Szpiro pays particular attention to the paradoxes that arise, and discusses them through examples,

wrote Steven J. Brams, New York University – himself an expert on democracy related mathematics.

The quality of Szpiro’s writing can be tasted at his recent op-ed at the History News Network.

This particular article deals with the history of the problem of apportionment. In the article, the author highlights what became known as the Alabama and Population paradoxes. Szpiro lucidly explains how these and other paradoxes arise due to the rounding errors, inevitable evil of the process of dividing a limited number of seats among the representatives of such a big country as the USA. He makes it clear that mathematical tool set is not powerful enough to resolve the problems of democratic representation.

Towards the end of the article, Szpiro suggests – I believe rather light heartedly – to resolve the problem of paradoxes and the constitutionally mandated fairness of the representation by avoiding rounding (in all possible ways) and by simply assigning to the districts a fractional number of representatives depending on the size of the population. This is rather obviously an impractical solution. The House will have to grow (by 25 representatives in Szpiro’s estimate). Each new representative will be entitled on a full size staff. But budgetary considerations aside, presently the voting goes sometimes along the party lines and sometimes by creating coalitions. Some representatives have more power than others – due to their caring of important committees – and thus are better positioned to promote their (or their home states’) interests. So it is not exactly the case of 1 representative, 1 vote, anyway. Fractional representation will, in all likelihood, only deepen the divide. And of course it will create additional conflicts and power struggles. A state with 20.75 representatives will send 21 persons to serve in the House. Will there be anyone to carry the .75 power or will it be applied on a rotation basis?

There are just a couple of concerns that fractional representation will lead too. This is probably where mathematics should draw a line. All the power of mathematics notwithstanding, the representation will never be 100% fair. Politics may be a dirty job; the history teachers us that some dirt is necessary to make this job functional.

Szpiro’s article has been hightlighted at the Princeton University Press blog and elsewhere on the web.