Problem of the Month
Solution to Problem 6: March 2023

Note: In this solution, we will take for granted that if $n$ is a positive integer that is not a perfect square, then $\sqrt{n}$ is an irrational number.

1. Since $\sqrt{2}\approx 1.4142$ and $\sqrt{3}\approx 1.7320$, we have that $f(2)=4$ and $f(3)=7$.

   In the table below, the first column contains the integers $n$ from $37$ through $48$, the second column contains $\sqrt{n}$ truncated to four digits past the decimal point, and the third column contains $f(n)$.

   $n$	$\sqrt{n}$	$f(n)$
   $37$	$6.0827$	$0$
   $38$	$6.1644$	$1$
   $39$	$6.2449$	$2$
   $40$	$6.3245$	$3$
   $41$	$6.4031$	$4$
   $42$	$6.4807$	$4$
   $43$	$6.5574$	$5$
   $44$	$6.6332$	$6$
   $45$	$6.7082$	$7$
   $46$	$6.7823$	$7$
   $47$	$6.8556$	$8$
   $48$	$6.9282$	$9$

   Among the values of $f(n)$ for $n$ from $37$ through $48$, each integer from $0$ through $9$ appears exactly once except for $4$ and $7$, which appear exactly twice each. Notice that $4$ and $7$ are the values of $f(2)$ and $f(3)$, respectively.

2. Since $\sqrt{5}\approx 2.2360$, $\sqrt{6}\approx 2.4494$, $\sqrt{7}\approx 2.6457$, and $\sqrt{8}\approx 2.8284$, we have that $f(5)=2$, $f(6)=4$, $f(7)=6$, and $f(8)=8$.

   In the table below, the first column contains the integers $n$ from $50$ through $63$, the second column contains $\sqrt{n}$ truncated to four digits past the decimal point, and the third column contains $f(n)$.

   $n$	$\sqrt{n}$	$f(n)$
   $50$	$7.0710$	$0$
   $51$	$7.1414$	$1$
   $52$	$7.2111$	$2$
   $53$	$7.2801$	$2$
   $54$	$7.3484$	$3$
   $55$	$7.4161$	$4$
   $56$	$7.4833$	$4$
   $57$	$7.5498$	$5$
   $58$	$7.6157$	$6$
   $59$	$7.6811$	$6$
   $60$	$7.7459$	$7$
   $61$	$7.8102$	$8$
   $62$	$7.8740$	$8$
   $63$	$7.9372$	$9$

   Similar to part (a), observe that among the values of $f(n)$ for $n$ between $50$ and $63$ inclusive, every integer from $0$ through $9$ appears either once or twice, and the integers that appear twice are exactly $f(5)=2$, $f(6)=4$, $f(7)=6$, and $f(8)=8$.

3. Suppose $m$ is a positive integer in the list $n^2+1,n^2+2,\dots ,n^2+2n$. This is equivalent to $n^2<m<(n+1{)}^2$, which is equivalent to $n<\sqrt{m}<n+1$ since $m$, $n$, and $n+1$ are non-negative.

   Fix an integer $d$ satisfying $0\le d\le 9$ and assume that $m$ is an integer satisfying both $n^2<m<(n+1{)}^2$ and $f(m)=d$. That $f(m)=d$ means $d$ is the first digit past the decimal point in the decimal expansion of $\sqrt{m}$. That $\sqrt{m}$ is between $n$ and $n+1$ means the integer part of $\sqrt{m}$ is $n$. Therefore, $\sqrt{m}$ is at least ${\displaystyle \frac{d}{10}}$ more than $n$ and at most ${\displaystyle \frac{d+1}{10}}$ more than $n$. Since $\sqrt{m}$ is between two consecutive perfect squares, it is not a perfect square, which means $\sqrt{m}$ is irrational. Putting this together, we get that $$n+\frac{d}{10}<\sqrt{m}<n+\frac{d+1}{10}$$ where the strict inequalities are justified by the irrationality of $\sqrt{m}$. We are also assuming that $n$ is a positive multiple of $5$, which means there is some positive integer $k$ such that $n=5k$.

   The quantities in the chain of inequalities above are all positive, which means $${(n+\frac{d}{10})}^2<{\sqrt{m}}^2<{(n+\frac{d+1}{10})}^2$$ Expanding and substituting $n=5k$, we get $$25k^2+dk+\frac{d^2}{100}<m<25k^2+(d+1)k+\frac{(d+1{)}^2}{100}$$

   We will now count the number of integers that satisfy the inequalities above.

   Since the integer $d$ satisfies $0\le d\le 9$, we must have that $0\le {\displaystyle \frac{d^2}{100}}<1$. Therefore, $25k^2+dk+{\displaystyle \frac{d^2}{100}}$ is between the consecutive integers $25k^2+dk$ and $25k^2+dk+1$, possibly equal to the smaller of the two but not equal to the larger of the two. Since $m$ is an integer that is greater than $25k^2+dk+{\displaystyle \frac{d^2}{100}}$, we conclude that $$25k^2+dk+1\le m$$

   Similarly, $0\le d\le 9$ implies that $0<{\displaystyle \frac{(d+1{)}^2}{100}}\le 1$. This means $25k^2+(d+1)k+{\displaystyle \frac{(d+1{)}^2}{100}}$ is between the consecutive integers $25k^2+(d+1)k$ and $25k^2+(d+1)k+1$, possibly equal to the larger of the two but not equal to the smaller of the two. Since $m$ is an integer that is smaller than $25k^2+(d+1)k+{\displaystyle \frac{(d+1{)}^2}{100}}$, we can conclude that $m\le 25k^2+(d+1)k$. Combining this inequality with the inequality from earlier, we now have that $$25k^2+dk+1\le m\le 25k^2+(d+1)k$$ The number of integers $m$ that satisfy this inequality is $$(25k^2+(d+1)k)-(25k^2+dk)=k$$

   We have now shown the following: For each integer $d$ satisfying $0\le d\le 9$, there are at most $k$ integers $m$ in the list $n^2+1,n^2+2,\dots ,n^2+2n$ with the property that $f(m)=d$. There are $2n$ integers in the list above and only ten different values that the function $f$ can output. Since $10k=2n$, there is no possibility other than that $f$ takes every possible value exactly $k={\displaystyle \frac{n}{5}}$ times.

4. To get an idea of how to proceed, we first discuss the results of parts (a), (b), and (c).

   In part (a), we saw that for values of $m$ between $1^2$ and $2^2$, the function $f$ takes on every possible value the same number of times (zero) with the exception of $4$ and $7$, which occur one extra time each. For values of $m$ between $6^2$ and $7^2$, the function $f$ takes on every possible value the same number of times (one) with the exception of $4$ and $7$, which occur one extra time each.

   Similarly, in part (b) we observed that $f$ takes on every value the same number of times, with the exceptions of $2$, $4$, $6$, and $8$ when $m$ ranges between $2^2$ and $3^2$ as well as between $7^2$ and $8^2$.

   The result of part (c) was that if $n$ is a multiple of $5$, then $f(m)$ takes on every possible value the same number of times (with no exceptions) as $m$ ranges over the integers strictly between $n^2$ and $(n+1{)}^2$.

   The patterns in part (a) and (b) continue, and there are similar patterns for other ranges between perfect squares. A bit more precisely, if $n$ is a positive integer, then as $m$ ranges over the integers between $n^2$ and $(n+1{)}^2$, $f(m)$ takes on every possible value the same number of times, possibly with some exceptions that occur one extra time each. These exceptional values depend only on the remainder when $n$ is divided by $5$.

   Even more precisely, the following five claims are true. The claims are numbered to correspond to remainders after division by $5$.

   • Claim 0: Suppose $n=5k$ for some integer $k\ge 0$. As $m$ ranges over the integers strictly between $n^2$ and $(n+1{)}^2$, $f(m)$ takes every value from $0$ through $9$ exactly $k$ times.

   • Claim 1: Suppose $n=5k+1$ for some integer $k\ge 0$. As $m$ ranges over the integers strictly between $n^2$ and $(n+1{)}^2$, $f(m)$ takes the values $4$ and $7$ a total of $k+1$ times each and takes every other value $k$ times.

   • Claim 2: Suppose $n=5k+2$ for some integer $k\ge 0$. As $m$ ranges over the integers strictly between $n^2$ and $(n+1{)}^2$, $f(m)$ takes the values $2$, $4$, $6$, and $8$ a total of $k+1$ times each and takes every other value $k$ times.

   • Claim 3: Suppose $n=5k+3$ for some integer $k\ge 0$. As $m$ ranges over the integers strictly between $n^2$ and $(n+1{)}^2$, $f(m)$ takes the values $1$, $3$, $4$, $6$, $7$, and $8$ a total of $k+1$ times each and takes every other value $k$ times.

   • Claim 4: Suppose $n=5k+4$ for some integer $k\ge 0$. As $m$ ranges over the integers strictly between $n^2$ and $(n+1{)}^2$, $f(m)$ takes the values $1$, $2$, $3$, $4$, $5$, $6$, $7$, and $8$ a total of $k+1$ times each and takes the values $0$ and $9$ a total of $k$ times each.

   In part (c), we showed that Claim 0 is true. Before proving Claims 1, 2, 3, and 4, we will answer the actual question which was to determine how many times each digit occurs in the list $$f(1),f(2),f(3),\dots ,f({10}^4)$$ Because ${10}^4$ is a perfect square, $f(0)=f({10}^4)=0$, so we can instead count the number of times each digit occurs in the slightly different list $$f(0),f(1),f(2),\dots ,f({10}^4-1)$$

   There are $100$ perfect squares among the integers from $0$ through ${10}^4-1$, so there are $100$ occurrences of $0$ in the list that come from perfect squares.

   For every other integer $m$ in the list $0,1,2,3,4,\dots ,{10}^4-1$, there are unique integers $k$ and $r$ with $0\le k\le 19$ and $0\le r\le 4$ with the property that $(5k+r{)}^2<m<(5k+r+1{)}^2$.

   Suppose $d$ is a non-zero digit. For fixed $k$ and $r$, as we let $m$ take the values strictly between $(5k+r{)}^2$ and $(5k+r+1{)}^2$, Claim $r$ tells us whether the digit $d$ occurs either $k$ times or $k+1$ times in that range. We are considering values of $m$ satisfying $(5k+r{)}^2<m<(5k+r+1{)}^2$ for every pair $(k,r)$ with $0\le k\le 19$ and $0\le r\le 4$. For every pair of the form $(k,0)$, we get $k$ occurrences of $d$ (see Claim 0). For every pair of the form $(k,1)$, we always get $k$ occurrences or we always get $k+1$ occurrences of $d$, depending on what Claim 1 says about the digit $d$. Continuing with this reasoning, the number of occurrences of $d$ in the list $f(0),f(1),f(2),\dots ,f({10}^4-1)$ can be expressed in the form $$a(0+1+2+\cdots +18+19)+b(1+2+3+\cdots +19+20)=190a+210b$$ where $a$ is the number of values of $r$ for which Claims 0 through 4 say there are $k$ occurrences of $d$, and $b$ is the number of values of $r$ for which Claims 0 through 4 say there are $k+1$ occurrences of $d$.

   For example, for $d=1$, there are $k$ occurrences when $r=0$, $r=1$, and $r=2$, and there are $k+1$ occurrences when $r=3$ and $r=4$. Therefore, with $d=1$, we have $a=3$ and $b=2$, so the number of times that $d=1$ occurs in the list is $3\times 190+2\times 210=990$.

   Using Claims 0 through 4, the table below summarizes the count for the remaining non-zero digits. In the first column, the digit $d$ appears, in the second column the value of $a$ appears, in the third column, the value of $b$ occurs, and in the fourth column, $190a+210b$ appears, which is the number of times $d$ appears in the list.

   $d$	$a$	$b$	$190a+210b$
   $1$	$3$	$2$	$990$
   $2$	$3$	$2$	$990$
   $3$	$3$	$2$	$990$
   $4$	$1$	$4$	$1030$
   $5$	$4$	$1$	$970$
   $6$	$2$	$3$	$1010$
   $7$	$2$	$3$	$1010$
   $8$	$2$	$3$	$1010$
   $9$	$5$	$0$	$950$

   Finally, for $d=0$, we already have $100$ occurrences of $0$ in the list coming from the perfect squares. Otherwise, we can use the exact same technique as above to count the number of $0$s in the list coming from integers that are not perfect squares. For $d=0$, $a=5$ and $b=0$, so there are $5(190)+0(210)+100=1050$ occurrences of the digit $0$ in the list $f(0),f(1),f(2),\dots ,f({10}^4-1)$.

   We will now prove Claims 1 through 4.

   Suppose $k$ is a non-negative integer, $r$ is $0$, $1$, $2$, $3$, or $4$, and that $d$ is a digit between $0$ and $9$ inclusive. We wish to count the number of integers $m$ such that $f(m)=d$ and $(5k+r{)}^2<m<(5k+r+1{)}^2$. Specifically, we want to show that this number is either $k$ or $k+1$ depending on $r$ and $d$ in the way delineated in Claims 0 through 4.

   The condition $(5k+r{)}^2<m<(5k+r+1{)}^2$ is equivalent to $5k+r<\sqrt{m}<5k+r+1$, and this combined with $f(m)=d$ (note that $m$ is not a perfect square and that $5k+r$ and $5k+r+1$ are consecutive integers) is equivalent to $$5k+r+\frac{d}{10}<\sqrt{m}<5k+r+\frac{(d+1)}{10}.$$ Since everything is non-negative, everything can be squared to get the equivalent chain of inequalities $$(5k+r{)}^2+\frac{2(5k+r)d}{10}+\frac{d^2}{100}<m<(5k+r{)}^2+\frac{2(5k+r)(d+1)}{10}+\frac{(d+1{)}^2}{100}.$$ After some expansion, we have $$(5k+r{)}^2+kd+\frac{2rd}{10}+\frac{d^2}{100}<m<(5k+r{)}^2+kd+k+\frac{2r(d+1)}{10}+\frac{(d+1{)}^2}{100}.$$ We are interested in how many integers $m$ satisfy the chain of inequalities above. Since $(5k+r{)}^2+kd$ is an integer, the number of integers $m$ satisfying the inequalities above is the same as the number of integers $m^{\prime }$ that satisfy $$\frac{2rd}{10}+\frac{d^2}{100}<m^{\prime }<k+\frac{2r(d+1)}{10}+\frac{(d+1{)}^2}{100}$$ and after combining fractions on the left and right, we get $$\begin{array}{}\text{(}\ast \text{)}& \frac{20rd+d^2}{100}<m^{\prime }<k+\frac{20r(d+1)+(d+1{)}^2}{100}\end{array}$$

   Suppose ${\displaystyle \frac{20rd+d^2}{100}}$ and ${\displaystyle \frac{20r(d+1)+(d+1{)}^2}{100}}$ are both strictly between $0$ and $1$. Then the integers $m^{\prime }$ satisfying $(\ast )$ are precisely the integers $1$ through $k$. More generally, we will show that whether there are $k$ or $k+1$ integers depends on whether or not the quantities ${\displaystyle \frac{20rd+d^2}{100}}$ and ${\displaystyle \frac{20r(d+1)+(d+1{)}^2}{100}}$ are between the same pair of consecutive integers.

   To give an idea of how the argument will proceed, consider the situation when $r=1$ and $d=4$. Then ${\displaystyle \frac{20rd+d^2}{100}}={\displaystyle \frac{96}{100}}$, but ${\displaystyle \frac{20r(d+1)+(d+1{)}^2}{100}}={\displaystyle \frac{125}{100}}$. Thus, $(\ast )$ becomes $$\frac{96}{100}<m^{\prime }<k+\frac{125}{100}$$ The integers $m^{\prime }=1$ through $m^{\prime }=k+1$ satisfy these inequalities, for a total of $k+1$ integers.

   Observe that $$\begin{array}{rl}\frac{20r(d+1)+(d+1{)}^2}{100}-\frac{20rd+d^2}{100}& =\frac{(20rd+20r+d^2+2d+1)-(20rd+d^2)}{100}\\ & =\frac{20r+2d+1}{100}\\ & \le \frac{20(4)+2(9)+1}{100}\text{(since }r\le 4\text{, }d\le 19\text{)}\\ & =\frac{99}{100}\end{array}$$ This means the difference between ${\displaystyle \frac{20rd+d^2}{100}}$ and ${\displaystyle \frac{20r(d+1)+(d+1{)}^2}{100}}$ is less than $1$, which leads to the following two possibilities.

   Possibility 1: There is an integer $a$ so that $$a\le {\displaystyle \frac{20rd+d^2}{100}}<{\displaystyle \frac{20r(d+1)+(d+1{)}^2}{100}}\le a+1$$ In this case, the integers satisfying $(\ast )$ are $a+1$, $a+2$, $a+3$, and so on through $a+k$ for a total of $k$ integers.

   Possibility 2: There is some integer $a$ with the property that $$a<{\displaystyle \frac{20rd+d^2}{100}}<a+1<{\displaystyle \frac{20r(d+1)+(d+1{)}^2}{100}}<a+2$$ In this case, the integers satisfying $(\ast )$ are $a+1$ through $a+1+k$, for a total of $k+1$ integers.

   We have now shown that there will be $k+1$ integers satisfying $(\ast )$ exactly when there is an integer strictly between ${\displaystyle \frac{20rd+d^2}{100}}$ and ${\displaystyle \frac{20r(d+1)+(d+1{)}^2}{100}}$. Multiplying through by $100$, this is equivalent to there being a multiple of $100$ strictly between $20rd+d^2$ and $20r(d+1)+(d+1{)}^2$

   The table below contains the values of $20rd+d^2$ for every $0\le r\le 4$ and $0\le d\le 9$. The columns after the first are indexed by a value of $d$ from $0$ through $9$ from left to right and the rows after the first are indexed by values of $r$ from $0$ through $4$ from top to bottom. The cell in the row corresponding to $r$ and the column corresponding to $d$ contains $20rd+d^2$. Cells are highlighted if there is a multiple of $100$ between the value in the cell and the value in the cell immediately to its right.

   $r$/$d$	0	1	2	3	4	5	6	7	8	9	10
   0	0	1	4	9	16	25	36	49	64	81	100
   1	0	21	44	69	96	125	156	189	224	261	300
   2	0	41	84	129	176	225	276	329	384	441	500
   3	0	61	124	189	256	325	396	469	544	621	700
   4	0	81	164	249	336	425	516	609	704	801	900

   The highlighted cells correspond to pairs $(r,d)$ for which $20rd+d^2$ is less than a multiple of $100$ and $20r(d+1)+(d+1{)}^2$ is greater than that multiple of $100$. As noted above, these correspond to the pairs $(r,d)$ for which $k+1$ integers satisfy $(\ast )$. For $r=0$, we see no values of $d$, which gives another proof of Claim 0. For $r=1$, the values of $d$ for which there are $k+1$ integers are $d=4$ and $d=7$, which proves Claim 1. Continuing, the data in the table above verifies Claims 0 through 4.