1

So I had a Year 11/12 Maths Competition today and one of the last questions on the competition paper was this:

"A certain number is comprised of only 1's and 0's. When divided by 23 it has a remainder of 18. What is the highest amount of "1's" in a number that fits this description?"

to my understanding, this means the number is Base 10 and not binary

this question was not multiple choice, you were given 3 digits to write into (keep in mind, the first number can be zero)

The test was also done without a calculator so if you can provide steps without the use of a calculator and what we can calculate on rough paper, that would be great. Thanks

Gamma Function
  • 5,642
VikeStep
  • 187
  • 3
    There isn't any largest such number: $10^{4+22k}$ has remainder $18$ upon division by $23$ for every $k$. So you want the largest 3-digit number? – Kevin Carlson Aug 01 '13 at 07:46
  • its asking for how many 1's are in the largest number. so if you're correct wouldn't that mean the highest is 999? – VikeStep Aug 01 '13 at 07:49
  • Jyrki is right, so I'm not sure what was the expected answer. You can get as many $1$s as you want by adding together $10^4+10^{26}+...+10^{4+22k}$. – Kevin Carlson Aug 01 '13 at 07:52
  • A second reading reveals that the question is about the largest possible number of $1$s as digits. Using Kevin's idea you can make this as high as you want. Just add up numbers of the form $10^{22k}$ in such a way that you use $18$, $41$, $64$, $87,\ldots$, different values for $k$, and you get numbers with $18,41,64,\ldots,$ ones. – Jyrki Lahtonen Aug 01 '13 at 07:56
  • So either the question was bad (no answer), or you have not described it here accurately. In contest-math you often can assume (for the toughest questions) that students have seen Little Fermat (even though it usually is not covered in school curriculum). Therefore you know that all the powers $10^{22k}$ have remainder $1$ when divided by $23$. – Jyrki Lahtonen Aug 01 '13 at 08:01

1 Answers1

2

If you’re limited to three-digit numbers (possibly with leading zeroes), you might as well do it by brute force: start with $18$ and keep adding $23$. You very quickly get

$$18,41,64,87,\underline{110},133,156,179\;,$$

and the next number is too large. The only three-digit number that fits the description is $110$, and it has $2$ ones.

If you’re not limited to three digits, then there is no largest possible number of ones, as others have already pointed out in the comments.

Brian M. Scott
  • 616,228
  • I realised I asked the question wrong, I will edit it in the OP – VikeStep Aug 01 '13 at 07:50
  • the difference is what is the number which has the most "1's" in it that fits this description and how many are there – VikeStep Aug 01 '13 at 07:52
  • 2
    @VikeStep: If the number of digits is unrestricted, you can have any positive number of $1$’s in a number fitting that description. There is no largest possible number. – Brian M. Scott Aug 01 '13 at 07:56
  • hmmm, well I get the test back in 2 months time so I will be interested to see what the answer gets back. Thanks for the responses. – VikeStep Aug 01 '13 at 07:57
  • @VikeStep: You’re welcome. (I’m actually kind of curious myself at this point!) – Brian M. Scott Aug 01 '13 at 08:00
  • If I remember, I'll come back here. (I get the question sheet in a week but not the answer) so there is a possibility i left out an important detail – VikeStep Aug 01 '13 at 08:02
  • 1
    @VikeStep: Thanks. It’s no big deal if you don’t, but if you remember, that would be great. – Brian M. Scott Aug 01 '13 at 08:04