Looking through the
Gazette of the Australian Mathematical Society, and found their puzzle corner (July 2009 , so the exponents in the first problem are explained) ... really nice problems.
I think I have this one, but I didn't prove it....
Digital deduction
The numbers 2^2009 and 5^2009 are written on a piece of paper in decimal notation.
How many digits are on this piece of paper?
And this one has me puzzled (which is why they call them puzzles, I guess)..
Piles of stones
There are 25 stones sitting in a pile next to a blackboard.
You are allowed to take a pile and
divide it into two smaller piles of size
a and b,
but then you must write the number
a×b on the
blackboard. You continue to do this until you are
left with 25 piles, each with one stone. What is
the maximum possible sum of the numbers written
on the blackboard?
Anyone know how to a) prove the first, or b) solve the second...
Do let me know....mostly down to chewing my pencil tips now....
Spoiler (I think)
x
x
x
x
x
x
x
OK, I think the total for the 25 stones will always be 300... I tried it about three different ways and they all came out the same... hmmmm... In fact, if we look at some smaller numbers for a guide, it seems that for any n, the sum of the products by this process will lead to $\dbinom{n}{2}$...
now why is that?
Anyone, Anyone??? Bueller?
19 comments:
Hmm, the second seems easier to me. But maybe I'm missing something. I think I've solved it. Not sure if you want solutions here.
Just checking the rules of the game: If my first split is to 20 and 5, then I get 20x5=100 'points', and I'll keep adding points by splitting piles until I get all piles of 1.
(I haven't proved my solution is the best sum, but I'm pretty sure it is.)
The first one *looks* like it's going to be n+1, but I don't see why it has to stay that way.
Sure I want solutions.. and the proof if you have one.. My fist thought was that since the largest product possible when breaking n into two parts is (n/2)^2 I would break it into the biggest parts possible, 12x13 first for 156 then break the 12 into 6x6 and the 13 into 6x7 but I don't know for sure if that will be the largest sum, because the other way 1x24 etc would give more numbers... so I'm still tinkering..
That was my thought at first too.
• Split into 12 and 13: 12x13 = 156 'points'
• 6x6 and 6x7 = 36+42 points
• 3x3, 3x3, 3x3, and 3x4 = 39 points
• 1x2 (7 of those) and 2x2 = 18 points
• The nine 2s become pairs of 1s = 9 points
That all adds up to 300, but doing this made me suspect that 3's are no good. You get a 1 too soon. If I want as many 2's as possible, then I want as many 4's as possible, and then I want 8's, etc. I also want the first split to be as close to even as possible. So I tried 16 and 9. And my total goes up to 312.
(First split of 17 and 8 gets 300. Hmm, a bunch of different ways all get 300 as their total.)
I haven't proved there's no higher total, but I feel pretty sure 16 and 9 getting 312 is the max.
Dang! Never mind. 16 and 9 gives 300 also. I'm beginning to think any split gives 300. My hypothesis at this point is, given a number n, all ways of playing the game for n give the same score.
When I looked at 2^2009 and 5^2009 I immediately thought of 10^2009 as an upper limit -- 2010 digits. Then I cheated and used PARI/GP to compute the number of digits in 2^2009 and 5^2009 (605 and 1405, respectively, which does in fact add up to 2010).
But how to PROVE that this works out exactly in general? 9^2009 and 9^2009 multiply out to 3835 digits, but they add to 3836 digits.
But how do you prove it works
(Sorry, hit publish before I was done editing -- ignore the last line "But how do you prove it works")
The number of digits in a number, n, is ceil(log_{10}(n)), where ceil is the ceiling function (next biggest integer). If you are thinking about the number of digits in a power, n^p, log rules come in handy. The number of digits is ceil(p*log_{10}(n)).
For the problem at hand, the sum of the digits of 2^p and 5^p, that means the answer is ceil(p*log_{10}(2))+ceil(p*log_{10}(5)). Now log_{10}(2)+log_{10}(5)=log_{10}(10)=1. I claim that if m is any integer, and x and y are two real numbers with x+y=1, then ceil(mx)+ceil(my)=m+1. This will prove the conjectured answer to the problem.
Suppose x+y=1, so that y=1-x, and m is an integer. Let mx=n+f where n is an integer and 0<f<1. Then ceil(mx)=ceil(n+f)=n+1 and ceil(my)=ceil(m(1-x))=ceil(m-mx)=ceil(m-n-f)=m-n. Therefore, ceil(mx)+ceil(my)=(n+1)+(m-n)=m+1, as claimed.
I like the second problem. I'm looking forward to playing with it some more, and reading what you all come up with as well.
Ok, I think I got the second one too. I've been playing around with the python programming language recently, so I wrote a little script to work out all the splittings of numbers up to 25, and see what all the different splittings give as a final answer. And, as conjectured above, the final answer seems to be independant of what the splitting was. Looking at small starting values, say 3, 4, 5, instead of 25, I conjectured that the final answer, starting with n, is the (n-1)st triangular number, (n-1)*n/2. Once that conjecture is made, it seems fairly straightforward to prove the claims by induction.
But if the answer is triangular numbers, there's almost certainly a picture involved, right? I think there is. I don't want to try to write down a formal way to do it, but here's an example. Start with 7, split it as 4+3. Then split 4 as 2+2, and 3 as 1+2. Finally, split all of the 2s into 1+1. The products I record can then be pictured graphically:
* * * | * * | *
| |
* * * | * * |
|------
* * * | *
|
* * * |
-------
* * |
-----
*
I know that graphic comes out terribly here. Copy and paste it somewhere where you've got fixed-width characters, and hopefully it'll make more sense.
Pat, Thanks for these problems, I'm loving thinking about them! I couldn't sleep for a while, and these were much better companions than my usual nighttime thoughts.
Problem 1 first:
sumidiot, you helped me get there with logs. But you have an error: "I claim that if m is any integer, and x and y are two real numbers with x+y=1, then ceil(mx)+ceil(my)=m+1."
I had trouble following that when I read it last night. The way I did this problem was a bit different, but it helped me see that you can't use just any reals above. If x and y each equal 1/2, and m =2 then mx=my=1 and you'll have 2=3 above. x and y must both be irrational for your claim to hold.
I learned something pretty cool last night at about 3am, because I would not have thought proving something is irrational would be easy.
Here's how I did it:
First, I wanted to understand how logs go with digits. Any 2-digit number is between 10^1 and 10^2, so has a log of 1 point something. So an (n+1)-digit number has a log of n point something. Taking ceiling of the log gives the digits. (Except that 10 itself has log 1, and ceiling would still be 1, not the required 2 for its 2 digits. But we know that neither 2 nor 5 to an integer power can = 10 to an integer power. So we know we don't have to worry about the integer powers of 10.)
Now 10^n = 2^n*5^n, and taking logs gives us n = log(2^n)+log(5^n). Because neither 2^n nor 5^n can be a power of 10, these logs are not whole numbers.
If you took only the integer parts of the logs, and added, you'd get n-1, using the ceiling instead, you get n+1.
digits in 2^n = ceiling(log(2^n))
digits in 5^n = ceiling(log(5^n))
adding gives n+1, so we have n+1 digits.
Solving the problem was fun, but proving to myself that log(2) is irrational was more fun. Proof: If log(2)=a/b, then b*log(2)=a, then log(2^b)=a, then 10^a=2^b, which is not possible. This proof held because 10 and 2 are not both integer powers of some common base, and can be extended to any two numbers with that relationship.
Problem 2:
We can prove this. And it may be the first time I've used proof by induction on a problem I was really solving on my own.
I want to call the total sum in this problem the points, and write P(25)=300. (To make P(n) well-defined, I should say it's the maximum possible points, so I don't really know yet what P(25) equals, but I'm going to be sloppy and use it as the sum for any splitting sometimes.)
Just like sumidiot, I saw that it was much easier to calculate these for smaller numbers, and turned to induction. It was clear that if you peeled off one stone each time, you'd get P(n)=(n-1)+(n-2)+...+2+1 = (n-1)n/2.
The problem is proving that you always get that result no matter how you split. 2 can only split to two piles of 1, and 1*1=1, so P(2)=1. 3 can only split to two piles as 2 and 1, 2*1=2, now split the 2, so P(3)=2+1=3. 4 can split two ways. If we let P(1)=0 since 1 can't be split, then we can write P(4)=3*1+P(3)+P(1)=3+3+0=6 or P(4)=2*2+P(2)+P(2)=4+1+1=6.
In general P(n)=(n-x)*x+P(n-x)+P(x).
Using induction, we can assume P(n-x) and P(x) are as given above, so we get P(n)=(n-x)*x+(n-x-1)(n-x)/2+(x-1)*x/2 = 2x*(n-x)/2+... = (2xn-2x^2+n^2-2xn+x^2-n+x+x^2-x)/2 = (n^2-n)/2 = n(n-1)/2 QED
That looks awful the way I wrote it. If you get my description, you can do that last part yourself. ;^)
Pat asked "Now why is that?" at the end of her post. I don't think induction is very good at answering that question. I'd love to understand your diagram, sumidiot, but I'm lost. Can you help me?
Thanks, Sue, for pointing out my mistake with the mx and my business. I had used that mx was not an integer so that my f wasn't 0. But as you point out, that need not be the case in general. Of course, since you prove that the x I use (log(5)) is irrational, my argument still works in this case :)
I'll try to come up with some nicer picture. I may end up posting them on my blog, for convenience, but I'll post a link here if I go with that option.
Ok, perhaps the picture here helps. I took 10 as my starting number, and on the left I traced out how I was going to split it up. Then on the right, I draw rectangular boxes of the appropriate size for the products we're supposed to record in the process. So my first split is 10=7+3, so I record a 7 by 3 box.
I've tried to use some sort of systematic approach to drawing this (though I think it might not matter much). I write each split as A+B where A >= B, A in blue, B in red. For splitting a blue number, I use blue arrows (and blue sides of rectangles), and red similarly. Since there are several 2=1+1 splits, I circled some with their own color, and used that same color arrow to highlight the part of the diagram.
I don't know if any of that made sense...
Sumidiot??? some idea... Very nice
I count digits with floor(log_b(n))+1. It covers all cases, including integral powers of b.
Thanks, Sue and doctorbinary for patching up my logs to count digits. Off by one occasionally... silly me.
For the first problem, I think the log approach is the best.
The second problem I have seen many times in books as a strong induction exercise, but ... WHY does it come out the triangular numbers?
Well, the triangular numbers are the solution to the handshake problem.
When all the pebbles are in one pile, let them all shake hands.
At each splitting step, the number of points you score is equal to the number of handshakes you destroy.
At the end, you have all the pebbles in their own individual pile, so there are no more handshakes possible - they have all been destroyed.
Hence the score is equal to the initial number of handshakes.
Joshua,
You ARE the math man... perfectly clear...why don't I see things like that...
thanks..
I may write one more blog about this to make that clear to students, explained as complete and bipartite graphs...
Post a Comment