0
$\begingroup$

Let $m$ be an even natural number. Find natural numbers $x$ and $y$ such that $$ m=(x+y)^2+3x+y$$

Try a few cases to find pattern and then use induction to prove that the pattern works.

P.S I saw this problem on one of the textbooks about discrete math. I tried a couple of approaches but they all failed. One of them is to determine whether $x$ and $y$ are all even or odd.

  • 0
    If you try up to $m=12$ you'll see that they don't need to be all even or odd : $12 = (0+3)^2 + 3 \cdot 0 + 3$.2011-12-07

3 Answers 3

4

By trial and error I constructed the following table:

$$\begin{array}{c|c|c|c|c}\rm{Block}&m/2&m&x&y\\ \hline 1&0&0&0&0\\ \hline 2&1&2&0&1\\ &2&4&1&0\\ \hline 3&3&6&0&2\\ &4&8&1&1\\ &5&10&2&0\\ \hline 4&6&12&0&3\\ &7&14&1&2\\ &8&16&2&1\\ &9&18&3&0\\ \hline \end{array}$$

I think that it makes the pattern fairly clear, but I’ve inserted some horizontal lines to make it even more apparent. See if you can prove it; if not, I’ll add to the answer.

Added: It’s helpful to consider $m/2$, so I’ve added it to the original table, as well as block numbers. Note that each block starts with $m/2$ equal to a triangular number (a sum of consecutive integers starting at $0$): $0,1,3,6,10,\dots$. Specifically, the first value of $m/2$ in Block $n$ is $\sum_{k=0}^{n-1}k=\binom{n}2$. Thus, the values of $m/2$ in Block $n$ run from $\binom{n}2=\frac12 n(n-1)$ through $\binom{n+1}2-1=\frac12 n(n+1)-1$, and therefore $m$ runs from $n(n-1)$ through $n(n+1)-2$. Moreover, there are $n$ values of $m$ in Block $n$, and within Block $n$ $x$ runs consecutively from $0$ through $n-1$, while $y=n-1-x$.

We therefore conjecture that given $m$, we can find $x$ and $y$ as follows. First find the number, $n$, of the block containing $m$: $$n=\max\{k:k(k-1)\le m\}\;.\tag{1}$$ Then let $x=\frac12\big(m-n(n-1)\big)$, and let $y=n-1-x$.

To verify the conjecture, note that $x+y=n-1$, so

$$\begin{align*} (x+y)^2+3x+y&=(x+y)^2+(x+y)+2x\\ &=(n-1)^2+(n-1)+m-n(n-1)\\ &=n(n-1)+m-n(n-1)\\ &=m\;, \end{align*}$$

as conjectured. It only remains to show that $x$ and $y$, as given by this algorithm, are always non-negative. Since $x+y=n-1$, this amounts to showing that $0\le x

By definition $n(n-1)\le m$, so $x=\frac12\big(m-n(n-1)\big)\ge 0$. On the other hand, the maximality of $n$ implies that $(n+1)n>m$ and hence that

$$\begin{align*} x&=\frac12\big(m-n(n-1)\big)\\ &<\frac12\big((n+1)n-n(n-1)\big)\\\\ &=n\;. \end{align*}$$

It might be objected that $(1)$ isn’t a very handy way to calculate $n$. However, it amounts to saying that $n$ is the unique positive integer satisfying $$n(n-1)\le m<(n+1)n\;,$$ which is true iff $$n^2-n\le m This can be rewritten as $$\left(n-\frac12\right)^2-1\le m<\left(n+\frac12\right)^2-1\;,$$ $$n-\frac12\le\sqrt{m+1}< n+\frac12\;,$$ $$n\le \sqrt{m+1}+\frac12 and finally as $$n=\left\lfloor\sqrt{m+1}+\frac12\right\rfloor\;.$$

Note that no induction is actually required.

  • 0
    I can see the pattern here. For $$m = \{20,22,24,26,28\}, (x,y) = (0,4),(1,3),(2,2),(3,1),(4,0)$$ respectively. But I still cannot find a general formula of it. And I saw someone help me tag the question with (diophantine-equations), how does this question relate to diophantine equations in general?2011-12-07
  • 0
    @John: Diophantine equations are equations that require integer or rational solutions. Did you not give a restriction like this in your question?2011-12-07
2

Hint: You might look up the Cantor pairing function (will need to divide by $2$).

1

Look at this Mathematica code : MatrixForm[Table[(x + y)^2 + 3 x + y, {x, 0, n}, {y, 0, n}]]

for some value of $n$. For $n=5$, for instance, you get $$ \begin{bmatrix} 0 & 2 & 6 & 12 & 20 & 30 \\ 4 & 8 & 14 & 22 & 32 & 44 \\ 10 & 16 & 24 & 34 & 46 & 60 \\ 18 & 26 & 36 & 48 & 62 & 78 \\ 28 & 38 & 50 & 64 & 80 & 98 \\ 40 & 52 & 66 & 82 & 100 & 102 \\ \end{bmatrix} $$ The pattern is quite obvious : When letting $(x,y)$ going in the sequence $(0,n), (1,n-1), \dots, (n-1,1), (n,0)$, the integers $m$ appearing are all the even integers going from $n^2+n$ to $n^2 + 3n$. Note that $n^2 + 3n + 2 = (n+1)^2 + (n+1)$, so that you can "patch" $2\mathbb N$ with intervals like [$n^2 + n, n^2 + 3n]$. Now you go prove that. =)

Hope that helps,

  • 0
    Is there anyway we can just input mathematica code in here? It would be amazingly efficient if simply putting some weird braces to get in mathematica environment would allow us to plot/show stuff, without the need of computing, just the results.2011-12-07
  • 0
    Not really; we just indicate that something is code with backticks: ``.2011-12-07
  • 0
    Didn't know the backticks thing. It'll still come a little handy. Thanks!2011-12-07