Tough puzzles requiring mathematical skill
W I N
I   O
N O W
Mathematical Puzzles
The Contest Center
59 DeGarmo Hills Road
Wappingers Falls, NY 12590
W I N
I   O
N O W


All of the mathematical puzzles on this webpage are very challenging.
We will post the names of anyone who solves them.
-
* indicates I have only a partial solution.
** indicates I do not have a solution.



** Rubin's 3 Powers Conjecture #1
       Prove or disprove that every integer can be expressed as a sum of 3 distinct powers,   xa + yb + zc   where   x, y, z, a, b, c   are all integers, and   1<a<b<c.
       For a table showing how each of the integers from -100 to +100 can be expressed in this form CLICK HERE. For a table showing how each of the integers from -8000 to +8000 can be expressed in this form CLICK HERE.


** Rubin's 3 Powers Conjecture #2
       Prove or disprove that all but a finite number of positive integers can be expressed as a sum of 3 powers,   xa + yb + zc   where   x, y, z, a, b, c   are all positive integers, and   1<a<b<c.


** Bell's Triangle (Contributed by Naim Uygun)
       The Bell triangle, also called Aitken's array or the Peirce triangle, is a triangular arrangement of integers in which the top row has a single 1. Each subsequent row begins with the last number of the previous row, and each additional number in the row is the sum of the number to the left and the number above left. For example, on the fourth row the number 7 is the sum of the number 5 to its left and the number 2 above left. 
 
                    1
                 1     2
              2     3     5
           5     7    10    15
       15    20    27    37    52
    52    67    87   114   151   203
203   255   322   409   523   674   877
. . .
The sums of the terms on the first, second and fifth rows, namely 1, 3 and 151, are palindromic. Do any other rows have palindromic sums? Do any rows beyond the first have sums that are squares?


** Mixing Program
       Let N be the sequence of natural numbers 1,2,3, ..., n. A mixing program on N is a sequence of pairwise steps aibi for i = 1,2,...,k, where Step i indicates that the number in the ai position should be swapped with the number in the bi position with probability 1/2. Thus the mixing program 12 applied to the sequence 1,2,3 results in either 1,2,3 or 2,1,3 with probability .5, while the other 4 permutations have probability 0.
       After applying the mixing program, each of the n! permutations will have a specific probability. Call the sequence well-mixed if the most-probable permutation is at most 1% more likely than the least-probable permutation. How many steps are required for each value of n?


Two Trains
       Two trains are traveling on parallel east-west tracks at a speed of 0.99c. Five observers sychronize their stopwatches, and then take positions where they can see the point where the trains will cross. At the instant when the 5 observers get in position the two trains are 1 kilometer apart. The observers will stop their watches at the instant they perceive the two trains to pass nose-to-nose.
       E stands on the front of the eastbound train, W stands on the rear of the westbound train and observes the passing of the other train through a mirror mounted at a 45° angle at the front of the westbound train, M stands in the middle, halfway between the tracks, P stands on a platform 100 meters directly overhead, and S stands to the side, one kilometer directly north of the spot. Each train is 500 meters long. Assume that the time for light to travel from one track to the other is negligible.
       When the observers meet again, how will their watches compare?

Answers have been submitted by:   Ahmet Saracoglu, Paul Cleary


Heronian Triangles (with Paul Cleary)
       Do there exist two Heronian triangles a,b,c and a,b,d such that the area of one is an integer multiple n>1 of the area of the other?

Solved by:   P.M.A. Hakeem, Arthur Vause, Naim Uygun, Mark Rickert, Ender Aktulga, Ionut-Zaharia Chirila


26 Numbers (Contributed by Paul Cleary)
       There are infinitely many sets of 26 real numbers where their sum is 200 and the sum of their squares is S. The difference between the smallest and largest of the numbers in these sets is 60/13. What is the value of S?

Solved by:   Arthur Vause


** Plague
       A vast cloud of mosquitoes has been moving steadily towards your area. These mosquitoes are immune to all known insecticides and insect repellants. The mosquitoes carry a virus which will infect 1 out of every 100 people. Within 4 hours of arrival the mosquitoes will reach every part of your area, and within 6 hours everyone will be exposed to the virus. A person who has been infected will know this within minutes. Everyone else has natural immunity, and will not become infected, even if bitten multiple times.
       To cope with the virus, your area has been divided into 10 districts, each with 1,000,000 people. Each district has a designated hospital where everyone with the disease must go for treatment. 100,000 doses of the cure have been stockpiled in 20 special coolers at the central airport, and 20 planes are ready to carry these coolers to the 10 treatment centers.
       Everyone has been alerted. Hundreds of buses and trains are standing ready. Hundreds of doctors and nurses are available.
       Within 8 hours every infected person will reach the hospitals and within 10 hours you will have an exact count of the number of patients at each hospital. Within 12 hours the planes will reach their destinations. Within 14 hours the coolers with the drugs will be at the hospitals and ready for injection. That leaves 2 hours to inject and save the patients.
       Since every person has exactly 1 chance in 100 of contracting the disease, the number of patients at each center will be different. Therefore it would be wise to load some of the coolers with more than 5000 doses, and some with less, so that fewer doses can be sent to districts with fewer cases, and more doses to districts with more cases. This must be done now, before the mosquitoes arrive.
       It is your job to determine exactly how many doses should be in each cooler in order to save the greatest possible number of lives.
       This problem will be judged in a special way.   Click here for the specific rules.

Solved by:   P.M.A. Hakeem


** 4 Squares
       Prove that every whole number can be expressed as the sum of 4 distinct squares, except for numbers of the form 4ns where s is any number in the set   S = {1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 15, 17, 18, 19, 22, 23, 25, 27, 31, 33, 34, 37, 43, 47, 55, 58, 67, 73, 82, 97, 103}


** Squares on a Cube
       Suppose that a number is written onto each of the 6 faces of a cube. Is it possible for all 6 of the numbers to be squares, and for the sum of the 3 numbers surrounding each of the 6 vertices to be a square? Yes, if the number on the top and bottom faces is 1, and the other 4 faces have 4, then all 6 sums are 9. Is it possible without 2 adjacent faces having the same square? Yes, if the top and bottom faces have 1, the front and back have 16, and the left and right have 64, then all 6 sums are 81. Is it possible without any faces having the same square?


Stockholders
       The Foodlemyer Corporation has 12 stockholders. Whenever a major decision is needed, they vote, each person getting one vote for each share of stock owned. What is the smallest total number of shares possible so that no vote can ever be tied (regardless of how many stockholders participate), and no group of stockholders can ever outvote a larger group?

Solved by:   Lee Morgenstern, P.M.A. Hakeem, Arthur Vause, Mark Rickert


Secret
       Two people have found that they must communicate important secret messages with each other. However, they have made no arrangements in advance. Their only channel for communicating is by public telephone lines that can be assumed to be passively bugged. That is, enemies may be listening to and recording all of the messages in both directions, including all discussions they may have concerning how the secret messages may be concealed, but these enemies cannot alter the messages, insert their own messages, or prevent any messages from getting through.
       Both of the people know some mathematics, but neither one knows much about cryptography, and certainly nothing that was developed after World War I. They both have older model personal computers with modems, and both have a moderate degree of programming skill. The enemy, however, can be assumed to have massive, unlimited computing power and expertise. The messages are vital, but not urgent, so they can take several hours per message, if necessary.
       How can they arrange to send their messages securely?


** Copycats Club
       The Copycats Club has N members. Whenever a decision is needed, each member votes according to the votes of K other members, with 1 < K < N-1. That is, each member has selected K other members to copy, with K odd. (Assume that the selection is random, with each member having an equal probability of selecting and being selected by any other member.) Each member will vote for or against the motion according to the majority of those k selected members.
       On the first ballot the members vote independently, with probability P, for the motion. On all subsequent ballots they vote as described above. A unanimous vote is required to pass or defeat any motion. As a function of N, K and P, what is the probability that a given motion will pass? How many ballots will be needed?


** 3 Cubes
       Prove or disprove that every integer can be expressed as either the sum of 3 cubes, or the sum of 3 cubes + 4. Here "cube" means the cube of any integer. (For example, 11 can be expressed as 33+(-2)3+(-2)3, which is 27-8-8, while 14 can be expressed as 23+13+13+4, which is 8+1+1+4.)


** Paving
       Paving contractors estimate the areas of quadrilateral sectors by measuring the distance between the midpoints of opposite edges and multiplying. What are the maximum error and the expected error of this method? [Assume convex quadrilaterals, with no vertex angle less than 45°.]

Solved by:   James Wan


The Jewel Thief (contributed by Sudipta Das)
       The famous Kohinoor diamond has been put on display in a certain museum. The museum authorities have installed an electronic lock which has N buttons, each with a different symbol. To open the lock one must select the correct combination of the symbols, irrespective of the order in which the buttons are pressed. When each button is pressed it lights up. If the correct combination is lit, the lock immediately opens. On the side of the lock is a reset button which will turn off all the lights.
       The Jewel Thief visited the museum and noted down all the symbols. That night, he returned to steal the precious gem. Due to shortage of time, he must open the lock as fast as possible.
       What is the minimum number of presses needed to guarantee that the lock will open (including both symbols and reset)? Assume that all the lights are off when he arrives.

Solved by:   Nick McGrath, Toby Gottfried, P.M.A. Hakeem


4 Merchants
       Four merchants have been granted licenses to sell a certain line of products in Foodleshire, a flat perfectly square county in Ingland. Since they will sell exactly the same products at exactly the same prices, customers, who are uniformly distributed in the shire, will go to the nearest store. Successive merchants will place their stores so that they get the most selling territory.
       You are the first to establish a store. Where should you build it? (To avoid the problem of arbitrarily small distances, assume that Foodleshire is exactly 1000 furlongs square, and that stores may be placed only at integer coordinates. Also, assume that all 4 merchants know the order in which they will build their 4 stores.)

Solved by:   P.M.A. Hakeem


** Swiss Cheese
       Hawkeye Foodlemyer is firing a rifle at a paper target 500m away. The target is 10cm square, and each bullet hole is circular, 1cm in diameter. The bullet holes are uniformly distributed in the target area, and none extend beyond the boundary.
       (A) How many bullets must be fired before the chance that 2 bullet holes overlap exceeds 0.5? (B) How many bullets must be fired before the chance that the next bullet hole will overlap an existing hole exceeds 0.5?

Solved by:   Paul Cleary


Eight Pencils
       Arrange eight pencils so that each one touches every other one. (Use straight round wooden pencils, i.e., thin long rigid circular cylinders of equal diameter.)
       [A version of this puzzle was orginally published in Martin Gardner's Mathematical Recreations in Scientific American, I think in 1957. Gardner reported that 6 pencils was the most possible, however a few years later he published a solution with 7 pencils. We expect more from the fans of this website.]

Solved by:   Gilles Ravat, Carlos Rivera


Latin Squares
       A Latin Square of order N is an NxN matrix where the elements in each row and each column are the integers from 1 to N in some order. Two Latin squares are considered equivalent if one can be transformed into the other by any combination of permuting the rows, permuting the columns, or permuting the integers 1 to N. For example, these are two non-equivalent Latin Squares of order 4.
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

       Describe an efficient procedure for determining whether 2 Latin Squares are equivalent.


Thunderstorm
       The time between seeing a lightning flash and hearing the resulting thunder gives an accurate estimate of the distance to its location. During one storm a meteorologist observes 29 such flashes, and calculates the distances in miles as follows:
 
6.02
3.01
0.69
3.38
2.01
4.69 		3.54
3.67
3.67
4.55
5.79
3.72 		1.05
3.73
3.98
7.28
2.10
2.90 		6.95
6.18
7.20
4.89
6.60
2.53 		2.09
1.30
1.81
4.75
6.91
 

Assume that the cloud is circular, is not moving, and that the lightning strikes are uniformly distributed through the cloud. Determine the diameter of the cloud.

Solved by:   Nick McGrath


No Solution
       Prove that the equation   x4 + y4 = z2   has no solutions in positive integers.

Solved by:   Pierre de Fermat, Ritwik Chaudhuri, Rory Kulz, Sudipta Das, Ionut-Zaharia Chirila, Kaustuv Sengupta


Sum of Divisors
       Find a cube greater than 1 such that the sum of its divisors is a cube. for example, the divisors of 12 are 1, 2, 3, 4, 6 and 12.

Solved by:   Michael Quist, Mark Rickert, Claudio Meller, Arthur Vause, Paul Cleary, Ionut-Zaharia Chirila, Kaustuv Sengupta


The Clocks of Klotz and Klutz
       In the twin Swiss towns of Klotz and Klutz the people are proud of the wooden clocks they still make entirely by hand. Each Master in the Clock Guild wears a small clock on a neck chain. At noon each day the Masters all meet in Time Square where they pair off randomly to perform the clock matching ceremony.
       In the town of Klotz, each Master sets the clock to the time shown on the other's clock. In the town of Klutz, the two Masters set their clocks to the average of the times shown on their clocks.
       At the start of each year all of the Masters set their clocks according to the Great Clock in the city hall tower, which keeps perfect time. At the end of the year, they compare their clocks to the Great Clock. Anyone whose clock is more than 1 hour off is expelled from the Guild, and the leading apprentices are promoted to the rank of Master, so that each Guild always has 100 Masters.
       All of the clocks run at constant speed, which may be anywhere from 2 minutes per day slow to 2 minutes per day fast, uniformly. In which town will there be the most expulsions? If a town could modify the ceremony so that when A met B, A's clock would be set to rA+(1-r)B, and B's would be set to rB+(1-r)A, what value of r would yield the fewest expulsions?

Solved by:   Nick McGrath, Ricardo Faria


Sequence
       Let p(x) be a real-valued function such that p(x) is a positive integer whenever x is a positive integer. Let q(x) be a real-valued function which is positive whenever x is positive. Assume that there exist positive real values, A, B, a, b, c such that p(x) < Axa and q(x) < Bxb for all x > c. Find a necessary and sufficient condition for the existence of a sequence Si of positive real numbers satisfying
       S1 = 1
       Sn = SUMi=1,p(n) q(Si)        for   n = 2, 3, 4, ...


** Half an Interval
       When I was taking Measure Theory back in college, the professor assigned the following problem on a take-home exam:
       Let L(S) denote the Lebesgue measure of a measurable subset S of the real line R. Find a subset H of the unit interval [0,1] such that for any interval I=[a,b] in [0,1] the intersection H∩I is measurable and L(H∩I)=L(I)/2.
       Either (a) solve this problem, or (b) prove that no such subset H can exist.

Note: The sign ∩, resembling an inverted capital U, means the intersection of two sets. It does not display correctly on some browsers.

Solved by:   Michael Quist, Paul Budney


Sums of Polynomials
       Let pi(x) = x2+mix+ni for i=1,2,3,4 be four given polynomials with mi and ni integers, and m1 through m4 not all odd. Show that there is an integer N such that any integer n > N can be expressed as the sum p1(a1)+p2(a2)+p3(a3)+p4(a4) for some integers a1 through a4.

Solved by:   Arthur Vause


** Sums of Polynomials #2
       Let pi(x) for i=1,2,...,n+1 be polynomials of degree at most n with rational coefficients such that
(1) pi(x) is an integer whenever x is an integer,
(2) at least one of pi(x) has a positive high-order coefficient, or has odd degree,
(3) given any integers 0<a<m there exist integers ai such that SUM(pi(ai): i=1,2,...,n+1) ≡ a (mod m).
       Show that there is an integer N, such that any integer S > N can be expressed as SUM(pi(si): i=1,2,...,n+1) for some integers si.


* Pi
       This problem has been moved to its own webpage. Click here for the Pi Competition.

Send email Send us an email to submit answers to these puzzles, to report progress towards solution, to ask for help, or to submit new puzzles.
Be sure to change the $ to an @ in our email address.


Quick Links
Interactive Online Games
<<< PREV HOME MAP NEXT >>>


© Copyright 2024 The Contest Center