1
$\begingroup$

A person starts writing consecutive natural numbers from $5$ until $k$ digits are reached. For some values of $k$, this will be impossible, for example $6$ or $8$ are impossible as then after writing the single digit numbers, we will have $1$ and $3$ left over respectively, but then we can only write double digit numbers.

An example of this would be if the person wanted to write $9$ digits, they write $5, 6, 7, 8, 9, 10, 11$ for a total of $5 + 2(2) = 9$ digits.

Question: Prove that if $A$, $B$, and $n$ are positive integers, then it is not possible to write $An^{2}$ + $B$ digits for each possible $n$ i.e for each pair of $(A,B)$, there exists an $n$ such that the person cannot write $An^{2}$ + $B$ digits.

I proved that the statement is true for $An$ + $B$, and think that it is true in this case as well, but I can't come up with a proof.

Edit: A sketch of the proof for the above case would be to note that as we go from $n$ to $n + 1$, the initial $An + B$ part is identical, and we only add $A$ digits after. Note that the smallest number we use in this "$A$ " digits interval is ever increasing, so there will come a point when even the smallest number in this interval shall contain more than $A$ digits.

Some perhaps useful facts:

$1)$ The differences between consecutive iterations is $a(2n + 1)$, a linear function in $n$.

$2)$ For sufficiently large $n$, if the $n$-th iteration uses numbers with at most $P$ digits, then the next iteration will use numbers with at most $P + 1$ digits.

$3)$ I imagine the proof is something which can be generalized to higher order polynomials as well.

$\endgroup$
  • $\begingroup$ This is not clear. What does "until $k$ digits are reached" mean? I assumed you meant "natural numbers of length $k$" but that's not consistent with the rest of what you wrote. $\endgroup$ – lulu Jan 15 at 20:35
  • $\begingroup$ For example, until $9$ digits would mean writing 5, 6, 7, 8, 9, 10, 11. So the total number of digits is 5 + 2(2) = 9. $\endgroup$ – Saad Jan 15 at 20:37
  • $\begingroup$ I don't think that interpretation would occur to very many people. Please edit your post for clarity. $\endgroup$ – lulu Jan 15 at 20:39
  • 1
    $\begingroup$ No, @lulu. The question is to show that for each pair $(A,B)$, you cannot write $A(n^{2}) + B$ digits for each $n$. For instance, if $A$ = 2, $B$ = 3, the question is whether you can write out consecutive natural numbers to hit $5, 11, 21, 35, ..$ digits $\endgroup$ – Saad Jan 15 at 21:05
  • 1
    $\begingroup$ Sure...but if I could change the start each time, isn't it obvious that I could achieve whatever digit count I liked? I understand it if the starting point is fixed, but you indicated that you thought that irrelevant. $\endgroup$ – lulu Jan 15 at 21:06

Your Answer

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

Browse other questions tagged or ask your own question.