17
$\begingroup$

The bug is placed at point $(0,0)$. From $(x, y)$ the bug can move to $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, and $(x, y-1)$. Some points are dangerous. To know which points are safe, we check if $$n(|x|)+n(|y|)\le23 \tag{1}$$ where $n(a)$ is the sum of digits of $a$. Question: How large is the area (number of points) that the bug can access?

Well, if it was just to check the sum of the absolute values of coordinates, then $|x|+|y| \le 23$ would draw a square whose diagonal is $d=46$ and area $d^2/2$. However, with the rule $(1)$ I don't think one gets an ordinary geometrical object.

By the help of some code, the answer seems to be $592597$


A Python program gives (for $14$ instead of $23$): enter image description here

Any help is appreciated.

$\endgroup$
4
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Aug 29, 2020 at 14:48
  • 1
    $\begingroup$ Quick and dirty Python code to generate bitmap showing reachable as well as valid points pastebin.com/DrKjVHbF (image output i.imgur.com/nZdPojr.png) $\endgroup$
    – Sil
    Aug 29, 2020 at 18:29
  • $\begingroup$ @Sil Many people have provided the code, but I need a mathematical approach $\endgroup$
    – VIVID
    Aug 30, 2020 at 7:29
  • 1
    $\begingroup$ @VIVID That's why it is posted as a comment, not an answer. If someone finds a mathematical approach, I'm sure they will post it. $\endgroup$
    – Sil
    Aug 30, 2020 at 7:48

2 Answers 2

5
+50
$\begingroup$

In short, my strategy was to consider the digits from largest to smallest, and then sum up the corresponding safe numbers that are reachable.

I found your specific case $k=23$ to be easy and this problem to be fun, so I extended my method to general $k$ (and applied it up to $d=4$ digit numbers).


The general solution

If the safe points are given by $n(|x|)+n(|y|)\le k$, then the total number of reachable points is:

$$\begin{align} f_1(k\pm 0) &= 2x (x+1) + 1\\ f_2(k-9) & =\frac16 x (x (769 - (x - 34) x) + 2894) + 505 \\ f_3(k-18) & =\frac{1}{90} x (x (x (x ((x - 51) x - 425) + 46215) + 966124) + 3900336) + 47905\\ \dots \end{align}$$

Where $f_d:[0,9)\subseteq\mathbb N\to\mathbb N$ is derived from the case when greatest reachable number has $d$ digits.

For example, the solution to your problem $k=23$ is given by $f_3(23-17)=f_3(6)=592597$. For first three cases of digits $d$, here are all the results:

k 0  1   2   3   4   5   6    7    8    9    10    11    12    13    14    15     16     17     18      19      20      21      22      23      24       25       26
f 1  1   1   1   1   1   1    1    1    2     2     2     2     2     2     2      2      2      3       3       3       3       3       3       3        3        3
= 1, 5, 13, 25, 41, 61, 85, 113, 145, 505, 1121, 2025, 3245, 4805, 6725, 9021, 11705, 14785, 47905, 102485, 181533, 287881, 424129, 592597, 795285, 1033841, 1309537

Summary of my counting method (For your case $d=3,k=23$)

For example, lets solve for $d=3$, i.e. the largest number that the bug can reach is "$t99$", $t\in[1,9]$, i.e. we are searching for $f_3$ equation. It can be shown that then $k=t+18,k\in[18,26]$.

Consider points in a square region from $(a_100,b_100)$ to $(a_199,b_199)$ such that $a_1+b_1=c_1$, i.e. the sum of the largest digits is $c_1$. We can show that we must have $c_1\le t$ for the region to be reachable, which gives us that there are $4(c_1+1)$ many such reachable regions.

Let $B(c_1)$ be the number of reachable points in such a $100$ by $100$ region. The total number of reachable points will be equal to the sum of all these regions minus the overlapped duplicates on the axes, which is

$$ \left(\sum_{c_1=0}^{t}4(c_1+1)B(c_1)\right)-4\cdot t99 +1. $$

To find $B(c_1)$, we can look at square regions from $(a_1a_20,b_1b_20)$ to $(a_1a_29,b_1b_29)$ such that $a_2+b_2=c_2$. We can show that we must have $c_2\le 9+t-c_1$ for these regions to be reachable, which gives us that there are $s_{10}(c_2+1)$ many such reachable regions, where $s_m(n)=m-|m-n|$ is the "staircase" function that goes up to $m$ then down again.

Let $b(c_1,c_2)$ be the number of reachable points in such a $10$ by $10$ region. The total number of reachable points in $B(c_1)$ will be equal to the sum of all these $b_1(c_1,c_2)$ regions, which is

$$ B(c_1)=\sum_{c_2=0}^{9+t-c_1}s_{10}(c_2+1)b(c_1,c_2). $$

We are now walking over all reachable $10$ by $10$ regions. To find $b(c_1,c_2)$, we can subtract the number of non-safe points from the total number of points, which amounts to

$$ b(c_1,c_2)= 10^2-\sum_{i=0}^{c2 + c1 - t}s_{10}(i+1). $$

Finally, we can put all three steps together to obtain

$$ f_3(t)=\left(\sum_{c_1=0}^{t}4(c_1+1)\left(\sum_{c_2=0}^{9+t-c_1}s_{10}(c_2+1)\left(10^2-\sum_{i=0}^{c2 + c1 - t}s_{10}(i+1)\right)\right)\right)-4\cdot t99 +1. $$

This sum can be simplified to obtain the $f_3(k-18)$ expression given at the beginning.

You can verify that $f(t)$ and $f_3(k-18)$ are equal with Wolfram Mathematica code:

s[n_, m_: 10] := (m - Abs[m - n]);
f3a = Table[Sum[4 (c1 + 1) Sum[s[c2 + 1] (10^2 - Sum[s[i + 1], {i, 0, c2 + c1 - t}]), {c2, 0, 9 + t - c1}], {c1, 0, t}] - 4 (t*100 + 99) + 1, {t, 1, 9}];
f3b = Table[1/90 k (k (k (k ((k - 51) k - 425) + 46215) + 966124) + 3900336) + 47905, {k, 0, 8}];
Print[f3a == f3b];

by copy & pasting it into a online wolfram mathematica notebook and clicking run (shift + enter).

You can additionally verify it by comparing results with code that Sil provided in the comments.

In a similar way, we should be able to find a sum for any $f_d$ and then simplify it to a polynomial.


Results for larger $k$ values

For example, the next case $d=4,k\in[27,35]$ can be solved to obtain $$f_4(t)=4\cdot g_4(t)-4\cdot t999 +1,t\in[0,9)$$ where $g(t)$ is given by:

$$ \sum_{c_1=0}^t(c_1+1)\sum_{c_2=0}^{9+t-c_1}s_{10}(c_2+1)\sum_{c_3=0}^{\min\{18-c_2+(t-c_1),18\}}s_{10}(c_3+1)\left( 10^2-\sum_{i=0}^{-9+c_3+c_2+c_1-t}s(i+1)\right) $$

which can be simplified to $f_4(k-27)$ which equals

$$ \frac{1}{2016} x (x (x (x (x (x (x (- x + 68) + 238) - 97048) - 317009) + 95866148) + 1898425124) + 7662488304) + 4216357 $$

whose results are

4216357,9006221,15961125,25353625,37441397,52462177,70629201,92127245,117109345

I do not know if it is possible to express the coefficients of $f_d$ for larger $d$ in a nicer way.

$\endgroup$
2
  • $\begingroup$ @VIVID Note that my approach is not that great if we were to observe very large numbers or for small number bases. For example, if we were to observe sums of binary digits ($b=2$) instead of decimal digits ($b=10$ in your question), this would not be that great since we would need to compute a new $f_d$ for every single term. (In base $b$, I think we get $b-1$ terms per $f_d$.); I do not know if there is a better approach, i.e. I do not know if there is a better way to find coefficients of $f_d$ other than cracking down the $d$ nested sums. $\endgroup$
    – Vepir
    Sep 5, 2020 at 11:30
  • $\begingroup$ Thank you for your response. I see you have put lots of effort into this answer. Anyway, I wouldn't probably get a better answer in the bounty period. $\endgroup$
    – VIVID
    Sep 8, 2020 at 11:43
4
$\begingroup$

Let us consider a simple case first. Let one of $x$ and $y$ be $0$, say $x=0$. Then we keep incrementing $y$ until the maximum while being safe; the result is 698.

Then we roughly check the corresponding maximum $y$'s for $x=1,2,3,...,698$; during this process, let us pay attention to any regular pattern.

$\mathcal Let\space us\space go!$

  • When $x=0,1,2,3,4,5,6,7,8,9$, $y_{max}=698,598,498,398,298,198,98,88,78,68$ respectively.
  • When $x=10,11,12,13,14,15,16,17,18,19$, $y_{max}=598,498,398,298,198,98,88,78,68,58$ respectively.
  • When $x=20,21,...,29$, $y_{max}=498,398,...,48$ respectively.
  • $...$
  • When $x=60,61,62,63,64,65,67,68,69$, $y_{max}=98,88,78,68,58,48,38,28,18,8$ respectively.
  • When $x=70,71,...,78,79$, $y_{max}=88,78,...,8,7$ respectively.
  • $...$
  • When $x=90,91,...,99$, $y_{max}=68,58,...,5$ respectively.
  • When $x=100,101,...,189$, respective $y_{max}$'s duplicate those for $x=10,11,...,99$ respectively.
  • When $x=190,191,...,198,199$, $y_{max}=58,48,...,5,4$ respectively.
  • When $x=200,201,...,289$, respective $y_{max}$'s duplicate those for $x=110,111,...,199$ respectively.
  • $...$
  • When $x=590,591,...,598,599$, $y_{max}=9,8,...,1,0$ respectively.
  • When $x=600,601,...,689$, respective $y_{max}$'s duplicate those for $x=510,511,...,599$ respectively.
  • When $x=690,691,...,698$, $y_{max}=8,7,...,0$. This is the end by our very first simple case.

I know that it has been a long and tough journey. Hopefully, we have already found some precious regular pattern, making the effort worthwhile.

$\mathcal Here\space is\space some\space space\space for\space you\space to\space think\space about\space it\space on\space your\space own.$

Welcome back! What I have noticed is that for every hundred of $x$, the first $10\space x$'s are 'unique', and the rest $90\space x$'s would be 'copied' by the next hundred of $x$.

Let us list out all $y_{max}$ regardless of the associated $x$'s, i.e. $698,598,...,198,98,88,...,18,8,7,...,1,0.\qquad(*)$

So, for the $i$th hundred of $x$'s, starting from the $i$th element of $(*)$ from the left, the $j$th ten $x$'s correspond to the $j$th ten $y_{max}$'s of $(*)$, where $i=1,2,...,7$ and $j=1,2,...,10$. Note that the $7$th hundred is not exactly a hundred but one less, and the $10$th ten of the $7$th hundred is not exactly a ten but one less as well.

Here comes the calculator part. Well, if you know how to program, then you could save a lot of time! But I do not know how to program, so let me take some time. We want to add up all the $y_{max}$'s covered for all the correspondences except the $698$ because this dimension would not make up any area but mere line segments as you may check.

$\mathcal God\space bless\space me,and\space here\space I\space go!$

  • For the first hundred of $x$'s, summing up $y_{max}$'s: $598\times2+498\times3+\cdot\cdot\cdot+98\times7+88\times6+\cdot\cdot\cdot+68\times10+58\times9+\cdot\cdot\cdot+6\times2+5\times1=11232$.
  • I suddenly realized a little bit more efficient way to summing up all those $y_{max}$'s. We can making up a table of $24$ columns and 8 rows, and by calculating the column sums (ignore the first row for this) first we can save a lot of time!
  • Here is my self-made table. Excuse my messy writing. The Ingenious Table
  • Thus, we can multiply and add: $3\times598+6\times498+\cdot\cdot\cdot+10\times2+6\times1=41653$.

Now, since we increment $x$ by $1$ at a time, so the safe area in the first quadrant is $41653$. But we want the safe area upon all four quadrants; that is easy, $41653\times4=166612$. Finally, we are done!

Remark. I am pretty sure that there is an easier approach. But at least this is one solid way to tackle the problem. Most importantly, we have the final answer, which is rewarding and fulfilling! Last, excuse any minor mistakes above, and I welcome any comment whatsoever. Thank you all!


Sadly, I just realized that I was wrong. Hmm, hopefully my fault could provide some insight for someone to come out with the correct answer. Peace and love.

$\endgroup$
5
  • 4
    $\begingroup$ But the actual answer is $592597$... $\endgroup$ Aug 28, 2020 at 13:20
  • $\begingroup$ That is discouraging indeed. Let me check where I did wrong. Thanks for mentioning that. @AlexeyBurdin $\endgroup$ Aug 28, 2020 at 13:24
  • 1
    $\begingroup$ I know where I went wrong, guys. At least, I have proved one way that does not work. Peace and love. $\endgroup$ Aug 28, 2020 at 13:47
  • 1
    $\begingroup$ @IncredibleSimon Thanks for your try. $\endgroup$
    – VIVID
    Aug 28, 2020 at 13:58
  • 1
    $\begingroup$ Thank you for your thanks, VIVID! <3 @VIVID $\endgroup$ Aug 28, 2020 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .