Middle Three Digits
This question was Colombia State University’s Problem of the Week on December 03, 2007. It was also, according to this list, the problem for which the lowest percentage of solutions submitted was correct. (The second “most difficult” problem probably earned that distinction by being poorly specified. And on a second look, I think this one may fit that category as well.) I think that labeling problems as “most difficult” based on the percentage of correct answers is a poor way of making that determination (since for some questions, it will be obvious when an answer is wrong, and the person just won’t bother submitting). I’d think the absolute number of correct answers would be a better guide. Anyhow, the problem:
A five-digit perfect square in the form of 5abc6 has a thousands digit a, hundreds digit b, and tens digit c. If a is less than or equal to b and b is less than or equal to c, what is the sum of a + b + c?
My challenge to you, my readers, is this: is there a better way to solve this than “guess and check”? I see ways to narrow the guessing down substantially, so this may indeed be the best way, but I wonder if there is another approach.
And I’ll also add a combinatorics question to this: How many five-digit numbers are there of the specified form? (And if you like, you could add an answer to the question “Is this a Permutations question or a Combinations question?“)
Ramblings of a Math Mom 
So, what am I missing? It seems like there are two possible sums.
Here’s what I did:
Since 5abc6 ends in 6 the square root must end in 4 or 6.
Also, the square root of 50006 is less than 224 and the square root of 59996 is greater than 244 so the square root of 5abc6 must be one of the following:
224, 226, 234, 236, 244
If you square each of these numbers you get:
224 -> 50176. That satisfies the condition.
226 -> 51076. That doesn’t work.
234 -> 54756. That doesn’t work.
236 -> 55696. That also works.
244 -> 59536. That doesn’t work.
So, since 224 is the square root of 50176 then a+b+c = 0+1+7 = 8.
And, since 236 is the square root of 55696 then a+b+c = 5+6+9 = 20.
So, 8 and 20 are possible sums but it seems like they want one sum. This is disturbing.
The only “shortcut” I can see, once you identify the 5 possible square roots is to square each number using cross multiplication. This allows you to go from right to left, producing digits of the answer. If you get a digit that violates the condition of the problem then you can discard that number as a possible answer without computing the rest of the square.
Hi Sol,
I did just what you did, and also got the same two answers as you did. Which is why I said that perhaps the reason they got so few correct answers was that the problem was poorly specified. The other problem that I was complaining about being poorly specified was a “how many ice cream cones” problem that didn’t specify whether order matters (is chocolate on top and vanilla on the bottom the same as vanilla on top and chocolate on the bottom?) or whether a cone with two scoops of the same flavor would be allowed. That’s the only reason I can see why that otherwise simple problem would have had so few correct answers.
I like the Columbia State University Problem of the Week site as a source of new puzzles, but it seems that they do need to be reviewed before handing them to students…
Hi,
Regarding the counting problem, if you’re essentially asking how many 3 digit numbers abc are there (with 0 being ok as the first digit, the first two digits, or all three digits) such that a<= b <= c I think the answer is 220. Am I right? If so I can explain how I got the answer.
You seem to be implying that I know the answer. 😀
Well, I tried the problem and I came up with 220 also. So, I’m not sure if it’s right but I agree with you. I did it via casework with 3 cases — did you?
Here’s what I did:
I looked for a patten.
If the first two digits are 00 then there are 10 possibilities for the last digit.
If the first two digits are 01 then there are 9 possibilities for the last digit.
If the first two digits are 02 then there are 8 possibilities for the last digit.
…
If the first two digits are 09 then there is just 1 possibility for the last digit.
So, if the first digit is 0 then there are 10+9+8+7…+1 which is 11C2 as a binomial coefficient.
Then I looked at cases where the first digit was 1.
If n=11x then there are 9 ways to choose x.
If n=12x then there are 8 ways to choose x.
If n=13x then there are 7 ways to choose x.
…
If n=19x then there is 1 way to choose x.
So, if the first digit is 1 there are 9+8+7+…+1 ways to form the number which is 10C2.
Along that line of thinking there are 9C2 ways to form a number if the first digit is 2.
So, for all 10 cases of the first digit the number of numbers that meet the constraint is 11C2 + 10C2 + … + 2C2.
By seeing the hockeystick theorem pattern in Pascal’s triangle we see that the sum of those 10 binomial coefficients is 12C3, or 12x11x10/(3x2x1),
which is 2x11x10 or 220.
It’s not intuitive to me though why the answer is 12C3. It makes me think that there’s a way that one could see that this problem was equivalent to choosing 3 objects out of 12 regardless of order.
This problem is suspiciously similar to the Christmas present counting problem I wrote about on my blog recently. Maybe I’ll write a follow up article discussing this problem and the more general case.
Doing this problem and the Christmas present one make me want to get a good combinatorics book and brush up.
How did you solve the problem?
Also, how would you solve this for 4 digit numbers?
Sol, I did it a somewhat faster way.
First I considered the cases where no digit is repeated. There are 10C3 possible sets of 3 different digits. For each of them, one possible ordering is a legal ordering. So, there are 10C3 = 120 possibilities with no repeats.
Then I considered the case where all 3 digits are the same. There are 10 possibilities there.
Finally I considered the case where one digit occurs twice, and a different digit occurs once. There are 10×9 different ways of choosing the sets of numbers (choose one to occur once 10 ways, then choose a different number to occur twice 9 ways) and again each has only one legal order, so each one represents only 1 possible answer. So there are 90 possibilities for this case.
So my answer is 120 + 10 + 90 which is also 220. Since we both got the same number in different ways, I think we’ve got it right.
Your question as to why the answer is 12C3 and how we could have gotten there directly reminded me that the problem is really how many combinations are there of three digits from 0 to 9 with replacement. And the formula for that, if you look it up, is (for choosing k objects from n possibilities) (n+k-1)Ck or in our case 12C3 as you discovered.
Combinations with replacement seems to be the rarest of the four basic types of permutations and combinations with or without replacement. I wonder why….
I had to use google to find the last time I looked this up to comment on someone’s blog. 🙂 And I’ll again link to the place where I found a decent explanation as to why it is so.
In this problem, we could represent our choice as a string of ten 0’s and three 1’s, where the number of 1’s immediately to the left of the ith zero represents the number of times the digit i is included. So then it comes down to choosing 3 possible positions for the 1’s from among the n+k-1 allowable positions (the last digit can’t be a 1, since it has to occur to the left a zero).
And now, of course, we know that for a 4-digit number we can just plug it into the formula for combinations with replacement, and get 12C4 = 495.
And that also answers the question as to whether it is a permutation question or a combination question — it is a combination question with replacement, actually fitting much more neatly into a single box than I had at first realized.
“… how many combinations are there of three digits from 0 to 9 with replacement. And the formula for that, if you look it up, is (for choosing k objects from n possibilities) (n+k-1)Ck or in our case 12C3 as you discovered.”
I don’t get this. Where is this taking into account the fact that a<=b<=c?
“In this problem, we could represent our choice as a string of ten 0’s and three 1’s, where the number of 1’s immediately to the left of the ith zero represents the number of times the digit i is included. So then it comes down to choosing 3 possible positions for the 1’s from among the n+k-1 allowable positions (the last digit can’t be a 1, since it has to occur to the left a zero).”
I don’t see this. Can you give a few examples of what these strings look like and what numbers they represent, for both cases where digits are repeated and where they’re not? Also, a<=b<=c needs to be taken into account.
Thanks.
Where is this taking into account the fact that a<=b<=c?
The trick is this — any give set (combination) of 3 digits represents exactly one valid permutation in which a<=b<=c
So if the 3 chosen digits are {4,2,7} then abc = 247
Can you give a few examples…
Sure: suppose the 13-digit string looks like this:
0010100100000
Imagine that the zeros are labeled from 0 through 9, starting on the left. Each time there’s one or more 1’s immediately to the left of a zero, that represents choosing the number with which that zero was labeled.
So the string above has 1’s to the left of the #2, #3 and #5 zeros, so it represents choosing the digits 2, 3 and 5. We arrange them in the only permitted order and abc = 235
if we have:
1000011000000
that represents choosing the digits 0, 4, 4 (4 is chosen twice, because the 5th zero (#4 if we are labeling starting from 0) has two ones to the left of it. Again, we arrange these chosen digits into the only order permitted, and abc = 044 in this case.
It’s a combination question, because we take the 12 leftmost slots, and choose 3 places to put 1’s, then fill in the rest of the with 0’s (plus the 13th slot). It doesn’t matter in which order we choose the spots for the 1’s, only where they all ended up, because we are going to re-order the chosen numbers according to our constraints anyhow.
1110000000000 represents abc=000 and
0000000001110 represents abc=999
Hope that’s clearer!
One more thing: if we didn’t have any constraints on the relationships between a, b and c, then we would need the number of permutations of 3 items chosen out of 10 with replacement (10^3). It is the constraint that gives us only one correct permutation per combination that tells us that we only need to know the number of combinations (with replacement) to answer the puzzle. So, I guess it is in a way both a permutation question and a combination question. 😉
Brilliant explanation. I get it now!
And, if you change the constraint to not allow equality, i.e. a < b < c, then I believe there are just 10C3 such numbers, right?
You have 10 choices for the first digit, then 9 choices among the remaining 9 digits, then 8 choices for the final digit. So, you have 10x9x8 ways to choose the 3 digits in order but among every set of 3 distinct digits there are 6 permutations and only one of those 6 is in ascending order. So, the answer is 10x9x8/(3x2x1), or 10C3.
Another way to look at it is that 10C3 is the number of dways you can choose 3 digits from 10 without replacement and regardless of order. Any 3 distinct digits you pick can be arranged in only 1 way to get them in ascending order.
Thanks for the combinatorics review. It’s been a while but I love the stuff!
You’re right about the case where repeated digits are not allowed. That was actually the first “case” of my long solution to the original problem, above.
I’m pretty solid on middle-school level combinatorics at this point, but beyond that, I am rusty as well. I didn’t remember how the combinations with replacement thing worked until I looked it up again. That is a trick that comes up in various guises in combinatorics, but I always forget about it!
Have you seen the bracelet problem I posted a couple of weeks back? Now that you’re ready to kick it up a notch… 😉
The bracelet problem looks interesting but not right now. It’s more hard thinking than I want to do right now.
Please help me with this problem:In how many ways can 2 red beads, 3 blue beads, 2 yellow beads, and 3 white beads be arranged in a necklace if
a. Beads of the same color are placed together?
b. No beads of the same color are beside each other
c. The beads may be arranged in any order
In how many ways can 8 male dancers and 8 female dancers arrange themselves in a circle if
a. male and female dancers alternate
b. 2 male dancers alternate with 2 female dancers