University of Padova
University of Pisa
Election time is approaching in the extremely indebted country of Taxonia. The two main parties competing for the elections know that the winner will have to increase the taxation for the coming year.
The Steady party wants to make things clear and explains to the population during the campaign that, in case they will win, a tax rate of 50% will be applied to personal incomes.
The Varying party claims that this is not needed and every person will be applied a tax rate determined by her/his problem solving ability. More precisely, the procedure for establishing the tax rate will work as follows: each person is given 10 tokens that s/he has to arranged on a table. Then the tax collector can draw a straight segment and collect all the tokens whose centre is crossed by such a segment: the amount of tokens collected will determine the percentage of taxes, each token contributing a 10%. However, to ensure that a mininum tax rate of 30% will be applied, each person has to guarantee that a third token lies along the line connecting any two tokens. For instance, the conguration in which all tokens are arranged in a circle as follows
is not admitted since no straight line would cross the centres of more than two tokens.
Q. If you were to vote for the party that allows you to pay less taxes, which one will you choose?
Hint. The constraint imposed by the Varying party is more demanding than one may expect. Try to prove that given any nite set S of points on the plane, either they all lie on the same line or there is at least one line crossing exactly two points of X.
Solution. Indeed, the wiser although not obvious choice is to vote for the Steady party. The tax scheme proposed by the Varying party, as it often happens, hides the crude reality under the carpet. As suggested by the hint, the crux is that, given any nite set S of points on the plane, either they all lie on the same line or there is at least one line crossing exactly two points of X.
This can be proved by contradiction, as follows. Assume that each line connecting two points in X contains at least a third point from X. Consider all the lines connecting pairs of points in X and the distances of the points in X from such lines. Take the point p in X and line L realising the least non-zero distance h.
By hypothesis line L crosses at least three points in X, therefore at least two of them are on the same side with respect to h. Assume, without loss of generality, that there are two points q and r to the left of h, as in the picture below. This accounts also for the case where r lies at the intersection between L and h.
Now, consider the line L’ though p and q. The distance h’ of r from L’ is smaller than h, contradicting with the minimality of h.
Therefore, for tax payers, the only way of ensuring that there are at least three tokens on each line will be to put all tokens in a straight line, thus allowing the tax collector to take any percentage of their income.
Notes. This problem was originally proposed by Sylvester in the Educational Times, Mathematical Question 11851, vol. 46 (383), 1893. The question on the ordinary real plane remained unanswered for forty years. Revived by Erdös in 1943, the problem was solved by Grunwald in 1944. The beautifully short proof above is due to Leroy Milton Kelly (1948).
More details in: “A Problem of Collinear Points, H. S. M. Coxeter, The American Mathematical Monthly, vol. 55 (1), 1948.”