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
    @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
    Didn't know the backticks thing. It'll still come a little handy. Thanks!2011-12-07