3
$\begingroup$

As a first step, you write the number 1 on a piece of paper and continue to append step by step the next following integer. After 10 steps the number 12345678910 is written on the paper.

How many numbers are written on the paper during the first 999 steps, which are divisible by 11?

$\endgroup$
2
  • 2
    $\begingroup$ "How many numbers are written on the paper": Are you including, in the count of such numbers, numbers that are written by the way while writing longer numbers? For example, while writing 12345678910 you had to first write 1234567891. $\endgroup$
    – msh210
    Aug 10 at 21:50
  • $\begingroup$ Updated my answer as someone pointed out that I had misunderstood the question. $\endgroup$ Aug 10 at 22:01
3
$\begingroup$

The number is

82

Explanation:

As $10 \equiv -1 \mod 11$ (hence $100 \equiv 1 \mod 11, 1000 \equiv -1 \mod 11$) it suffices to examine the sums $1,\\ -1+2,\\ 1-2+3,\\ \ldots,\\ 1-2+\ldots+9,\\1-2+\ldots+9+10,\\\ldots,\\1-2+\ldots+9+10+\ldots+99,\\-1+2-\ldots-9-10-\ldots-99+100,\\1-2+\ldots+9+10+\ldots+99-100+101,\\\ldots$
The signs in the sum alternate when a single or three digit number is appended and stay the same when a double digit number is appended.

It therefore makes sense to analyse three epochs based on the number of digits of the increments:
single digits: it is easily verified that the first 9 numbers are $\mod 11$ $1,1,2,2,3,3,4,4,5$
double digits: the next two are $4,4$ after which increments start at $1$ again. As the cumulative increment is $11$-periodic we need only count the next $11$ sums which are $5,7,10,3,8,3,10,7,5,4,4$. Therefore up to $99$ there are no multiples of $11$.
three digits: This is $22$-periodic. The structure is more or less the same as for single digits, only with an additional alternating offset of $\pm 4$: $8,5,9,6,10,7,0,8,1,9,2,10,3,0,4,1,5,2,6,3,7,4$ we see, that all residuals including $0$ occur twice. As there are $900 = 40\times 22+20$ three digit numbers to be added we see that the total number of multiples of $11$ must be $82$.

$\endgroup$
1
  • 1
    $\begingroup$ There is so much beauty in mathematics, excellent answer! $\endgroup$ Aug 10 at 22:32
4
$\begingroup$

Since the tag wasn't specified; the technical answer based on the description of the problem is:

There are 999 numbers since each step generates a new number. When we arrive at our final answer, we get a number that is 2889 characters long. Of these numbers, 82 of them are divisible by 11.

Drawing inspiration from @loopy walt's answer; the numbers divisible by 11 are pretty massive so below are their values after performing MOD 10 on them:

6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3, 8, 5, 0, 7, 2, 9, 4, 1, 6, 3

Using lateral thinking, we can also deduce the following information:

There are technically 1998 numbers involved in this process; of those numbers 1994 of them are distinct. This can be gathered by the step number and the newly generated number. The numbers that are duplicated are 12 and 123.

I arrived at my answer with the following C# source code:

int digit = 1;
string number = "1";
List<BigInteger> values = new List<BigInteger>();
List<BigInteger> divisibleBy11 = new List<BigInteger>();
for (int i = 0; i < 998; i++) {
    values.Add(digit);
    number += (++digit).ToString();
    var x = BigInteger.Parse(number);
    values.Add(x);
    if (x % 11 == 0)
        divisibleBy11.Add(x % 10);
}

Console.WriteLine(number);
Console.WriteLine(number.Length);
Console.WriteLine(divisibleBy11.Count);
Console.WriteLine(values.Distinct().Count());
Console.WriteLine(string.Join(',', values.Where(w => values.Count(c => c == w) > 1)));
Console.WriteLine(string.Join(',', divisibleBy11));

The final number is:

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999

$\endgroup$
3
  • $\begingroup$ If my answer can be improved, feel free to leave a comment to explain how and I'll take action to do so. $\endgroup$ Aug 10 at 21:51
  • 1
    $\begingroup$ The 11th step gets you 1234567891011, followed by 123456789101112 - the integer after 10 is 11, not 1. You don't just repeat 1234567890 ninety-nine times. $\endgroup$ Aug 10 at 21:56
  • $\begingroup$ @NuclearHoagie very well :D a misunderstanding on my part. Correcting now. $\endgroup$ Aug 10 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.