One can show that the largest number in the quadruple must have decreased after at most four iterations. Consider the cases corresponding to the possible patterns of zeroes.
In general, we saw that if we restrict the integers in the first step to zeroes and ones, then f is a linear transformation (modulo 2). Now, it is easy to show that the applying the transformation four times results in the zero vector. Then, one can use this to think about the parities in the general case, and show that the number of iterations needed is O(log n).
Generalizations to input vectors of 8, 16, 32, ..., integers is now pretty easy, as is seeing why the number of entries cannot have an odd factor greater than one.
Was this a fluke? Try starting with some other 4-digit number -- avoid multiples of 1111.
Are there nice results for 6-digit numbers? (Look, e.g., at the results of starting from each of these three numbers: 420876, 549945, 631764.)
5-digits numbers? (Look at the three numbers 53955, 61974, 62964.)
For the proof in the 4-digit case, consider a 4-digit integer abcd (representing 1000a+100b+10c+d), where a ≥ b ≥ c ≥ d and a > d. Now, the first iterate gives 999(a-d) + 90(b-c), and there are only 9 choices for a-d and 10 for b-c. Hence, after the first iteration, the result is one of the numbers:
1998, 2088, 2178, 2268, 2358, 2448, 2538, 2628, 2718, 2808,
2997, 3087, 3177, 3267, 3357, 3447, 3537, 3627, 3717, 3807,
3996, 4086, 4176, 4266, 4356, 4446, 4536, 4626, 4716, 4806,
4995, 5085, 5175, 5265, 5355, 5445, 5535, 5625, 5715, 5805,
5994, 6084, 6174, 6264, 6354, 6444, 6534, 6624, 6714, 6804,
6993, 7083, 7173, 7263, 7353, 7443, 7533, 7623, 7713, 7803,
7992, 8082, 8172, 8262, 8352, 8442, 8532, 8622, 8712, 8802,
8991, 9081, 9171, 9261, 9351, 9441, 9531, 9621, 9711, 9801.
However, not all of these give distinct 4-digit integers when we sort the digits. In fact, only 30 cases result:
8820, 8730, 8721, 8640, 8622, 8550, 8532, 8442, 7731, 7641,
7632, 7551, 7533, 7443, 6642, 6552, 6543, 6444, 5553, 5544.
After two iterations and a subsequent sorting of digits, the 17 results are:
8532, 7731, 7641, 7443, 6642, 6552, 6543, 5553.
Subsequent rounds, in shorthand, are:
9972 → 7731 → 6543 → 8730 → 8532 → 7641
6552 → 9963 → 6642 → 7641
8721 → 7443 → 9963 → 6642 → 7641
9810 → 9621 → 8532 → 7641
If a bus containing a countably-infinite number of people arrives when the hotel is already full, show that the new people can be accommodated.
If a countably-infinite number of busses, each containing a countably-infinite number of people arrives, show that the new people can all be accommodated.
(Don't ask me to find you a countably infinite number of people.)
Prove that for k=2 and any positive integer value m0, there is an index N such that mN is in the set {1,4}.
Examine this problem for some other positive integer values of k.
One obvious starting point for this question and the next one:
If the integer n has exactly s digits, then fk(s) ≤ 9ks. Thus, if 9ks < 10s, then fk(n) < n. For a fixed value of k ≥ 2, consider the function g(s) = 9ks-10s. Prove that g'(s) has exactly one zero and thus g(s) has at most two zeroes. Note also, g(0) < 0, g(1) > 0, and g(s) goes to -∞ as s goes to ∞. For any particular k, we need only identify where the function becomes negative, after s = 1. Hence, if g(t) > 0 and g(t+1) < 0, then fk shrinks numbers with t+1 or more digits. If we're looking for possible cycles, then we need only look at numbers with t digits or fewer.
If n has at least four digits, f2(n) < n.
Now, if n has three digits, f2(n) ≤ 243.
If n ≤ 243, then f2(n) ≤ 22+92+92 = 162.
We need deal with no number larger than 162.
If n has at least five digits, f3(n) < n.
If n ≤ 9999, then f3(n) ≤ 934 = 2916.
If n ≤ 2916, then f3(n) ≤ 23+933 = 2195.
We need deal with no number larger than 2195.
You can use the hint and finish with some calculations. The possible forms are n = a999, n = ba99, n = cba9, n = dcba, where a ≠ 9. The first three forms are easily shown to be impossible, and in the last form, a = 0 and d ≤ 2. Thus, f3(dcb0) ≤ 23+923 = 1466, and d3+c3+b3 is a multiple of 10. If d = 0, then c + b = 10, and there are only ten choices to try. If d = 1, there are also limited choices.
Of course, a computer can do it very quickly once you've limited things to at most four digits.
10 12 13 9 11 9 11 12 8 10 13 15 16 12 14 11 13 14 10 12 8 10 11 7 9
13 11 10 8 7 14 17 13 12 11 15 19 12 7 9 16 20 18 17 16 14 13 16 10 12
Hint: No transversal of the given square can have a sum larger than transversals of the square depicted below.
13 17 11 8 7 17 21 15 12 11 15 19 13 10 9 22 26 20 17 16 18 22 16 13 12
To find a dominating square, such as the one above, involves some detailed calculations, but there is a nice primal-dual algorithm (due to Kuhn and Menkres) which will do the work. One can also use standard linear programming techniques.
My students pointed out that this old chestnut appeared in the movie Die Hard with a Vengeance.
- Hint: Suppose the parabola were given by y=kx2, and consider a line segment M
with endpoints
(a,ka2) and (b,kb2) on the parabola, with a≠b.
The slope of M is (kb2-ka2)/(b-a)=k(b+a).
The midpoint of M has x-co-ordinate (b+a)/2, which depends only on the
parabola chosen and the slope of the M. What can you say about the midpoints of two parallel chords?
(Is it wrong to use co-ordinatization to help prove that a straightedge and compass construction is valid?)
(i) For some k, α={a1,a2,...,ak}, with 1≤a1<a2<...<ak≤n (we specifically allow k=0, k=1); and
(ii) ai and ai+1 have different parity if 1≤i<k.
For example, for n=4, there are the following possibilities for α: { }, {1}, {2}, {3}, {4}, {1,2}, {1,4}, {2,3}, {3,4}, {1,2,3}, {2,3,4}, {1,2,3,4}, for a total of twelve allowable sets.
How many possibilities are there for α, for each positive integer n?
Let's call such subsets alternating parity subsets. Let βn denote the number of alternating parity subsets from the set {1,2,...,n}, let fn denote the number of alternating parity subsets from the set {1,2,...,n} and whose largest element is even, and let gn denote the number of alternating parity subsets from the set {1,2,...,n} and whose largest element is odd.
Note that βn = fn + gn + 1; the empty set is counted by neither fn nor gn.
Now, if n=2k, then every set S counted by βn-1 contributes one to the value of fn as follows, if the largest element of S is even, then S is counted by fn, and if S is empty, or if the largest element of S is odd, then S union {n} is counted by fn. Hence, f2k = β2k-1. Also, g2k = g2k-1.
When n=2k+1, we deduce: g2k+1 = β2k-1 and f2k+1 = f2k.
These five equations should help you generate some values for (fn,gn,βn), and then you can try to make a conjecture as to the solution:
-
βn = fn + gn + 1;
f2k = β2k-1;
f2k+1 = f2k;
g2k = g2k-1; and
g2k+1 = β2k-1.
| n | gn | gn | βn |
| 1 | 0 | 1 | 2 |
| 2 | 2 | 1 | 4 |
| 3 | 2 | 4 | 7 |
| 4 | 7 | 4 | 12 |
| 5 | 7 | 12 | 20 |
| 6 | 20 | 12 | 33 |
Unfortunately, treasure hunters who have found the island discovered that the gallows has long since vanished. However, the oak and the pine are still there, in the same field. Can you find the treasure? Can you do it using straightedge and compass only?
1The exact location has been changed, otherwise somebody else might get to the treasure first.
2The names of the trees has been changed, so that even locating the island will not help in finding the treasure.
As discussed in class, there can be no such integer greater than 54. For example, a 2-digit number when cubed has at most 6 digits, and thus has cube-digit-sum at most 54. A k-digit number when cubed has at most 3k digits and thus has cube-digit-sum at most 27k, which is smaller than 10k-1 for k ≥ 3.
A computer run with 1 ≤ n ≤ 54 shows us the following examples: 1,8,17,18,26,27.
Solution.
A composite integer m with the property that m divides nm-n, for every integer n, is called an absolute psuedoprime or a Carmichael number. Other examples are: 2821, 10585, 15841.
Discuss the generalization to coins of values a units and b units. (ab-a-b)
Want something much harder? If a, b, c, are positive integers, what is the largest integer n that you cannot write as a non-negative integral linear combination of a, b, c?
On the first pass, he turned every lock, opening them all;
On the second pass he turned every second lock, beginning with the second, locking the even numbered cells;
On the third pass he turned every third lock, beginning with the third, locking cells 3,9,15,... and opening cells 6,12,18,...
What cells will be open at the end of the procedure, allowing those prisoners to leave?
Hint: If you think of the points A,B,C as being fixed, so that the line segment AC is fixed, then the triangle ABC has a fixed area, but the triangle CDA has an area that depends on x. For what position of the line segment CD is the area of the triangle CDA maximized?
Solution
Pictures
Prove. If one j-sorts a k-ordered list, the result is a list which is both k-ordered and j-ordered.
In particular, if a list is 3-ordered and 2-ordered, no entry is more than one space from where it belongs.
(The number of elements in S is approximately (log2n)(log3n).)
One nice thing about this approach is that it gives a reasonably fast parallel algorithm for sorting.
1 15 14 4 10 6 7 9 8 10 11 5 13 3 2 16
As a result, if p is prime, then p divides n p-n.
(We've already shown that 561 divides n561-n, for every integer n, but 561 is not prime.)
| x2+y2 x y 1 |
| a2+b2 a b 1 | = 0.
| c2+d2 c d 1 |
| e2+f2 e f 1 |
It is possible to place two checkers on the board, so that when one jumps the other, there is now a checker with y-co-ordinate +1. For example, place the two checkers at (0,0) and (0,-1). The checker at (0,-1) jumps the checker at (0,0), removing it, and lands at (0,1).
Similarly, one can attain a position with y-co-ordinate +2, by starting at (0,0), (0,-1), (-1,0), and (-2,0).
Eight properly placed checkers allow one to get to the third level, and twenty allow one to get to fourth level.
How many are needed to get to level five?
Solution.
Try the same problem with the straight-tromino. Which cells can be left uncovered?
|
|
These two are pictures of two complementary partitions. (One can be rotated and flipped on to the other.) A partition is self-complementary if its complement is itself. For example, the number 17 can written as a self-complementary partition in 5 ways: 9+1+1+1+1+1+1+1+1+1 = 7+3+3+1+1+1+1 = 6+4+3+2+1+1 = 5+5+3+2+2 = 5+4+4+3+1. The number 17 can also be written as the sum of odd distinct positive integers in 5 ways: 17 = 13+3+1 = 11+5+1 = 9+7+1 = 9+5+3. Coincidence?
(Basic rules for chess can be found at http://www.uschess.org/beginners/letsplay.html.)
| BR | BB | ||||||
| WB | |||||||
| BK |
There is a simple strategy to win this game.
(i) Write each of the numbers in binary, and place these numbers so that the units columns are aligned.
(ii) If any column sums to an odd number, you can replace one of the binary numbers by a smaller number so that the columns sums are all even. This tells you your move.
(iii) If each column (units, twos, fours, eights, etc.) sums to an even number, you should simply make a small random move, and hope that your opponent does not know how to win. He is in a position to do so.
Verify that this is a winning strategy.
(Harder: If you want to go first, what move will you make?)
|
|
|
|
|
|
|
|
|
(Harder If you want to go first, what is your move?)
{1,2,3,4,6,8,9,12,18,24,36,72}, {4,8,9,12,18,24,36,72}, {4,8,12,18,24,36,72}, {12,18,24,36,72}, {18,24,36,72}, {24,36,72}, {24,72}, {72}.
Reference link.
"Four," said the professor, "and all of their ages are different positive integers, but total to less than eighteen."
This leaves a finite number of cases to examine (hint), it was not enough information for the student to decipher their ages, so he asked for the product of their ages.
"The same as the number on my house," said the professor.
Having narrowed the list further, but still baffled, the student asked if the youngest one had her second birthday yet, and was rewarded with an answer.
"Now I can tell you their ages," beamed the student.
You can too.
| WB | WK | WR | |||||
| BR | WB | ||||||
| WR | |||||||
| BB | BP | BP | |||||
| WP | BK | WP | |||||
| BP | WP | BP | |||||
| WP | WP | WP | |||||
| WN | WN |
I got this problem from a Martin Gardner book. The Sun-Sentinel today (April 13, 2003), on page 8D, credits the problem to Karl Faber.
Now I — even I — would celebrate
In rhymes unapt the great
Immortal Syracusan rivaled nevermore,
Who in his wondrous lore,
Passed on before,
Left men his guidance
How to circles mensurate.
(I don't know how to do it without a computer, but properly formulating the method leads to not having to store any significant fraction of the digits of 1000000!)
- Exactly one statement on this list is false.
- Exactly two statements on this list are false.
- Exactly three statements on this list are false.
- Exactly four statements on this list are false.
- Exactly five statements on this list are false.
- Exactly six statements on this list are false.
- Exactly seven statements on this list are false.
- Exactly eight statements on this list are false.
- Exactly nine statements on this list are false.
- Exactly ten statements on this list are false.
After all the handshakes were over, I asked each person, including my wife, how many hands he or she had shaken. To my surprise, each gave a different answer. How many hands did my wife shake?
For k > 0, (3+4i)k = (3-i)k = 3-i (mod 5). 'Nuff said?
Note that p = (3+4i)/5 is in S. Then, pk is in S, for k integral, and S is infinite. Now, let q be the integer part of 2π/α, where α = arctan(4/3). One of 2π-qα or (q+1)α-2π is less than α/2. An obvious recurrence allows us to generate a point in S with argument arbitrarily small, but non-zero. The rest is easy.
If A(a,b) and C(c,d) are points with a,b,c,d in some field F, then the midpoint of the line segment AC also has both of its coördinates in F. The slope of the line segment AC is in F. The slope of any line perpendicular to line segment AC is also in F, so the perpendicular bisector of AC is a line y = mx + k, with m,k in F. The intersection of any two such lines results in a point with both coördinates in F.
(b) Supppose that there are three points with both co-ordinates algebraic on a circle. Show that the center of the circle has both co-ordinates algebraic.
(c) Can a circle (of positive radius) in the plane have all of its points having both co-ordinates rational? Both co-ordinates algebraic?
(d) Show that there is a point in the plane, and a family of circles, C1, C2, C3, ..., such that Ci contains exactly i lattice points in its interior.
Can you find a point P such that no circle centered at P has more than one point with both coördinates rational?
(a) White to mate in three.
(b) Remove the white knight. Now White to mate in four.
(c) Remove the white knight and the white pawn at KR2. Now White to mate in five.
(d) Remove the white rook (only). Now White to mate in six.
| WR | |||||||
| BP | |||||||
| WK | BK | ||||||
| BP | |||||||
| BB | WP | WP | |||||
| WN |
Solutions
A caterpillar is a tree T with a property that the removal of the end-vertices of T results in a path. You could draw one by drawing a path (which we will call the spine), say with vertices 1,2,3,4,5,...,n, so that vertex i is joined to vertex i+1, for 1≤i<n. Then, add k1 edges from vertex 1 to k1 new vertices, add k2 edges from vertex 2 to k2 new vertices (disjoint from those for vertex 1) , add k3 edges from vertex 3 to k3 new vertices (disjoint from those for vertices 1,2) , etc. Perhaps we should call this the caterpillar [k1,k2,...,kn]. If you've drawn the picture as specified, it looks a little like a caterpillar. Similarly, we could refer to a collection of caterpillars, by listing the caterpillars in the collection, so [[1,2,3],[4,3],[3,2,1]] is isomorphic to the graph consisting of two copies of the caterpillar [1,2,3] and one copy of the caterpillar [3,4].
The game goes as follows: Start with a mutually agreed upon caterpillar. Now, two people take turns. At each turn one of the players removes the edges of a path. The person who takes the last edge wins.
Discuss the winning strategy for the initial caterpillar [j,k].
More Challenging problem: Discuss the winning strategy for the initial caterpillar [j,k,m].
You can see what the next question would be -- and we're soon at the level which might be good for an M.S. Thesis.
Under what conditions is taking the spine, possibly with a leg at the first vertex and/or the last vertex, a winning move?
Consider the problem for other sizes, too. Also, toroidal boards, etc.
Yes, I actually did this one with two bills. Don't try it -- big companies cash whatever you send them.
Some rook polynomials.
A trivial computer program reveals that the only solutions in integers between -10,000 and 10,000 are: x = -1, x = 0, and x = 3. So, prove this.
Problem 74 in Mathematical Morsels. (Original Proposer: T.H. Gronwall.) Start with: (x2 + x/2 + 1)2 is too large, if x ≠ 0. Also, (x2 + x/2 + τ)2 is too small, for τ = (sqrt(5)-1)/4.
- The warden meets with the 23 prisoners when they arrive. He tells them:
- Devise a strategy which the prisoners can employ to guarantee their release.
- How would you change your strategy if there were 37 prisoners? What if the requirement were that each had to visit the room five times before release?
You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
In this prison there is a switch room which contains two light switches, labelled A and B, each of which can be in the on or off position. I am not telling you their present positions. The switches are not connected to a light, bell, or any other appliance. After today, from time to time, whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room, and this prisoner will select one of the two switches and reverse its position (e.g. if it was on, he will turn it off); the prisoner will then be led back to his cell. The prisoner must change the position of exactly one switch. Nobody else will ever enter the switch room.
Each prisoner will visit the switch room arbitrarily often. That is, for any integer N it is true that eventually each of you will visit the switch room at least N times.
At any time, any of you may declare to me: "We have all visited the switch room." If it is true (each of the 23 prisoners has visited the switch room at least once), then you will all be set free. If it is false (someone has not yet visited the switch room), I shall enjoy feeding you all to the alligators.
These ratios are not quite correct, but are not that far off the true values. The expected numbers of squares missed are: 161/4 = 40.25, 2111/84 ≈ 25.13, 10138/651 ≈ 15.57, 760405/79422 ≈ 9.57, and 1854589/317688 ≈ 5.84.
Show how to use five queens to cover all of the squares of the board.
The problem is to take the sixteen possible squares (all of the same size, of course) that result from drawing all possible subsets of the four lines of symmetry of the square and to rearrange these sixteen squares into a larger four by four square such that each line segment continues thought the adjancent squares (and thus looks like an unbroken line).
- At the beginning of each round, the three players simultaneously place one dime on the table.
- If all three coins show the same side (three heads or three tails), the players retreive their own coins and the round continues with them placing the coins on the table again (after possibly switching the side they will place up). This process will continue until the coins do not all match.
- If the coins do not match, the player whose coin shows a different side from the other two coins is declared the winner of that round, and keeps all three coins. This ends the round.
- The game continues until (at least) one of the players has no more dimes.
Hint: If f(x,y,z) is the expected number of rounds when the players start with x, y, and z dimes, with xyz ≠ 0, then
The original problem, posed in 1941, asked for the expected number of tosses. That adds a factor of 4/3, since the equation will now be
The published proof of this one is a little long. It might be nice to have a shorter solution. (I have an easy proof that the chromatic number is at most k c1/2, for some constant k.)