From: Android Subject: POD and correction to yesterday's problem First of all, the correction, I meant was there a positive intergral solution set to a^4 + b^7 + c^9 = d^11 Now, the P.O.D. Assume you have four squares, you have five balls. You throuw the five balls at the four squares and each ball has the same probability of falling into one of the squares. What is the possibility, that after 5 rounds (one round = throwing five balls), you have at least one hole free of balls. Also, if you pay $1 to a "game manager" for each round, and receive $1 from him for each empty hole after 5 rounds, how much does the "game manager" expect to make? I didn't understand the second part of the question when I first saw it, and I still don't get it. (this problem appeared on this year's UCSB math advanced exame) Enjoy, Benjie From: claxnes@dude.nwer.sandia.gov (Carl L. Axness) Subject: SPOILER - mood improver11/9 Find all complex solution to x^2(x^2+2) = (x-1)(x-3) Benjie SPOILER x^2(x^2+2)=(x-1)(x-3) Expanding and adding 1 to each side x^4 + 2x^2 +1 = x^2 - 4x + 4 => (x^2+1)^2=(x-2)^2 => x^2+1=x-2 or x^2+1=-(x-2) The solution to the last two eqs. is x=-1/2(+ or -)sqrt(5)/2 and x=1/2(+ or -)isqrt(11)/2 From: Android Subject: Contest 3, Round 3, Due Mon, Nov. 22nd early morning. Subject: Contest 3, Round 3 The following questions are for contest 3, round 3. Complete answer should be send to benjie@quack.kfu.com ONLY ^^^^^^^^^^^^^^^^^^^^^^^^^ Posting solutions to IAMS list will automatically disqualify you for the ^^^^^^^^^^^^^^^^^^^^^^^^ entire contest. ^^^^^^^^^^^^^^ Answers are due on Nov. 22nd. I. Find a formula for the sum of all the digits in the sum 1 + 11 + 111 + 1111 + ... + 111..1 where the last number in the sum are n 1's. If you think there are none, prove it. II. Find the sum of the digits in 1 + 11 + 111 + ... + 1111111...11 \- 22 1's -/ using the above formula. III. Find the roots of the quadratic equation x^2 - (5+7i)x + (-6+17i) = 0 IV. Assume X is a binary number, write a set of procedures to find out the number of 1's in X using only +, - and AND (the and logic operator) (Hint: use loops) Enjoy, Benjie From: Android Subject: Results of Contest 3 Round 2, Solutions follow The solution is also available from the mail server. Here is the result of the round 2 of the contests, I received limited number of solutions, may be because this round is a bit harder. Any other reasons? But anyway, if you only worry about your average, missing one round won't hurt. clong@cnj.digex.com 17/17 elessar@hermes.acm.rpi.edu 17/17 pasquale@xsft2.ico.olivetti.com 17/17 radcliff@csd4.csd.uwm.edu 17/17 cei@access.digex.net 16/17 dawagner@phoenix.Princeton.EDU 16/17 rajeev@cs.utk.edu 16/17 gt0095a@prism.gatech.edu 14/17 TavenerS@lilhd.logica.com 12/17 Congrats to all of them...... Here is the solution/key I made up, if you have any questions, email me. -----solutions------- I. "SUM" Additional Problems (12 Points) Let L_n = r^n + s^n for all positive integers n, where r = (1+sqrt(5))/2 and s = (1-sqrt(5))/2. A. Show that L_{n+1} = L_{n} + L_{n-1} Solution: note that r and s are solutions of x^2 - x - 1 = 0 thus r^2 = 1+r and s^2 = 1+s therefore, L_{n+1} = r^{n+1} + s^{n+1} = r^{n-1}r^2 + s^{n-1}s^2 = r^{n-1} + r^{n} + s^{n-1} + s^{n} = L_{n} + L_{n-1} Total Points: 3 B. Calculate r^2, r^5, r^8 Solution: r^2 = 3/2 + 1/2 sqrt(5) r^5 = 11/2 + 5/2 sqrt(5) r^8 = 47/2 + 21/2 sqrt(5) Total Points: 1 C. Conjecture on how you could obtain L_n by using only r_n Solutions: 1. s^n decreases as n gets larger. more, s^n < 1/2 for n > 1, so L_n is just the nearest integer to r^n. 2. Since r^n = a+bsqrt(5) and s^n = a-bsqrt(5), r^n+s^n=2a=L_n 3. 1/r = 2/(1 + sqrt(5)) { multiply top and bottom by s} = 2s/((1+sqrt(5))(1-sqrt(5))/2) = 4s/(1-5) = -s => s = -1/r therefore L_{n} = r^n + (-1)^n/r^n Total Points: 1 (I gave everybody a point here just for getting L_n in terms of r, there is no right answer, I wanted conjectures...) D. Compute the number of digits in L_201 Solution: Take the log_10 of L_201, which is almost r^201. Log_10 (r^201) = 201 Log_10 (r) = 42. So L_201 has 42+1=43 digits. Total Points: 2 E. Compute the smallest integer n for which L_n has 21 digits. What about 200 digits. Solution: n log r = 20, n=96 n log r = 199, n = 953 Total Points: 2 F. The fibonacci number can be obtained from the formula F_n = 1/(sqrt(5)) (r^n - s^n), for all positive integers n. Compute the smallest integer n for which F_n has 21 digits and write the first four digits of that F_n. Solution: log F_n ~=~ n log r - log(sqrt(5)) n log10 r - log(sqrt(5)) >= 20 n >= 97.3, n=98 F_98 = 1.353 x 10^20 Total Points: 3 II. Three roots of the equation (5 points) x^4 - px^3 + qx^2 - rx + s = 0 are tan A, tan B, tan C, where A, B, C are the angles of a triangle. Determine the fourth root as a function of (only) p,q,r, and s. Solution: let a,b,c,d denote the four roots. Note that tanA*tanB*tanC=tanA+tanB+tanC let j=a+b+c=abc let k = tan A tan B + tan A tan C + tan B tan C then (x-a)(x-b)(x-c)=x^3-ax^2+bx-a and (x-a)(x-b)(x-c)(x-d)=(x^3-jx^2+kx-j)(x-d) =x^4-(j+d)x^3+(j+kd)x^2-(k+jd)x+jd so j+d = p (1) j+kd = r (2) k+jd = q (3) jd = s (4) (3points) therefore, k = q-s, and (1-k)d = p-r so (1-q+s)d = p-r d = (p-r)/(1-q+s) (4points) if (1-q+s)=0, q-s=1, k=1, (x-a)(x-b)(x-c)(x-d)=(x^3-jx^2+kx-j)(x-d) => (x^3-jx^2+x-j) = (x-j)(x^2+1) (x-j)(x^2+1) (5points) has only one real zero, which cannot occur based on the origial question. From: Android Subject: Corrected Version of Solution to Problem II of Round 2 I made the following mistake, please note: 89c89 < then (x-a)(x-b)(x-c)=x^3-jx^2+kx-j <-- should be this --- > then (x-a)(x-b)(x-c)=x^3-ax^2+bx-a <-- not this -------------solution-------------- II. Three roots of the equation (5 points) x^4 - px^3 + qx^2 - rx + s = 0 are tan A, tan B, tan C, where A, B, C are the angles of a triangle. Determine the fourth root as a function of (only) p,q,r, and s. Solution: let a,b,c,d denote the four roots. Note that tanA*tanB*tanC=tanA+tanB+tanC let j=a+b+c=abc let k = tan A tan B + tan A tan C + tan B tan C then (x-a)(x-b)(x-c)=x^3-jx^2+kx-j and (x-a)(x-b)(x-c)(x-d)=(x^3-jx^2+kx-j)(x-d) =x^4-(j+d)x^3+(j+kd)x^2-(k+jd)x+jd so j+d = p (1) j+kd = r (2) k+jd = q (3) jd = s (4) (3points) therefore, k = q-s, and (1-k)d = p-r so (1-q+s)d = p-r d = (p-r)/(1-q+s) (4points) if (1-q+s)=0, q-s=1, k=1, (x-a)(x-b)(x-c)(x-d)=(x^3-jx^2+kx-j)(x-d) => (x^3-jx^2+x-j) = (x-j)(x^2+1) (x-j)(x^2+1) (5points) has only one real zero, which cannot occur based on the origial question. From: BANDA@ausvm1.vnet.ibm.com Subject: Fibonacci Problem Problem: Let F(i) denote the ith Fibonacci number, i.e, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, ... etc For any prime p (not equal to 5), show that p divides F(p-1) or F(p+1) Enjoy, Cheers, Venu From: Android Subject: P.O.D. Finished my USAMTS round 2 problems yesterday (one day late, oh well), so here is one for fun...... Assume you have a bag of 1993 red balls and 1993 black balls. Each time you take two from the bag. If they are of the same color, discard them, if they are of different color, keep the red throw away the black. What is the probability that the process will terminate with one red ball in the bag? Enjoy, Benjie From: claxnes@dude.nwer.sandia.gov (Carl L. Axness) Subject: POD - SPOILER 1! Perhaps a more interesting question would be what the answer would be for the same problem with 1992 red and 1992 black balls in the urn. From: Competitive Enterprise Institute Subject: Re: POD - SPOILER On Thu, 18 Nov 1993, Carl L. Axness suggested that the Tues. POD would be more exciting with 1992 red balls and 1992 black balls. This is a spoiler for his modified problem. 0! (that's not ! for factorial, but ! for emphasis) Because you always have an even number of red balls. Perhaps a more interesting question would be: what's the probability that, with 1992 red and 1992 black balls, you end up with (a) nothing, and (b) one black ball. From: claxnes@dude.nwer.sandia.gov (Carl L. Axness) Subject: Modified POD OK... OK.... I think I've almost gotten all the egg off my face! I guess working at a place like the Competitive Enterprise Inst., one is bound to catch an error (or trivial problem) quickly. But let's put the "modified POD" out where everyone can work on it instead of after a SPOILER. cei@access.digex.com suggests the following modification to Benjie's POD. First the original POD -- Assume you have a bag of 1993 red balls and 1993 black balls. Each time you take two from the bag. If they are of the same color, discard them, if they are of different color, keep the red throw away the black. What is the probability that the process will terminate with one red ball in the bag? The modification -- > Perhaps a more interesting question would be: what's the probability that, > with 1992 red and 1992 black balls, you end up with (a) nothing, and (b) > one black ball. > From: Android Subject: Problems Here are some brain teasers from Sept. issue of Quantum B91 Dancing regularities. At a party each boy danced with three girls, and each girl danced with three boys. Prove that the number of boys at the party was equal to the number of girls. B93 Bubbles in a glass. An upside-down glass was immersed in a pan filled with hot water. After a while, air bubbles started coming out of the glass. Why? From: Competitive Enterprise Institute Subject: SPOILER On Thu, 18 Nov 1993, Android wrote: > > Here are some brain teasers from Sept. issue of Quantum > > B91 Dancing regularities. At a party each boy danced with three > girls, and each girl danced with three boys. Prove that the number of > boys at the party was equal to the number of girls. Let b be the number of boys and g the number of girls. The total number number of dances is equal to 3b and is also equal to 3g. Therefore, b=g. > B93 Bubbles in a glass. An upside-down glass was immersed in a pan > filled with hot water. After a while, air bubbles started coming out > of the glass. Why? The water in the glass became hot eventually; the air expanded and the bubbles escaped from the glass. (I think. But I'm a mathematician. What do I know from physics?) From: Competitive Enterprise Institute Subject: A sports problem Suppose you have 8 teams competing in a tournament. Since 8 is a power of 2, it's easy to eliminate 8 teams to 1, usinga quarter final, a semi final, and a final -- A vs. B, C vs. D, E vs. F, G vs. H makes up the quarter final, etc. The total number of games is, of course, 4 + 2 + 1 = 7. Is this the minimum number of games to obtain one winner? What's the general form for the minimum number of games for 2^n teams? What if the number of teams isn't a power of 2 -- how many games are required for 10 teams? What about 17295 teams? Remember, we're looking for the *minimum* number of games required, so if your answer depends on the schedule or timing of the games, be sure it's really a minimum. - Alexander "Sasha" Volokh From: "David A. Wagner" Subject: Tiling a rectangle There was a nifty little piece in a magazine our math library gets called _The_Mathematical_Intelligencer_, and I thought some of you might like it... It was about tilings of rectangles: tiling a rectangle means partitioning it into a disjoint union of squares. Here's an example +---+-------+ | | | +---+ | | | | +---+-------+ if you believe that those really are squares. A perfect tiling is one where no two squares are of the same size, and a simple tiling is one where no proper subset of the squares form a subrectangle. Can you find any perfect tilings? How about any perfect simple tilings? If you want to think about the problem first, don't read the rest of this article :-) SPOILER! Here's a nifty way to think about the problem, using linear algebra. Suppose we have a tiling of a rectangle. Then extend the horizontal edges of all the tiles; let's call the regions between consecutive lines strips. Maybe a picture will help: ...+---+-------+... | | | ...+---+.......|... | | | ...+---+-------+... [The tiling pictured above isn't perfect or simple, but it should illustrate what I mean by strips: there are 2 strips in the diagram above.] Let m be the number of strips and n the number of tiles. Number the strips from 1 to m, proceeding (say) from the top down. Also number the squares from 1 to n in any fashion you like. Now define the m-by-n matrix A by the rule that A_ij is 1 if the i-th strip meets the interior of the j-th square, and 0 otherwise. Let x_i be the size (that is, side length) of the i-th square and let y_i be the height of the i-th strip. Define the vectors x = (x_1, x_2, ..., x_n) and y = (y_1, y_2, ..., y_m). Also let j be the m-vector (1, 1, ..., 1). CLAIM: The vectors x and y are determined uniquely (up to multiplication by a constant) by the matrix A and the equations A A^t y = j A^t y = x where A^t is the transpose of A. PROOF: The side length of each square is the sum of the heights of the strips that meet it, so by the definition of A, A^t y = x. Next, the sum of the side lengths of the squares which meet a strip must be the width of the rectangle. Since I'm only interested in determining the answer up to multiplication by a constant, without loss of generality suppose the width of the rectangle is 1. Then again by the definition of A A x = j. Now substituting x = A^t y, it follows that A A^t y = j. Now I must show that x and y are unique. It's enough to show that A A^t is non-singular, since then y = (A A^t)^-1 j x = A^t y = A^t (A A^t)^-1 j = A^-1 j. Let's calculate the rank of A. Note that for any two consecutive strips, say the k-th and (k+1)-th strips, there is some square that meets the former strip but not the latter. Thus, there is some column in A which has a 1 in row k and a 0 in each row after row k. But this holds for every 1<=k<=m, so A contains an upper triangular submatrix of size m, and A has rank m. Then an old linear algebra result tells us that A A^t is non-singular, and we're done. This theorem gives us a nice way of looking at the problem, and a few other results too! COROLLARY: There are a finite number of tilings of a rectangle with n squares. PROOF: There are only a finite number of possible intersection matrices A for any given m, n. Also we must have m <= n, so there are only a finite number of possible intersection matrices for any given n. But intersection matrix defines at most one solution pair (x, y) [disregarding multiplication by a constant], so we're done. COROLLARY: Any tiling must consist of squares with a rational side length. PROOF: Since A consists of just 0s and 1s, it is rational. Then x and y must be rational as well. -------------------------------------------------------------------------------- David Wagner dawagner@princeton.edu From: "Jonathan Wildstrom" <95JWILDSTROM@vax.mbhs.edu> Subject: Re: POD - SPOILER >Perhaps a more interesting question would be: what's the probability that, >with 1992 red and 1992 black balls, you end up with (a) nothing, and (b) >one black ball. You really only need to find one of these. Once you know the probability of nothing, you can find the probability of one black ball by subtracting the answer to a) from 1, since the sum of all the outcomes must be one, and the answer to one red ball was 0, leaving just nothing and one black ball. From: greg_jamison@csufresno.edu (Greg Jamison) Subject: Re: A sports problem In any tournament of this type, each game eliminates one team. Therefore, no matter how the games are scheduled, n-1 games are required to eliminate n-1 teams to leave one winner in n teams. From: Android Subject: Contest 3 Round 4, Due Sun, Nov. 28, 9:00am PST The following questions are for contest 3, round 3. Complete answer should be send to benjie@quack.kfu.com ONLY ^^^^^^^^^^^^^^^^^^^^^^^^^ Posting solutions to IAMS list will automatically disqualify you for the ^^^^^^^^^^^^^^^^^^^^^^^^ entire contest. ^^^^^^^^^^^^^^ Subject: Contest 3, Round 4 I. The sum of two integers is 30,030. Prove that their product is not divisible by 30,030. II. Does there exist a polyhedron with 1993 faces all of which are quadrilaterals? If yes, prove. If not, explain. Enjoy, Benjie From: Android Subject: Results, Contest 3 Round 3 Well, I've got even fewer admissions this time. May be the problems aren't that interesting or something? Please tell me why you are not participating so that I could make future contests better. All the solutions I got were good, even the ones that were wrong showed a lot of promising works. Congrats to all of the people who tried. The first one was not easy, some people misinterpreted the problem. Here is the result...... pasquale@xsft2.ico.olivetti.com 17/17 dawagner@phoenix.Princeton.EDU 16/17 rajeev@cs.utk.edu 16/17 maxime@srcinf.sochi.su 14/17 TavenerS@lilhd.logica.com 14/17 cei@access.digex.net 13/17 efedula@aol.com 9/17 wgd@houston.geoquest.slb.com 8/17 From: Android Subject: SPOILER -- Solutions to Contest 3, Round3, also available through mail server. > > I. Find a formula for the sum of all the digits in the sum > 1 + 11 + 111 + 1111 + ... + 111..1 > where the last number in the sum are n 1's. If you think there are > none, prove it. > Solution: This one is a bit hard. I did not get it neither, so I will include a solution from one of the submissions. Solution from dawagner@phoenix.princeton.edu, similar to that of pasquale@xsft2.ico.olivetti.com Let a_n = \sum_{j=1}^n {(10^j-1)/9} = 1 + 11 + 111 + ... + 111..1 as above. Also a_n satisfies the recurrence relation a_n = 10 a_{n-1} + n, a_0 = 0. Then the first few numbers in the sequence are 1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 1234567900, 12345679011, 123456790122, 1234567901233, ... Let b_0 = 0 and b_j = 123456790123456790...123456790 where the block 123456790 is repeated j times; that is, b_{j+1} = 10^9 b_j + 123456790 holds for all j>=0. An easy induction shows that for j, k non-negative integers, b_{j+k} = 10^{9k} b_j + b_k. Now for any non-negative integers j, k with 0<=j, 0<=k<=9 we have a_{10j+k} = 10^{j+k} b_j + a_{j+k} - j. An easy induction argument shows this also holds for any j>=0, k>=0. This enables us to calculate a_n easily and rapidly. Next let s(m) be the sum of the digits of m. We have s(10^k m) = s(m) for all non-negative integers k. Also, if q<10^k, then s(q + 10^k m) = s(q) + s(10^k m) = s(q) + s(m). Since a_n < 10^n for all n>=0, we have s(a_{10j+k}) = s(10^{j+k} b_j + a_{j+k} - j) = s(b_j) + s(a_{j+k} - j). Now since s(123456790) = 37, from the definition of b_j we see s(b_j) = 37j. All that remains is to analyze s(a_{j+k} - j). s(a_{j+k} - j) = s(10 a_{j+k-1} + j+k - j) = s(10 a_{j+k-1} + k) = s(a_{j+k-1}) + s(k) = s(a_{j+k-1}) + k when k<10. Now we can get a recurrence relation for s(a_n): s(a_n) = s(a_{10 floor(n/10) + {n mod 10}}) = s(b_{floor(n/10)}) + s(a_{floor(n/10) + {n mod 10}} - floor(n/10)) = 37 floor(n/10) + {n mod 10} + s(a_{floor(n/10) + {n mod 10} - 1}). Recall that s(a_1) = 1, which gives us an initial condition. Also, when n<10, s(a_n) = 37*0 + n + s(a_{0 + n - 1}) = n + s(a_{n-1}) = n + (n-1) + ... + 2 + 1 = n(n+1)/2, which is exactly as expected. Total Points: 6 > > II. Find the sum of the digits in > 1 + 11 + 111 + ... + 1111111...11 > \- 22 1's -/ > using the above formula. > Answer: 82 Total Points: 2 > > III. Find the roots of the quadratic equation > x^2 - (5+7i)x + (-6+17i)=0 > Answer: 2+3i and 3+4i Solution: let a and b be the two roots, then a+b = 5+7i ab=-6+17i if we think of a and b as a=(x1+y1*i) and b=(x2+y2*i) then x1+x2=5 y1+y2=7 x1*y2+x2*y1=17 x1*x2-y1*y2=-6 solve for x1, x2, y1, y2 we have x1=2 x2=3 y1=3 and y2=4 Total Points: 4 > > IV. Assume X is a binary number, write a set of procedures to find out > the number of 1's in X using only +,- and AND (the and logic operator) > Solution: Here is a description: count = 0 k = 1 loop: start with an integer n, let a be the "n and k" if a is k, count=count + 1 k = k+1 run the process again from loop until k = (number of binary bits in n) +1 or count = 0 loop: let n be the integer, k be the number of binary bits in n a = n & (2^(k-1)) if a = 2^(k-1), then count = count+1 and n = n - 2^(k-1) k=k-1 goto loop Total Points: 5 From: rajeev@cs.utk.edu Subject: SPOILER -- problem 4 from round 3. Benjie sends the following solution to problem 4 of round 3 of the contest. Qn. Assume X is a binary number, write a set of procedures to find out the number of 1's in X using only +,- and AND (the and logic operator) Sol. count = 0 loop: let n be the integer, k be the number of binary bits in n a = n & (2^(k-1)) if a = 2^(k-1), then count = count+1 and n = n - 2^(k-1) k=k-1 goto loop This is "cheating" because it uses an equality check ( if a = 2^{k-1}) inside the loop, and this is not one of the operations we are allowed to use. Is it possible to count the number of 1's in X without using this equality check? I think the following procedure works ( by adding 2 to a counter with every other 1 in X) when the number of 1s in X is even, but is off by one when the number of 1's is odd. Anybody got a fix? Note : I assume negative numbers are represented in sign magnitude form. A = 0, C = 0, K = 1. for i from 1 to n do A = ( X AND (K - A)) + ((X - K) AND A). { if current bit = 1, A toggles between 0 and K. } { if current bit = 0, A is unchanged } C = C + ((A + A + A + A - 1) AND 2). { if A = 0, C is unchanged. if A != 0, C = C + 2} K = K + K. A = A + A. end for. --Rajeev Govindan From: Android Subject: Re: SPOILER -- problem 4 from round 3. Hmm.. I didn't realize the = was actually an operator. I used it as a comparison function. Oh well, one of my solutin was right, I hope...... Benjie From: benjie@wales.sbay.org (Android) Subject: no subject (file transmission) From Benjamin.J.Tilly@Dartmouth.EDU Tue Nov 23 11:41:56 1993 However here is an interesting problem. Suppose that p(x) and q(x) are two monic polynomials of degree n and m respectively, with coefficients in the integers, and with roots a_1 , a_2 , ... , a_n and b_1, b_2, ... , b_m. It turns out that \prod_{i=1}^n \prod_{j=1}^m (x - a_i - b_j) is a polynomial with integer coefficients! In fact for (x-a_i-b_j) I could have written out *any* polynomial with integer coefficients with x, a_i, and b_j as variables. I find it neat that this makes it easy to find a polynomial with integer coefficients with sqrt(2) + cuberoot(3) as a root, either in factored form, or in unfactored form if you are willing to do some algebra. Ben Tilly From: Android Subject: Puzzles The following puzzles appeared in the sept. issue of Quantum, I though they were very interesting. The key to solving them is the property of invariant. 1. The numbers 1,2,..., n are arranged in some order. We can exchange any two adjacent numbers. Prove that an odd number of such exchanges produces an arrangement necessarily different from the initial one. 2. The numbers 1,2...,1993 are written in increasing order. Any four numbers can be rearranged in reverse order in the same places. Is it possible to obtain the reverse order 1993,1992,...,2,1 of the entire set of numbers? Enjoy, Benjie From: vhansen@ipf.bau-verm.uni-karlsruhe.de (Wolfgang von Hansen) Subject: Division by seven? Hi all! How can I check it out if a given integer can be divided by seven? How about eleven and thirteen and higher primes? Wolfgang From: Ingrid Voigt Subject: Re: Division by seven? > How can I check it out if a given integer can be divided by seven? > How about eleven and thirteen and higher primes? The integer abcdefghijk is divisible by seven if and only if the integer abcdefghij - 2k is. Example: 12345678 ==> 1234551 ==> 123453 ==> 12339 ==> 1215 ==> 111 ==> 9 9 is not divisible by 7, so 12345678 is not. Similar rules hold for eleven and thirteen: abcdefghij is divisible by eleven if and only if abcdefghi - j is. abcdefghij is divisible by thirteen if and only if abcdefghi + 4j is. They can be extended to *any* prime. Another rule for divisibility by eleven: abcdefghi is divisible by eleven if and only if a-b+c-d+e-f+g-h+i is. There is even a rule for all three of these primes: Divide your number into groups of three numbers, beginning on the *right*. Then add and subtract those three-digit numbers as above. Your long number is divisible by seven, eleven or thirteen if and only if the sum is. Example: 9876564321098 ==> 9 876 564 321 098 ==> 9 - 876 + 564 - 321 + 098 ==> -526 This number is not divisible by seven, eleven and thirteen, so 9876564321098 is not. Ingrid. From: Tavener Stephen Subject: RE: Division by seven? - SPOILER 10 mod 7 == 3 100 mod 7 == 10 * 10 mod 7 == 3 * 3 mod 7 == 2 10^3 mod 7 == 3 * 2 == 6 == -1 10^4 == 3 * 6 == 4 == -3 10^5 == 3 * 4 == 5 == -2 10^6 == 3 * 5 == 1 Cyclic, period 6 --> Define lookup[6]={3, 2, -1, -3, -2, 1} a0 * 10^0 + a1 * 10^1 + .... + an * 10^n is divisible by 7 <=> a0 * lookup[0] + a1 * lookup[1] + a2 * lookup[2] + .... + an * lookup[n mod 6] is divisible by 7 For 11, define lookup[2]={-1, 1} (10 mod 11 == -1, 100 mod 11 == 1 - cyclic, period 2) For 13, 10 mod 13 == -3 100 mod 13 == -30 == -4 10^3 mod 13 == -40 == -1 10^4 mod 13 == -10 == 3 10^5 mod 13 == 30 == 4 10^6 mod 13 == 40 == 1 Cyclic, period 6 --> Define lookup[6]={-3, -4, -1, 3, 4, 1} ---------- From: iams-request Subject: Division by seven? Hi all! How can I check it out if a given integer can be divided by seven? How about eleven and thirteen and higher primes? Wolfgang From: Android Subject: P.O.D. Here is a nice problem. Ten plus signs and fifteen minus signs are written on the blackboard. You can erase any two signs and write in their place a plus sign if they were the same and minus if they weren't. This operation is repeated 24 times. What sign remains on the blackboard? Hint: Use the property of Invariant. Enjoy, Benjie From: Wlodzimierz Holsztynski Subject: poyhedra with quadrilateral faces Let's talk about convex polyhedra. For n=1993 Benjie have asked if there is one which has n=1993 faces -- all quadrilaterals. I have an answer for all n but n=7 and 9. You may consider the case n=5 to be a mood improver. Wlodek Wlodzimierz Holsztynski From: Ariel Scolnicov Subject: Re: Division by seven? There are lots of rules for division by various numbers (I was unaware of the existence of simple rules for 7, though). In our Computability, Automata and Formal Languages class we did some related stuff a while back. It turns out that you can always check for these things with a finite state machine: According to a theorem by Myhill, any language defines a right-invariant congruence relation: x ~ y iff (for all w xw is in the language iff yw is). The language is regular iff the number of congruence classes of the relation is finite. The minimal FSM accepting the language has that number of congruence classes. What this means in real terms is that we can consider the decimal strings representing numbers divisible by 7, say, as a language. It is easy to see that the congruence relation has 7 classes: one for each remainder. So there exists a finite state machine with 7 states (but no less) which accepts all numbers divisible by 7. What does it look like? Well, each state has to represent a certain remainder. By inspection we see what the remainder is after dividing by 7. So state 1 (representing remainder 1), receiving the digit 0, goes to 3 (because we have a number of the form 7k+1 which we multiply by 10); receiving the digit 1, goes to 4 (7k+1 --> 70k+11 --> 7k'+4), etc. Of course this isn't very helpful when it come to actual rules. But "real" rules are always based on properties of these state transitions. Please excuse any mistakes I may have made regarding technical terms. I only know most of these terms in Hebrew, which isn't much help. I'd be grateful to know if I'm using the wrong terms. Ariel. From: AD Wilcock Subject: Alphabetical Symmetries Here's a little symmetry problem for you all, I don't know the answer, but I know there is one: Why can't a letter of the alphabet (when written in its most symmetric form) have two points of symmetry ? From: Steve Wildstrom Subject: Divisibility Areil Scolnikov describes a general method for testing divisibility, but it seems more complicated than it has to be. Steven Taverner (I hope I got that right) in his post of yesterday has a much simpler approach, but stops short of generalizing it. The following combines the two approaches into what I hope is a simple-to-follow test of divisibility. This algorithm will work for any odd prime other than five: 1) Determine the cycle of residues for 10^k mod p. For example: 10^0 mod 7 = 1 10 mod 7 = 3 10^2 mod 7 = 2 10^3 mod 7 = 6 10^4 mod 7 = 4 10^5 mod 7 = 5 10^6 mod 7 = 1 (Taverner treats a mod b as negative for a Subject: Pi mnemonic Some of you may know of ways to remember digits of pi. The most common way seems to be remembering sentences or poems; counting the number of letters in each word gives you a digit of pi. For example, in French: Que j'aime a faire apprendre ce nombre utile aux sages! Illustre Archimede, artiste, ingenieur, [a line which I've forgotten] Pour moi, ton probleme eut de pareils advantages. Or, in Russian: Kto i (sh)ut(ia) i skoro po(zh)elaet' pi uznat' (ts)yfr' u(zh)' znaet [31415926535, where (xx) counts as one letter, and ' is a letter] Or, in Latin: I nunc, O Baili, Parnassum et desere rupem, Dic sacra Peridium deteriora quadris! (or something like that) etc., etc., etc. I and some friends have come up with an English version. A common English version of 3.14159265358979 already exists, but we built off of that. We now have 167 digits. By the way, the reference to "valuable wood" is a reference to Monte-Carlo estimations of the value of pi, which consist of throwing toothpicks onto a paper with evenly spaced lines. (The propbability of the stick hitting a line is related to pi, so that estimating the probability of hitting the line by observing the frequency allows you to estimate pi.) 3.14159265358979323846264338327950288419716939937510582097494459230 78164062862089986280348253421170679821480865132823066470938446095 5058223172535940812848111745028410270 [167 digits.] (Note: Insert a 0 after the end of each sentence.) How I need a drink, alcoholic of course, after the tough lectures involving quantum mechanics, but we did estimate some digits by making very bad, not accurate, but so greatly efficient tools! By dropping valuable wood, a dedicated student -- I, Volokh, Alexander, can determine beautiful and curious stuff, O! Smart, gorgeous me! Descartes himself knew wonderful ways that could ascertain it too! Revered, glorious -- a wicked dude! Behold an unending number -- pi! Thinkers' ceaseless agonizing produces little, if anything. For this constant, it stops not -- just as e, I suppose. Vainly ancient geometers computed it -- a task undoable. Legendre, Adrien Marie: "I say pi rational is not!" Adrien proved this theorem. Therefore, the doubters have made errors. (Everybody that's Greek.) Today, counting is as bad a problem as years ago, maybe centuries even. Moreover, I do consider that variable x, y, z, wouldn't much avail. Pi, imaginary, like i? No, buffoon! - Alexander "Sasha" Volokh David Tazartes Steve LaCombe From: Competitive Enterprise Institute Subject: Re: Alphabetical Symmetries -- SPOILER On Tue, 30 Nov 1993, AD Wilcock wrote: > Why can't a letter of the alphabet (when written in its most symmetric > form) have two points of symmetry ? Suppose a letter of the alphabet did have two points of symmetry. Call those points A and B. This means that if X is a point on the letter, then fa(X), the image of X with respect to A, is also on the letter. So is fb(X). The alphabet is such that the line (AB) will intersect the letter at least once. Let X be one such intersection, and assume for convenience that A is closer to X than B is. So XA < XB. fb(X) is on the letter, and the distance from X to fb(X) is 2 XB. Now consider fa(fb(X)). The distance from fb(X) to fa(fb(X)) is twice the distance from A to fb(X), which is equal to 2 (AB + XB). Keep on taking the image of every point thus obtained with respect to the furthest center of symmetry. Of course, every such point is on the letter. I don't feel like calculating the exact distances between points, but clearly, the distance between the furthest points increases without bound as you do more and more iterations. Since no letter of the alphabet is infinitely large, it cannot have two centers of symmetry. - Alexander "Sasha" Volokh From: Steve Wildstrom Subject: Re: Divisibility -- SPOILER On Tue, 30 Nov 1993, Competitive Enterprise Institute wrote: > > > On Tue, 30 Nov 1993, Steve Wildstrom wrote: > > > > > Areil Scolnikov describes a general method for testing divisibility, but > > it seems more complicated than it has to be. Steven Taverner (I hope I got > > that right) in his post of yesterday has a much simpler approach, but > > stops short of generalizing it. The following combines the two approaches > > into what I hope is a simple-to-follow test of divisibility. > > > > This algorithm will work for any odd prime other than five: > > > > 1) Determine the cycle of residues for 10^k mod p. For example: > > 10^0 mod 7 = 1 > > 10 mod 7 = 3 > > 10^2 mod 7 = 2 > > 10^3 mod 7 = 6 > > 10^4 mod 7 = 4 > > 10^5 mod 7 = 5 > > 10^6 mod 7 = 1 > > (Taverner treats a mod b as negative for a > me but it works just as well.) > > > > 2) Consider the number to be tested as a polynomial in the form > > a_0 + a_1*10 + a_2*10^2 + ... + a_n*10^n > > > > 3) Replace each power of 10 with the appropriate residue form (1), that is > > (10 ^(k mod c)) mod p, where c is the length of the cycle (6 in the > > example given) and p is the prime being tested. > > > > 4) Carry out the multiplications and sum the terms. If the sum is > > divisible by p, the number is. > > > > The proof of this derives from the fact that > > (a*b) mod n = (a mod n * b mod n) mod n > > > > The remaining question, left as a not-quite-trivial exercise, is: > > Why doesn't the algorithm work for p=5? > > Doesn't it, though? > > 10^0 mod 5 = 1 > 10^1 mod 5 = 0 > 10^k mod 5 = 0 for all k > 0 > > (Just replace the phrase "k mod c" in section 2 with "k" -- or think of > the length of the cycle as being infinity, and k mod infinity is alaways k.) > > Therefore, > a_0 + a_1 * 10 + a_2 * 10^2 + ... + a_n * 10^n > is congruent, mod 5, to: > a_0 + 0 + 0 + ... + 0 = a_0. > > If a_0 is divisible by 5, so is the number. Same for 2. This is because > 2 and 5 are the only primes not relatively prime to 10. > > - Alexander "Sasha" Volokh I guess it does indeed work, in a degenerate sort of way. I realized that in the case of two, all positive powers of 10 were congruent to 0 mod 2. When I was playing with five, I saw thta I wasn't getting a proper cycle of residues, attributed the failure to the fact that gcd(10,5)>1, and never bothered to notice that the cancellation of all but the units place still left with a valid test. So we can say it works for all primes, though 2, 3, and 5 are trivial cases where this method of "casting out whatever" amounts to a complicated version of the standard tests for divisibility. From: widsith@mindvox.phantom.com (David Devejian) Subject: subscribe I heard about this IAMS thing, and would like to jon up. so add me to your mailing list or what ever it is. By the way, I checked out the problems on sunday, and for the second, the one involving reeversion of four numbers at a time, it is proveable by induction. given and sequence of N+1 numbers, you can revers it by reversing N numbers at a time , simply by repetitions of reversing the set {1..N} and {2..N+1} alternately. thus given four, you can get to 1993. However it does take approx 1E5000 moves. Mailing Address is : /***********************************************\ * 'What man, not a nincompoop, has ever * * been heard by a jury of his peers?' * * -Jane Heap (Editor of the Little Review) * \***********************************************/ From: Android Subject: SPOILER -- POD 11/29 - Invariant problem From dawagner@phoenix.Princeton.EDU Tue Nov 30 07:45:31 1993 Problem: Ten plus signs and fifteen minus signs are written on the blackboard. You can erase any two signs and write in their place a plus sign if they were the same and minus if they weren't. This operation is repeated 24 times. What sign remains on the blackboard? Solution: Lemme change the wording of the problem just a little: suppose the blackboard was filled with ten instances of ``+1'' and fifteen of ``-1''. Then it is originally true that the product of all the numbers on the blackboard is 1^10 (-1)^15 = -1. Also, the operation defined in the second sentence [erase any two numbers; write ``+1'' if they were the same, and write ``-1'' otherwise] does not alter the product of the numbers on the blackboard. That is, the product of the numbers on the blackboard before the operation is the same as the product of the numbers on the blackboard after the operation. So the invariant that "the product of all the numbers on the blackboard is -1" remains true no matter how many times we apply the operation. Thus, when we're done, the one remaining number must be -1. [To translate into the wording of the original problem, this means that the one remaining sign on the blackboard must be a minus.] From: jmlm@dit.upm.es (Joaquin Maria Lopez Munoz) Subject: Re: Alphabetical Symmetries -- SPOILER I think the proof you give is not entirely satisfying. Why do you assert that line AB does intersect the letter at some point? In fact this is the case, for alphabet letters actually dont have two distinct simmetry points, therefore every assertion one can made about such (inexistent) lines is neccesarily true. But, as you surely have realized, this is a circular reasoning. ----------------- Joaquin Maria Lopez Munoz. ETSI de Telecomunicacion. Madrid, Spain. e-mail address: jmlm@bosco.dit.upm.es From: Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly) Subject: Re: Could people please not treat the IAMS list as a forum for personal conversations? If this continues for long then I will have to unsuscribe. Please make sure that things sent over this group either are business, such as some of the administrative messages that Benjie sends out, or are mathematical And in keeping with my request that people avoid just having personal comments on this list, here is a cute problem to try. Show that if p is an odd prime then there is always a positive integer N < sqrt(p) + 0.5 with N not congruent to any square mod p. As there are stronger results available with complicated techniques, I also want the proof to be very short. A little notation may help. Define (n,p) to be 1 if n is congruent to a square mod p and -1 otherwise. You may take it as given that if p is an odd prime then (n,p) is -1 sometimes, and (n,p)(m,p) = (nm,p). I will post a solution in a few days if nobody gets it. Enjoy, Ben Tilly From: Competitive Enterprise Institute Subject: Re: Alphabetical Symmetries -- SPOILER On Wed, 1 Dec 1993, Joaquin Maria Lopez Munoz wrote: > I think the proof you give is not entirely satisfying. Why do you > assert that line AB does intersect the letter at some point? In fact > this is the case, for alphabet letters actually dont have two > distinct simmetry points, therefore every assertion one can made > about such (inexistent) lines is neccesarily true. But, as you > surely have realized, this is a circular reasoning. It isn't *quite* circular reasoning. The proof doesn't depend on it, but it's just easier to explain if you limit the set of letters to letters through which you can't pass an infinite line (unlike, say, the Greek lettter capital Chi). A proof that doesn't use this fact would go as follows: Assume two points of symmetry, A and B, and let X be a point on the letter. If X is on the letter, then so is fa(X) and so is fb(fa(X)). And the distance between X and fb(fa(X)) is greater than AB. (This is easy to show, but a picture is worth a thousand words. [Note: 1000 words = 2000 bytes = 16000 bits, and 2 bits is a quarter. So a picture is worth $2000. But I digress.] Since this is true of any point on the letter, you can apply the same process (reflect with respect to A, then with respect to B) to fb(fa(X)), and the distance between X and the resulting point (fb(fa(fb(fa(X))))) will be greater than 2AB. In fact, when you apply the process n times, the disttance between X and the resulting point "[fb(fa]^n(x)" is greater than nAB. Therefore, the distance between X and the last point given by this process increases without bound as the number of iterations increases. Since alal of these points belong to the letter, the letter must be infinite. Since no letter of the alphabet is infinite, there can not be two points of symmetry. The reason I had done my previous explanation with X being the intersection of (AB) with the letter was that then you could replace "greater than AB" with "equal to AB," and you could draw a simple picture like this: A B X fa(x) A B X fa(x) A B X fb(fa(x)) and so on. - Alexander "Sasha" Volokh From: claxnes@nwer.sandia.gov (Carl L. Axness) Subject: quickies I was dissappointed to see a number of unsubscribers to iams this morning. Perhaps there is not enough "action" or what is a bit disappointing to me, rigorous proofs of problems. In any case, here are a couple of "quickies." 1) At how many points on the earth can a person walk a mile south, then a mile east, and finally a mile north and end up at the same point. i 2) Compute i , where i=sqrt(-1). From: Wlodzimierz Holsztynski Subject: Re: quickies It was about finding points on Earth (sphere), from which by going one mile South, then East, then North we get back to the original point. Begin forwarded message: From: Abraham S. Mantell Subject: Re: quickies 1) As far as I see, only one point...namely the North Pole. mantell@rpi.edu ======================= This is not the only one. There are also all points on infinitely many latitudes near the South pole. You go toward the South pole, then you make a few FULL circles around it, then you get back going North. For each positive integer n there is exactly one latitude corresponding to making n cirles. Wlodek H. From: feng@iqe.ethz.ch (Jianhong Feng (HPF D21 2342)) Subject: Re: quickies On <199312011812.AA01409@quack.kfu.com> Carl L. Axness wrote claxnes@nwer.sandia.gov > 1) At how many points on the earth can a person walk a mile south, then > a mile east, and finally a mile north and end up at the same point. On all points of the northern hemisphere which are 0.5 mile away from the equator. > i > 2) Compute i , where i=sqrt(-1). i^i = exp[i ln(i)] = exp[ i [i (2 n + 1/2) Pi] ] = exp[ -(2 n + 1/2) Pi ], where n is an arbitrary integer. J. Feng From: Android Subject: SPOILERS -- Hints for BenTilly's Problem From Benjamin.J.Tilly@Dartmouth.EDU >Show that if p is an >odd prime then there is always a positive integer > N < sqrt(p) + 0.5 >with N not congruent to any square mod p. As there are stronger results >available with complicated techniques, I also want the proof to be very >short. A little notation may help. Define (n,p) to be 1 if n is congruent to >a square mod p and -1 otherwise. You may take it as given that if p is an odd >prime then (n,p) is -1 sometimes, and (n,p)(m,p) = (nm,p). >I will post a solution in a few days if nobody gets it. Hint: Look at {p, p + 1, ... , p + N - 1}. Spoiler: Let N be the smallest positive integer with (N,p)=-1. Then N divides one of p, p-1 , ... , p + N - 1 since that is a string of N consecutive integers. Since p is prime, (p,p) is not -1, and (1,p) is not one, we know that N does not divide p. Therefore there exists a positive integer m with p < N m =< p + N - 1 Now (N m, p) trivially is (N m - p, p), which by the definition of N must be 1. Therefore (m , p) must be -1. But m is a positive integer so by the definition that means that m is at least N. Therefore we have that N^2 =< p + N - 1 At this point it is clear that N cannot be much larger than sqrt(p), but we still need to figure out how much. This can be done with the quadratic formula, or less messily as follows. Let a = N - sqrt(p) so N = sqrt(p) + a. What we need to show is that a < 0.5. Now the previous equation becomes p + 2a sqrt(p) + a^2 =< p + sqrt(p) + a - 1 But p = p and if a >= 0.5 then 2a sqrt(p) >= sqrt(p) and a^2 > a - 1, which contradicts the inequality. Ben From: mic@cs.ucsd.edu (Michelangelo Grigni) Subject: SPOILER: squares mod p A nice puzzle from Benjamin.J.Tilly@Dartmouth.EDU (Benjamin J. Tilly): > Show that if p is an odd prime then there is always a positive > integer > > N < sqrt(p) + 0.5 > > with N not congruent to any square mod p. A little notation may > help. Define (n,p) to be 1 if n is congruent to a square mod p and > -1 otherwise. You may take it as given that if p is an odd prime > then (n,p) is -1 sometimes, and (n,p)(m,p) = (nm,p). Spoiler Below Since sqrt(p)+0.5 is not an integer, it suffices to take B=floor(sqrt(p)+0.5), and show that some N<=B is a non-square. Assume instead that all 1<=N<=B are squares. First note B >= sqrt(p)-0.5, so B(B+1)>=p-1/4. Since B(B+1) is an integer, we have B(B+1)>=p, so the following claim applies for M=B: CLAIM: Suppose that M= p, and (N,p)=1 for all 1<=N<=M. Then (M+1,p)=1 as well. Proof: Let k be the least integer such that k(M+1)>=p. By the assumptions on M we have 1<=k<=M, so (k,p)=1. Let x=k(M+1)-p, clearly x>=0, and x>=1 since p is prime. By the choice of k we have (k-1)(M+1)<=p-1, thus x<=M, so (x,p)=1. Finally k(M+1)==x(mod p), (k,p)(M+1,p)=(x,p), and (M+1,p)=1. Applying the claim inductively for M=B,...,p-2, we get no non-squares at all mod p. But that contradicts the existence of non-squares. [qed] [PS: My apologies for the pedantic style. The decoration illustrates a solution to the "firing squad problem". So, what is the problem?] From: efedula@aol.com Subject: Re: SPOILERS -- Hints for BenTilly's Problem --- Let N be the smallest positive integer with (N,p)=-1. Then N divides one of p, p-1 , ... , p + N - 1 since that is a string of N consecutive integers. Since p is prime, (p,p) is not -1, and (1,p) is not one, we know that N does not divide p. --- Correct me if I'm wrong, but I believe that (1,p) is 1 for all integers p (not just primes) greater than 1, since 1^2=1 (mod anything), and (p,p) is 0 (p^((p-1)/2) divides p). We know that N doesn't divide p since p is prime, and N is not 1 or p (since neither has a quadratic character of -1 mod p). I guess you just accidently threw in that extra 'not.' From: Android Subject: Contest 3 Result 4, Finally Here is the contest 3 result 4, took me a while to get start on it and also a while to grade it. I got, as usual, nice solutions. Keep it up, folks. questions attempted From pasquale@xsft2.ico.olivetti.com 17/17 2 From radcliff@csd4.csd.uwm.edu 17/17 2 From wlodek@wtg20.wiltel.com 17/17 2 From TavenerS@lilhd.logica.com 13/17 2 From gt0095a@prism.gatech.edu 13/17 2 From lip@maths.mu.oz.au 13/17 2 From dawagner@phoenix.Princeton.EDU 8/17 1 From: Android Subject: Contest 3 Round 5 Solutions to Round 4 are available through the mail server. Email iams-request@quack.kfu.com with SOLUTION as the subject to receive the solutions. Subject: Contest 3, Round 5 The following questions are for contest 3, round 5. Complete answer should be send to benjie@quack.kfu.com ONLY ^^^^^^^^^^^^^^^^^^^^^^^^^ Posting solutions to IAMS list will automatically disqualify you for the ^^^^^^^^^^^^^^^^^^^^^^^^ entire contest. ^^^^^^^^^^^^^^ Answers are due on Dec. 11th, 9:00am PST I. Find all positive integer solutions (x,y) of the equation x^y - y^x=x+y. II. Does there exist a pentagon that can be cut into two congruent pentagons? Prove or disprove. Enjoy, Benjie From: Android Subject: SPOILER -- Solutions to Contest 3 Round 4 Here is the solution to contest 3 round 4. I hope they are all right this time. Please email comments regarding to the contest solutions to the net, so everybody could hear. If you found an easier solution, post it. Happy mathing, Benjie //////////////////////////////////////////////////////////////////////// IIIII A M M SSSSSS I A A MM MM SS I AAAAA M M M M SS I A A M M M M SS IIIII A A M M M SSSSSS /////////////////////////////////////////////////////////////////////// I. The sum of two integers is 30,030. Prove that their product is not divisible by 30,030. Total Points: 8 Solutions: 1) By radcliff@@csd4.csd.uwm.edu 30,030 is the LCD of {2,3,5,7,11,13}. Since 0 < m < 30,030, there exists p in {2,3,5,7,11,13} so that p does not divide m. Since p divides 30,030, it follows that p does not divide n = 30,030 - m. Suppose that 30,030 divides mn. Then p divides mn. Since p is prime, either p divides m, or p divides n. This is a contradiction. Q.E.D. 2) By benjie@quack.kfu.com Assume two positive integers are a, and b and a+b=30030. Assume, also, that their product is divisible by 30,030. Note that if a+b=30030 then a*b=a(30030-a) = 30030a-a^2 Since we assumed that the product of a and b is divisible by 30,030, 30030a-a^2 | 30030 and a^2 | 30030 Assume a^2=n*30030 for some integer n, then a = sqrt(n*30030) but a has to be an integer, so n*30030 has to be a perfect square. Since 30030=2*3*5*7*11*13, in order for n*30030 to be a perfect square, n=2*3*5*7*11*13 at least. In which case a=30030. But a and b are positive integers and a+b=30030, which means a<30030. Thus, our assumption that a*b | 30030 is wrong. Q.E.D. II. Does there exist a polyhedron with 1993 faces all of which are quadrilaterals? If yes, prove. If not, explain. Total Points: 9 Solutions: 1) By radcliff@csd4.csd.uwm.edu If you have a polyhedron with N quad. faces, then you can get one with N+4 quad. faces. Choose a face, and do the following transformation: +---------+ +---------+ | | |\ /| | | | \ / | | | | +---+ | | | >=====> | | | | | | | +---+ | | | | / \ | | | |/ \| +---------+ +---------+ If we can find a polyhedron with K faces, where K < 1993 and K = 1 mod 4, then the problem is solved. We just repeat the transformation above until we have 1993 faces. I will now describe a polyhedron with 25 quad. faces. Take two cones whose bases are decagons (10-gons), and glue them together along the bases, to form a polyhedron with 20 triangular faces. Now, truncate every other corner around the "equator" where the cones were joined. All of the triangles have become quadrilaterals, and we have added 5 new quad "facets". 2) From pasquale@xsft2.ico.olivetti.com Take a pyramid, whose base is a square with side length of 1, whose height has a length of 1, and falls in the center of the base. Section the pyramid with a plane, parallel to the base, at 1/10 of the height, so getting a frustum of pyramid, with bases ABCD (larger) and A'B'C'D' (smaller), and heigth 1/10. Take a second frustum, equal to the first, turn it upside down, and join the two, so that larger bases coincide. Let it be A"B"C"D" the smaller base of second frustum. The resulting solid is a polyhedron with 1 + 4 + 4 + 1 = 10 faces. Now, section the polyhedron with a plane, perpendicular to the base diagonal AC, and containing vertices A' and A", and cut away the piece containing vertice A. Let it be L and M the intersections of that plane with, respectively, edges AB and AD. The resulting polyhedron has: - face ABB'A' modified in face LBB'A'; - face ADD'A' modified in face MDD'A'; - face ABB"A" modified in face LBB"A"; - face ADD"A" modified in face MDD"A"; - new face A'LA"M, so that it has 11 quadrilateral faces. Make the same cut to vertices B and D, finally getting a polyhedron with 13 quadrilateral faces. Now, consider a new frustum of pyramid, with square bases, the larger one equal to base A'B'C'D', the smaller one equal to 9/10 of larger one, heigth 1/2 of previous frustum. Put this frustum on top of the polyhedron, getting a new polyhedron with 13 + 4 = 17 faces (lateral edges of last frustum, and original polyhedron ones are not alligned). Repeat this operation for: (1993 - 13 - 4) : 4 = 494 more times, each time taking a new frustum with larger base fitting the top face of polyhedron, smaller base equal to 9/10 of larger one, heigth 1/2 of previous frustum, so adding 4 more quadrilateral faces. The ending polyhedron has 1993 quadrilateral faces. From: tulled@rpi.edu (David Michael Tuller) Did anyone here take the Putnam? For those of you who didn't, I am including a copy of the exam that appeared on sci.math. Please post your answers (so I can see solutions to those I didn't get). Enjoy! {{{{{{{{{{{{{{{{{{{{{{{{{{{{ * notes * }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Hopefully this will clarify this article a little. / integeral is denoted by | | / x is x subscript n n x^y is x rasied to the y th power {{{{{{{{{{{{{{{{{{{{{{{{{{{{ * notes * }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Here were the questions: ============================================================================== A1: The horizontal line y=c intersects the curve y=2x-3x^3 in the first quadrant as in figure. Find c so that the ares of the two shaded regions are equal. | y | ___ y=c | / B \ (parts labeled A, B are shaded regions) ------------------------- |A / \ | / \ |/ \ ------------------------- x | ============================================================================== A2: Let {X } be a sequence of nonzero real numbers such that { 2} X^2 - X X =1, for n=1,2,3... n n-1 n+1 Prove there exists a real number a such that X =aX -X for all >=1. n+1 n n-1 ============================================================================== A3: Let P be the set of subsets of {1,2,...,n}. Let c(n,m) be the number of n functions f:P --> {1,2,...,m} such that f(A AND B)=min{f(A),f(B)}. n Prove that m _ c(n,m)=\ j^n /_ j=1 ============================================================================== A4: Let x ,x ,...,x be positive integers each of which is less than or equal to 1 2 19 93. Let y ,y ,...,y be positive integers each of which is less than or 1 2 93 equal to 19. Prove that there exists a (nonempty) sum of some x' i equal to a sum of some y' s. j ============================================================================== A5: Show that ( x^2 - x )^2 f(x)= ----------------- ( x^3 -3x + 1 )^2 / -10 / 1/11 / 11/10 | | | | f(x)dx + | f(x)dx + | f(x)dx / -100 / 1/101 / 101/100 is a rational number ============================================================================== A6: The infinite sequence of 2's and 3's 2,3,3,2,3,3,3,2,3,3,3,2,3,3,2,3,3,3,2,3,3,3,2,3,3,3,2,3,3,2,3,3,3,2,... has the property that, if one forms a second sequence that records the number of 3's between successive 2's, the result is identical to the given sequence. Show that there exists a real number r such that, for any n, the nth term of the sequence is 2 if and only if n=1+ |_ rm _| for some nonnegative integer m. (Note: |_ x _| denotes the largest integer less than or equal to x.) ============================================================================== B1: Find the smallest positive integer n such that for every integer m, with 0 Subject: Putnam Contest On Sun, 5 Dec 1993, David Michael Tuller wrote: > A1: > The horizontal line y=c intersects the curve y=2x-3x^3 in the first quadrant > as in figure. Find c so that the ares of the two shaded regions are equal. > > | y > | ___ > y=c | / B \ (parts labeled A, B are shaded regions) > ------------------------- > |A / \ > | / \ > |/ \ > ------------------------- x > | > I got c=4/9. > ============================================================================== > A2: > Let {X } be a sequence of nonzero real numbers such that > { 2} > > X^2 - X X =1, for n=1,2,3... > n n-1 n+1 > Prove there exists a real number a such that X =aX -X for all >=1. > n+1 n n-1 > I proved that (1) There exists a real number "a" that works for n=1. (2) Suppose "a" works for n=k, and "b" works for n=k+1, after a bunch of algebraic manipulations, I showed that a-b=0. ie. The same "a" works for all n up to k+1. By induction, this "a" works for all n >= 1. I couldn't get the other ones. Does anyone have more solutions? Howard Cheng hcheng@gpu.srv.ualberta.ca From: tulled@rpi.edu (David Michael Tuller) Subject: Putnam Contest: Numerical Spoilers I do have solutions for A1-3 and B1-3, some of which I got from sci.math. Some numerical answers: A1. 4/9 A6. I know that r=2+sqrt(3) is the r that they want but I can't prove it. B1. 1993*2+1=3987 B2. 0 B3. 5/4-1/4Pi Did anyone get A4-6 or B4-6? David M. Tuller tulled@rpi.edu From: Ariel Scolnicov Subject: Re: Putnam Contest: Numerical Spoilers tulled@rpi.edu (David Michael Tuller) writes: >I do have solutions for A1-3 and B1-3, some of which I got from sci.math. > >Some numerical answers: > >A1. 4/9 >A6. I know that r=2+sqrt(3) is the r that they want but I can't prove it. >B1. 1993*2+1=3987 >B2. 0 >B3. 5/4-1/4Pi > >Did anyone get A4-6 or B4-6? > >David M. Tuller >tulled@rpi.edu I took a Putnam-compatible contest in Tel Aviv University yesterday (same questions, same checking, no prizes :-( ). I didn't get A5 all the way through, but the "obvious" thing to do is to note that substituting 1/(1-u) for x in the function being integrated yields the same function again! So we can perform substitutions and get one monster integral on any one of the three integration intervals. I didn't go much further, except to do some cancellation and numerology: the integral is on the function x*(x-1)^3 + r(x) ---------------- r(x)^2 for r(x) = x^3-3x+1. ( I think. I may have forgotten something since yesterday). Can anybody take it from here? Regarding B6, somebody solved it yesterday (again in Tel Aviv) -- the key is to look as remainders mod 2^i. These can be eliminated for all i from each of the three numbers. The proof was fairly complicated, and I don't particularly remember it, but the idea is to transform remainders mod 2^i into remainders mod 2^(i+1), with i increasing by 1 in each step (the possible remainders are thus 0 and 2^(i-1) mod 2^i for each i). Since the sum of the 3 numbers remains constant, eventually we have 2^i larger than the smallest number, which is thus 0. This solves the question. Note that the process doesn't work once one of the numbers is 0. If it did, we'd be in a lot of trouble, since we could zero all three numbers -- an obvious impossibility! Ariel.