Morris: OLD IDAHO USUAL HERE
How does an amatuer mathematician collaborate with a professional? Through the internet of course!
We do it all the time on Math Factor.
Chaim pointed me at the Macalester Problem of the Week. This led to my making a minor contribution to a published paper. I can’t claim it’s a world changing paper, or that my contribution amounted to much, but I did get my name in print! You can read an extract here. {Just above is a review of a book on symmetry, I’m not sure that is real, one of the authors is called Chaim Goodman-Strauss, clearly a made up name.}
It certainly is a fun paper. Stan Wagon is a bit of a legend, as you’ll see from the picture. I’m campaigning for all cycle paths to be built for square wheeled bicycles!
Can you solve some of these problems?
The paper was written by Stan Wagon and Robert Israel. They kindly added my name when I was able to replace some computer proofs with ‘real proofs’ (that’s a whole other discussion!)
Take a sequence of letters containing no more than ten different characters, for example ABCABCDE. Can we replace the letters consistantly with digits so that the resulting number is divisible by some target number n?
If n is 2 then it is quite simple, we just replace the last letter with an even digit. For example can replace ABCABCDE with 12312346. So we can substitute any sequence of letters to make a number divisible by 2.
Lets try with a target number n=3. Can we find a method for replacing the letters of any sequence so that the resulting number is divisible by three?
We know that a number is divisible by three if the sum of digits is divisible by three. ABCABCDE has two As, two Bs, two Cs, one D and an E. We want 2A + 2B + 2C + D + E to be a multiple of three. This is quite easy as there are four digits which are divisible by three: 0, 3, 6 and 9. Use these for A, B and C and then chose D and E so that they add up to a muliple of three. So we could use 03603612. It’s okay for numbers to start with zero.
We can always replace any sequence of letters so that the resulting number is divisible by three. Can you find a method for doing this?
We say that three is ‘attainable’.
If it is true for a target number, n, then we say that n is attainable.
So far we have said that 2 and 3 are attainable.
What other target numbers are attainable?
Okay so these are my questions:
1. Is five attainable?
2. Can you show that three is attainable?
3. If I tell you that nine is attainable can you show that 18 is attainable?
4. What about four?
5. What about six?
6. What about seven? I will give you a big clue here, the title of this post.
7. What other numbers can you show are attainable or not attainable?
Do you think there is a difference between proofs by computer programs or proofs with just the human brain, possibly aided by a pencil and a few sheets of foolscap?
Have fun guys!
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
jyoak said,
September 9, 2009 at 5:57 am
So being inattentive as I am, I saw “Can you solve any of these problems?” and, not realizing it was a link, assumed I was meant to look at the site instead of looking at the rest of the article and now I’ve spent too long working on this to look at yours. But maybe someone will get interested in this one:
http://mathforum.org/wagon/spring99/p884.html
I’ve only successfully completed the first part. I found the number 6210001000 . I started with big ones assuming that little ones are harder as that’s part two of the question. I suspect, though I’m not sure, that this is the largest qualifying number.
Who can find the smallest one? And even though they didn’t ask, it would be cool to figure out an algorithm to generate these. What I did to explore feels like it could be formalized.
Stephen Morris said,
September 10, 2009 at 3:01 pm
Jeff,
You are a lightning rod conductor for great puzzles!
This is a very slippery problem, it’s difficult to keep the logic in your head; too much recursion!
The autobiographical number problem allows numbers to have up to 10 digits, they can have less. I think the smallest one is 1210.
There are a couple of identities which help.
First, the sum of the digits must equal the number of digits. In 6210001000 we have 6+2+1+1 = 10. In 1210 we have 1+2+1 = 4.
Second, the sum of the digits times the number they are counting must equal the number of digits. In 6210001000 this is 6×0 + 2×1 + 1×2 +1×6 = 10. In 1210 this is 1×0 + 2×1 + 1×2 = 4.
I should explain why the second identity works. If the third digit (which counts 2s) is equal to 3 then there are three digits with value 2. Each of these is counting two other digits. So we have accounted for 3×2 = 6 digits.
Given that each digit is at least zero this is very restrictive. It doesn’t completely describe the problem but I wonder if it allows any solutions which aren’t autobiographical numbers?
Your solution is the only one with ten digits. Lets say the first digit is A and that there are ten digits.
If A is five or less then there are at least four other non-zero digits and they sum to at least five . The smallest value for the second identity is given by A2111 which makes 2+2+3+4=11. So A > 5.
If A is seven or more then there are at most two other non-zero digits and they sum to three or less. One of these is the digit which counts A, it will be 1 otherwise the first identity will be at least 2A >= 14. The digit which counts 1 will be at least 1. It can’t be 1 as it would then need to be 2. If it is anything other than 1 then we need another non-zero digit to count it. So A <7.
So A=6 and it’s easy to see that 6210001000 is the only possibility.
We can find shorter numbers by removing zeros to give 521001000, 42101000 and 3211000.
I have also found 1210 and 2020. I suspect this is it but I haven’t worked it all through. That would be one solution for each value of A.
Mike Jarvis said,
September 23, 2009 at 11:13 am
Also 21200.