The title question would be a medium level math contest problem.
The following could be the SAT version:
369121518...99
The integer above is formed from consecutive positive integer multiples of 3 from 3 to 99 inclusive. What would be the 50th digit in this number?
A student could theoretically take the time to list all the digits up to the 50th, however, this would be more time consuming than using logic.
Possible approach for SAT-type:
369 uses 3 digits.
This leaves 50-3 = 47 more digits.
Starting with 121518... there are two digits for each multiple of 3, so we divide 47 by 2, producing 23 with remainder 1. We now need to determine the 23rd multiple of 3 beginning with 12:
12 + (23-1)3 = 78. [At what point should students know this formula for arithmetic sequences?]
The remainder of 1 means we need to look at the first digit of the multiple of 3 that comes after 78: 81
So the answer would be 8, but, of course, I could have erred in my logic or calculation, so pls check that!
One could now assign the title problem for extra credit or as an extension.
Comment: How many readers believe that middle schoolers on up tend to rely on their calculator to find remainders. This has been discussed previously on this blog and a couple of algorithms were given for computing the remainder from the decimal result given by the calculator.
Saturday, April 5, 2008
In the long integer 36912151821...9999, what is the 1107th digit?
Subscribe to:
Post Comments (Atom)
Posts
13 comments:
And, the advanced mathematical subject to be discussed here is the Bailey-Borwein-Plouffe [BBP] algorithm for computing arbitrary hexadecimal digits of π. Again, use Mathworld or Wikipedia.
That we can know the quadrillionth hex digit of π without needing to compute all the previous ones and being able to take only a short amount of time is amazing.
SAT problems are important, but let's not lose site of what mathematics is.
Eric--
I've become very aware of that extraordinary algorithm, a bit more sophisticated than my problem!
Eric, I use SAT problems as vehicles for encouraging higher-order thinking and problem-solving techniques. There is certainly far more important math beyond SAT and math contest problems, but, at the same time, there is much rich mathematics for our students embedded in many of these questions. I often use SAT questions as springboards for deeper investigations. Besides, students whose SATs are only a few weeks away might be interested in using some of these for training purposes. There is no substitute for experience...
We now need to determine the 23rd multiple of 3 beginning with 12:
12 + (23-1)3 = 78. [At what point should students know this formula for arithmetic sequences?]
Although we touched on that formula when playing with Gauss' method for summing arithmetic sequences, middle schoolers (except those studying for contests) generally don't know this. I don't think it's taught before Algebra II (if then).
However, I wouldn't use that formula in this problem anyhow. It is much easier (imho) to see that you can fit 23 2-digit multiples of 3, plus the three 1-digit multiples of 3, into the first 49 digits. Thus what we want is the first digit of the 27th multiple of 3 (starting from 3) which is clearly 3 x 27 = 81. (Then taking the first digit, we get 8 as the answer to the question.)
Mathmom,
I agree that it far more instructive for middle schoolers to use your 'constructive' approach and logical reasoning before being fed some 'canned' formula. I only did that to raise the question of when students should be shown this highly useful relationship. I would argue that Algebra I students need to see this when learning linear functions. Further, one could develop it earlier, for example, when asking students what the 100th positive odd integer is.
I believe your students could begin to construct the formula for themselves if the pattern is developed as follows. Let's say the first term is 5 and each term after that is 4 more than the preceding term:
1st: 5
2nd: 5 + 4⋅1
3rd: 5 + 4 + 4 = 5 + 4⋅2
4th: 5+4+4+4 = 5 + 4⋅3
...
There are so many applications of this basic formula that I believe it should be introduced much earlier than Alg II:
Becky has $40 in savings and saves an additional $8 per week. After how many weeks will she able to buy a $160 video iPod?
By the way folks, I encourage someone to try the title problem in the post -- there might be a surprise ending!
Since we're dealing with the number 3 it's easy
to figure out what the first and last k-digit
multiple of 3 is. From this we get the ammount
of k-digit multiples of 3 in n, as well as the
digit position of these multiples of 3 in n.
k=1: There are 3 1-digit multiples of 3 (3,..,9)
Note: Taking up 3 digits in n.
k=2: There are 30 2-digit multiples of 3 (12,...,99)
Proof: (99-12)/3 + 1 = 30.
Note: Taking up 2*30 = 60 digits in n.
k=3: There are 300 3-digit multiples of 3 (102,...,999)
Proof: (999-102)/3 + 1 = 300,
Note: Taking up 300*3 = 900 digits in n.
k=4: There are 3000 4-digit multiples of 3 (1002,...,9999)
Proof: (9999-1002)/3 + 1 = 3000
Note: Taking up 3000*4=12000 digits in n.
Now we need to find out which multiple of 3
sits in the 1107th digit.
The first 963 digits of n are taken by the 1-,2- and
3-digit multiples of 3. This leaves us with 144 digits
that we need to look at:
1107-963 = 144
Divide by 4 to find out which 4-digit multiple of 3 we're looking for:
144/4= 36
Now find out what the 36-th 4-digit multipe of 3 is:
999+36*3 = 1107
Therefore the 1107th digit of n is 7.
Nice analysis, Eric.
I thought it would pique someone's curiosity why I chose 1107...
Aside: I've been asked by a family friend to come up with a winning strategy for a variation of NIM.
2-players...
Start with one pile of 15 counters. Players alternately remove 1,2, or 3 from the pile accumulating their own piles. The game ends when the last counter is removed. Here's the twist:
The winner is the one who has accumulated an ODD number of counters. Devise a winning strategy.
I tried the usual techniques, forcing the remaining number of counters to 11, 7, then 3. But I was not able to finish it. Any ideas? This is kind of a reverse NIM game.
Dave, I agree that they could develop the formula. I have them do that, but not as a formula to memorize, just as a formula to use for a given problem -- a "function machine" find-my-pattern kind of thing. I think having "pre-existing" formulas at the middle-school level is bad. The kids forget them, misuse them, etc. At this point, I'm all about the thinking skills. Find the pattern. Construct a formula. Then plug it in. Takes more time, but they're at least accurate when they do it this way. Otherwise, forget it.
Florian--
Pls accept my apology for missing your name in the excellent solution you posted to my problem!
BTW, did you have a chance to consider the NIM problem that I mentioned? Your CS mind will probably devise an algorithm better than I could.
Mathmom--
As usual, I agree. I am opposed to rote memorization of formulas without comprehension. However, when a particular pattern appears often enough, some kind of abstraction (be it verbal, symbolic or visual) does enter long-term memory. A reasonable percent of your students may already have memorized the expression for the nth term (or for the amt. of savings after n time periods, etc.). It's not a bad thing to have in one's toolbox, particularly if a few of them will be taking SATs in 7th grade.
Thanks Dave! The game was a really good challenge!
Say we have players A and B. After each turn a =
#counters A took and b = #counters that B took.
The number of counters c = 15. (Note: The following
strategy actually works for any c= 3 + 4x where x>4)
If A starts, B has the following winning strategy
(which he applies after each turn of A):
CASE a =< b: IF (b-a) mod 3 = 0 THEN "take 3 counters" OTHERWISE "take 1 counter"
CASE a > b: IF (a-b) mod 3 = 0 THEN "take 1 counter" OTHERWISE "take 3 counters"
What makes finding a winning strategy tough is that that the winning
player needs to force the opponent to have an odd number of counters
when the remaining counters on the stack = 4 (more on this in a second).
This means controling two properties (oddness of a and remaining counters
on the stack when A has his turn).
I started out analysing those cases where the remaining counters r=1,2,3,4:
Since c is odd =>
1. If r is odd => A is odd and B is odd OR A is even and B is even.
2. If r is even => A is odd and B even OR A is even and B is odd.
Lets checkout what happens when r=1,2,3,4:
r=1:
Whoever is on the draw and has even wins (must take 1)
Whoever is on the draw and has odd looses (must take 1)
r=2:
=> A and B are not both odd or even.
=> Whoever is on the draw can win!
r=3:
=> A and B are both odd or even.
=> Whoever is on the draw can win!
r=4:
=> A and B are not both odd or even.
Whoever is on the draw and has even wins (by taking 3 => r=1)
Whoever is on the draw and has odd looses
(This is the same situation as r=1)
So in order to win, B needs to force r=4,a=odd,A's turn or
r=4,b=even, B's turn.
B wins by making shure that if a and b are both odd or even then b
becomes odd otherwise b becomes the opposite of a (odd or even).
What happens then is that the counters get taken from the stack
in a way that alternates the odd'ness and even'ness of a and b
every 3 removed counters.
I hope that made sense to you :)
Correction: It works for any c=3+4x with x>1 (not x>4)
Florian,
Thank you for that detailed analysis. You certainly thought far more deeply about this than I did! It turns out to be more complicated than I imagined but your solution makes sense. I just need to work through each case carefully.
Thanks again!
hello
have someone manage to develop nim game in matlab?
thanks a lot
Post a Comment