Saturday, March 28, 2009

my impossible project

Here is my project from this morning:
Yeah, it was tricky. I thought I had the calculations right, but there must have been a sign error somewhere.

Friday, March 27, 2009

solution: 7-11

The question was posed in terms of tuck-shop coupons, but this problem is classically stated in terms of postage stamps. Essentially,

What is the largest number which cannot be expressed as a sum of 7's and 11's?

Consider a different (but related) question: If we have an amount that is possible, how can we increase it by one? Since there is no one-rupee stamp, we would have to trade some appropriate combination of stamps to accomplish an increase. Add a few whose sum is N, take away a few whose sum is N-1. It is also worth mentioning that the trade will only be 7's for 11's or 11's for 7's. We will not have to worry about some complicated mixture. (if we gave a 7 and received a 7 we could ignore the 7 in both cases and accomplish the same change).

The problem becomes: can we find the smallest multiple of 7 which is one less than a multiple of 11? Or, can we find the smallest multiple of 11 which is one less than a multiple of 7? Take 3*7=21, which is one less than 2*11=22. Also, 5*11=55, which is one less than 7*8=56.
What this means is that to take an amount which works and increase it by one, we can either trade three 7's or five 11's. If either of the two options is available to us, then the next amount can be expressed in terms of 7's and 11's.

The amounts which do work but cannot be increased are those numbers which are the sum of fewer than three 7's and fewer than five 11's. The largest of these numbers will have two 7's and four 11's; 2*7+4*11=58 is therefore the largest number which cannot be increased, which means that 59 cannot be constructed as a sum of 7's and 11's. The next number, 60, can be made (with one 11 and seven 7's), so every number greater than or equal to 60 can be made with 7's and 11's.

Therefore 59 is the largest number which cannot be expressed as a sum of 7's and 11's.

Thursday, March 26, 2009

prisoner's dilemma

This article was mentioned on the Freakonomics blog. DNA evidence collected from the scene of a jewelry robbery in Germany was matched to two people, identical twins with indistinguishable DNA. Because the evidence failed to incriminate one particular person, both brothers were released. Of course, between the two of them, they probably know which one did it (if either of them did).

The Freakonomics post about this situation alludes to the prisoner's dilemma, which I actually have been pondering lately. Not because I'm a prisoner, but because I read another chapter in my intro to game theory book while grading tests a few nights ago.

The prisoner's dilemma goes like this.

Two prisoners are held in connection with a crime. They are not able to communicate to one another. Each is given the opportunity to confess, with the understanding that the sentencing will occur as follows:

  • If one talks, he goes free and the other gets a maximum sentence (because there is evidence against him).
  • If both talk, they each get a usual sentence. (evidence against them, but less for cooperating).
  • If neither talks, they each get a minimum sentence. (not enough evidence for a conviction).

The outcomes can be arranged in a matrix as follows, showing how many years each prisoner gets as a result of each of the four outcomes:

B talksB doesn't talk
A talks A:10, B:10A:0, B:20
A doesn't talk A:20, B:0A:5, B:5


Here is the tricky part, as seen by Prisoner A (B's considerations are the same). Prisoner A is trying to make a rational decision with the sole intention of serving the least amount of jail time possible. Prisoner A knows that if B talks, A should talk (to get 10 years instead of 20). If B doesn't talk, A should talk (to get 0 years instead of 5). So while the outcome is uncertain, the strategy is clear. Prisoner A should talk, no matter what B decides.

Likewise, Prisoner B would be better off talking, no matter what A decides. Therefore, they will both be rational and talk. They will each serve 10 years.

The intriguing facet of this situation is that there exists an outcome which is better for both prisoners (they both stay quiet and each serves 5 years), but which would involve each of them acting irrationally. Of course, if their decision were made to avoid jail time, it could hardly be called irrational. That's the catch-22.

At a glance, it seems like a clever illusion and it is tempting to think that after considering the outcomes, each prisoner would be silent and thereby obtain the most favourable outcome available: 5 years and 5 years. But remember that the only reason a prisoner would be quiet is if he were confident that the other prisoner would also be quiet. And if he were confident of that, would he really pass up the chance of immediate freedom?

This leads to a mathematical discussion of why we do not see more cooperation in the world. The best outcome for everyone is usually necessarily artificially imposed or it will not happen.

My simplified rendition assumes that both prisoners are equally guilty and know that they would be convicted by the other's testimony. It also assumes that they do not like being in jail. Honor among thieves could certainly keep them quiet if the jail time were a matter of days, but as the sentence gets more substantial, the reward for informing on the other prisoner grows considerably, in addition to being the only rational choice. This means that the relative magnitudes of punishments and temptations come into play. Here is a more lengthy discussion of the dilemma that explains some of the variables.

solution: base b & b+3

The number n expressed in base b has the form 364. In base (b+3), n is written as 202. Find the decimal values of n and b, which are both positive integers.

Solution:
Without knowing the base, we cannot know the number which is represented by the symbols 364. The place-value system allows us to perceive it as a number having a one's place, a b's place, and a b2's place, just as a three digit decimal number would have a ones' place (100), a tens' place (101), and a hundreds' place (102).

Therefore n=3*b2+6*b+4
and n also equals 2*(b+3)2+0*(b+3)+2

so we have

3*b2+6*b+4=2*(b+3)2+0*(b+3)+2
3*b2+6*b+4=2*b2+12*b+18+2
b2-6*b-16=0
(b-8)*(b+2)=0

so b=8 or b=-2. The problem says that the base is positive, so we take b=8. Once we have found b, we can put the value into either equation for n. We get b=8, n=244.

In this problem, I offered the students an easy base that they could find by trial and error. Several students noted that since 364 contains a "6", the base had to be at least 7, a very astute observation. Also, when you solve the quadratic, you get only on positive option.

If the quadratic equation had two positive roots, we could find a number n which had the given representations (for bases b and b+3) for two different values of b. If the base b representation was four digits, there could be as many as three distinct values of b that could solve such a problem. If the base b representation was six digits, we would get a fifth degree equation, which Abel says cannot be solved for the five different b's that could exist.

Monday, March 23, 2009

another rock in the wall


This is a wall we saw in the granite ruins of Hampi in South India. The wall surrounds part of the royal complex. It is hundreds of years old and probably thirty feet tall. You can tell that they got tired of hoisting the big ones as the wall grew taller.

5-star challenge #4

Grades 11 & 12 5-Star Challenge #4
Captain Cooke the buccaneer buried his treasure at a small Himalayan boarding school. His legendary love of mathematical riddles inspired him to leave this clue, enigmatically encoded in the arrangement of 216 enormous stainless steel cuneiform characters in the school’s Peace Garden:

"The treasure is below Handsome Field. Start at the pile of broken tube-lights. Walk straight to the rock that looks like a flower, counting your steps. Turn 90 degrees to the right and walk the same number of steps in that direction. Put a twig in the ground where you stop. Start again at the pile of broken tube-lights and walk directly to the flower that looks like a rock, counting your steps. Turn 90 degrees to the left and walk that number of steps in that direction. Stick a twig in the ground at that point. Tie twine tautly 'tween the twain twigs and find its halfway point. The treasure is buried beneath the midpoint of the twine."

Centuries later, the clue is discovered by a visiting alumna as she ponders the 5-Star Challenge #971. After decoding the directions, the alumna rushes down to the Handsome Field Coliseum (via the Class of 2009 Memorial Escalator) to discover that the flower and the rock are still inexplicably in their places, but the pile of broken tube-lights has been removed without a trace by CLEAN! Without knowing where the broken tube-lights should be, and without digging at random all over Handsome Field, is it still possible for the alumna to find Captain Cooke's treasure? Explain.

Grades 9 & 10 5-Star Challenge #4
Point A is 6 units from the center of a circle of radius 10. How many chords of the circle have integral length and pass through point A?

Sunday, March 22, 2009

5-star challenge #3

Grades 11 & 12 5-Star Challenge #3
The number n expressed in base b has the form 364. In base (b+3), n is written as 202. Find the decimal values of n and b, which are both positive integers.

Grades 9 & 10 5-Star Challenge #3
The new tuck-shop coupons are printed only for 7 rupee and 11 rupee denominations. What is the largest integer number of rupees which cannot be paid using a combination of 7- and 11- rupee coupons?

Tuesday, March 17, 2009

solution: pair-sums

Grades 9 & 10 5-Star Challenge #2
Every possible pair within a set of five numbers is summed.
The sums are 0, 3, 11, 12, 20, 21, 23, 29, 32, 41. Find the five numbers.


In this problem, the answer may be obtained by trial and error, but there are some neat aspects to the problem if one works to solve it. Let us assume that the five numbers are distinct (as they would need to be if their ten pair-sums were distinct). Let us consider the sums as F < G < H < J < K < L < M < N < P < Q. Let the five numbers be a < b < c < d < e. The order of a, b, c, d, and e offers only an incomplete understanding of the order of the sums. We have

(a+b) < (a+c) < [(b+c),(a+d)] < [(a+e),(b+d)] < [(c+d),(b+e)] < (c+e) < (d+e).

We know that F=a+b and G=a+c, and that Q=e+d and P=c+e. We do not know if the third and fourth smallest sums represent a+d and b+c or b+c and a+d, respectively.

This problem can be approached by solving all of the little equations to establish which is greater of (b+c) and (a+d). Once b+c is known, the system of three equations a+b=F, a+c=G, b+c=(H or J) can be solved for the values of a, b, and c. The values of d and e can be found shortly thereafter by substitution.

There is a less tedious way to solve the problem. By identifying that each number is summed with each possible partner, we know that each number a < b < c < d < e appears four times in the sum F+G+H+J+K+L+M+N+P+Q, so the sum of the ten pair-sums must be equal to 4(a+b+c+d+e). By adding the first and last sum, we know that F+Q=a+b+d+e, and we can therefore find the value of c.

In our problem, the pair-sums are 0, 3, 11, 12, 20, 21, 23, 29, 32, 41, whose sum is 192, which is equal to 4(a+b+c+d+e). This means that 192/4=48=a+b+c+d+e.

We know that F+Q=0+41=a+b+d+e, so c=7.

If c=7, we know that G=3=(a+c)=(a+7), so a=-4. Then F=0=(a+b)=(-4+b) tells us that b=4. P=32=(c+e)=(7+e), so e=25. Since 48=a+b+c+d+e, d must be 16.

solution: 81^2009

Grades 11 & 12 5-Star Challenge #2
Find (a) the number of digits and (b) the last three (least significant) digits in the decimal expression of 812009.


My Solution...
This problem asks for two elementary observations. If the number were written in its entirety, it would be a simple matter to obtain the number of digits and the values of the last three digits. The entire number can be generated with a couple of lines of code using Java's BigInteger class.

BigInteger myBigNumber = new BigInteger("81").pow(2009);
System.out.println("myBigNumber: "+myBigNumber);

This returns (in a fraction of a second):

myBigNumber:

1400886426099001433589715356524325994077360058833291454060331448901202858812711608791505300540205160834871243114967077782896741018493232826119962265403933221408273710682285389474611581003628765532988693839153728368550209031963049953365587333165550684382285106676049916357515617508318430039472665058505400648134895508543610798780057273663322426956561416111481073295564688756106556978220972883768498990439376379038088913512578774433394954966862795937723871349150451305665824022155706009283754336379201724142185351446653196901336911382788170275693693431585571516214076703025655694724313935072160077237502277620633564638041394172823865006761057098692874958064119778303667684220473562875130389095576612598169616570264206698883864712941599975306460033566903701203176613915280808200553190149220172757742382552424264898048660485008953744755857351182328200797217390733117879482736723725387755343016641042324605268387235071317590044699322617486518833978498750446720283318797784379982099655399049514088697411493542735966238355231518335754560005454557858737827355594203256731113150254221184261378594118900660565386875397480998177808153453972240763137726201802935458465644187508973316810617828944777550600037116120613295523595674229092486855978909224433568001602101966137609851452418351933395026445713151813690775772659529245247483081061394734160452917273402957713927998398637008649959045364542625757251174939330779763645565078645414995355444331511328545544587436720247358813300136273063929536760693736894399092656898581391777601176686638814415800605457552137755811561722992947830941361575088520921316840670291945199828480758662688749076445628397158944252925926207253727397615642302175056456168537654926096910594424358310081741719763482063248026418549153981883499716627174273667624458356479660732203553476892308402043990264919201939021708092767869280613832259386192559262656045967546526551060223597953426164586528815240198370930615443469369831397836790511704027247717287613128262970900587798085687044826070427586179676392059739626595037167328563772506422713580328669959080751912111426766214386993833793411310032618393156947481034604475623258966648528615807295339485106694016473355821675133837209206523909378952991095736019452549069793468232090700893085918364572584074859059077156795322914743377215102376435931960712370356874666922951857034687294703109308613860715556328236763180084679159342631746367233847114542831918603472299798321527157441161819532742005968777296078987636685014605803610522533976135083018079462867231622504340685958958775803013385058237912087337518155851768194473603085161979303255925564896683534521901491172404855277443706334679904563837822732299389135616888785840527710491760378625577274127165160723696855383968993354486834189433444754952751349119445485023181677760092071751879339708391793177141272161381338406604416686619826676210135423387944224584209170249358763128906780988581499912792718505330714538446491560748113617647828696553112964608607567406647137734043006583685118169281006120091135549995534312849407690524527234325455560291603364366173667248135691235606237319206864662357808314487913529150433701250314479681846670702891523598161060942612992920037173624206384607196996451365525196548440267693551682140725599199807911935490733624764556262308015951473144301853801136043280112830549607313441641080796896809627284910178979983295107307002907330430332271237131267427131349236806228355581537700780297380111225674100174944973118017202128990296866935839828010719361300152001055622795047713257519014364284326307078184203112517839087782402492861653020274288404432905972207465665985433591495473890988412099059297644788913887941133672356210069355051778825969788920325814207846046437928268923946341521305003727054700978419670287048809561516312934357723512398670440769027697003378905339200718030813912207894907559735934856589959121

Of course you could count the digits by hand or write a couple more lines of java to find the number of digits, or use the character count in a Word document. Each of these processes is admirably resourceful, but disregards a lurking elegance. I would not object to such a direct approach to the problem, but there is certainly room for some more finesse. The sheer size of the number renders useless more accessible tools like calculators and spreadsheets. Microsoft Excel has pitiful accuracy, and the students quickly find out that they cannot even use their TI calculators to find the number of digits (directly).

To find the number of digits, we need to remember that we mean 'decimal' digits. The relationship between exponents and the number of digits is clear if the bases agree. Our number, 812009 can be written as 102009*log81=103834.146..., which must be a 3835 digit (base 10) number, as it is situated between 103834 (which is the smallest 3835-digit number) and 103835 (which is the smallest 3836-digit number).

The last three digits present more of a challenge (barring the availability of the number in decimal form). The last digit, one may easily observe, is 1.

As in the first part of the question, there is a simple shortcut that most would fail to find, but a few would anticipate or discover. The last three digits of the powers of 81 progress through a repeating pattern. This is because 8125=515377520732011331036461129765621272702107522001. The important part is that the last three digits of 8125 are 001, which means that when we multiply by 81 to get 8126, we will be back at 081 for our last three digits, and we will go through the progression again for every 25 factors of 81. By this, we can conclude that 812000 will have 001 as the last three digits, so 812009 will have the same three-digit ending as 819, which is 121. This idea can be used within Excel, but even 819 is beyond the precision, so it is necessary to discard the more significant digits, through a formula like:

A2=MOD(A1*81,1000)

which gives the last three digits of the next power of 81. The calculation is always manageable for Excel, and the values never get larger than 3 digits. I do not expect my students to know about modular arithmetic, but the problem certainly supports that type of finding.

A basic high-school-math-with-scientific-calculator method for solving this problem involves the binomial theorem, and I think is very clever.

If we write 812009 as (80+1)2009, we can expand it using the binomial theorem as:

(2009C0)802009*10
+(2009C1)802008*11
+(2009C2)802007*12
+...
+(2009C2006)803*12006
+(2009C2007)802*12007
+(2009C2008)801*12008
+(2009C2009)800*12009

Notice that most of the 2010 numbers in this sum end in 000. Any time the exponent on 80 is at least 3, the number will have 1000 as a factor. This means that the last three digits are entirely determined by the terms (2009C2007)802*12007, (2009C2008)801*12008, and (2009C2009)800*12009, which are:

12909030400
160720
1

...and whose sum ends in the digits 121.

This method is more general in that it does not rely on the discovery of a cycle (which may be very long for some bases) or the access to a computer brute-force approach.

Saturday, March 14, 2009

pi day!

Happy π Day!

5-star challenge #2

Grades 11 & 12 5-Star Challenge #2
Find (a) the number of digits and (b) the last three (least significant) digits in the decimal expression of 812009.

Grades 9 & 10 5-Star Challenge #2
Every possible pair within a set of five numbers is summed. The sums are 0, 3, 11, 12, 20, 21, 23, 29, 32, 41. Find the five numbers.

Wednesday, March 11, 2009

solution: circles


This problem is fairly straightforward with a correct diagram. A hastily sketched diagram may not accentuate the relevant details. Segment ED is 25 units in length. The length of segment BC is 24 units. (how do we know?) To find the length of the altitude to A of triangle ABC, go 9/25 of the way from 9 to 16. Then you have the base and height of a triangle. The area comes to 138.24 square units.

The problem became more interesting when I tried to construct a diagram. A drawing will suffice if you know, for example, that the radii should be perpendicular to the tangents. The construction of a tangent to two circles (but not at their shared point) took me a few minutes to contrive. Also, triangle ABC is a right triangle for any two circles (if we do not keep the radii to 9 and 16) which are tangent in this way. (why?)

My students are always disgusted to learn that I do this stuff for fun.

This problem came from the Georgia Tech Math Olympiad Sample Test.

solution: vases

Solution: The greatest number of heights that could be tested with certainty is 91.

If only one vase was available, we would have to begin at 1 foot and proceed upwards by 1 foot increments. If we skipped a height and the vase broke, we could not be certain that the maximum survival height was the last drop survived or a height which was skipped. If and when the first vase breaks, the problem will become a one-vase-scenario.

If two vases are available, we do not at first need to drop from consecutive heights, but we must choose a strategy which allows us to test the intervening heights between the first failure and the previous success.

With two vases, therefore, we can spend our first drop at 13 feet, knowing that we have 12 drops left with which to determine (in case of a failure), which of the heights 1-12 was the maximum. If the vase sustains a drop of 13 feet, we have 12 drops left and we should make our next drop from 25 feet, knowing that we will have 11 drops (in case of a failure) with which to determine the maximum that may be anywhere from 14 to 24.

Therefore, we can skip the first twelve heights, testing at 13. Then we skip the next eleven, testing at 25. By continuing this method, we can determine with certainty the safety of 91 different heights.

We plan to test at:
13 ft.
25 ft. (13+12)
36 ft. (25+11)
46 ft. (36+10)
55 ft. (46+9)
63 ft. (55+8)
70 ft. (63+7)
76 ft. (70+6)
81 ft. (76+5)
85 ft. (81+4)
88 ft. (85+3)
90 ft. (88+2)
91 ft. (90+1)

The winning student discussed 3, 4, and 5 vases. There would be a maximum, of course, if you had 14 vases and 13 drops, you would not benefit from the fourteenth vase.

Robert suspected a twist (in the comments for the question post) such as counting the first part of the fall. For example, if you drop a vase from 98 feet, it may smash at the end but it will safely fall 97 feet. However, a drop from 97 feet may also be fatal (in which case you have spent both of your vases and very little has been learned).

Friday, March 6, 2009

5-star challenge #1

I am trying to start a weekly math contest at my school. I have enjoyed the task of finding problems to use. This contest finishes today for my students, so I will pass on the questions for your own enjoyment. There is no prize but the dignity and warmth that comes of mathematical triumph. I will post answers in the comments when I have the time and inclination.

Grades 11 & 12 5-Star Challenge #1

Mr. Burchell has two identical vases and he wants to know exactly how far such a vase could fall without breaking. The vases may be fairly robust. With no more than 13 drops from integer heights (in feet), what is the greatest height (in feet) which could be determined with certainty as the longest drop which such a vase could survive (without breaking)? That is, beginning at 1 foot, what is the greatest number of heights which could be proven safe for the vase?

Grades 9 & 10 5-Star Challenge #1

Circle P with radius 9 and circle Q with radius 16 intersect only once, at point A. A certain line is tangent to both circles, touching circle P at point B and circle Q at point C. Find the area of triangle ABC.