1
$\begingroup$

Imagine filling a grid diagonally, like in Cantor's diagonal argument: \begin{array}{ |c|c|c|c|c|c|} \hline 1 & 3 & 6 & 10 & 15 & \dots \\ 2 & 5 & 9 & 14 & 20 & \dots \\ 4 & 8 & 13 & 19 & 26 & \dots \\ 7 & 12 & 18 & 25 & 33 & \dots \\ 11 & 17 & 24 & 32 & 41 & \dots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \hline \end{array} My question is, given some $n$, what are the formulae that tell us which row and column it will get put in?

e.g. $C(1) = (1,1)$, $C(2) = (1,2)$, $C(3) = (2,1)$, ... $C(n) = (i_n,j_n)$; what are $i_n$ and $j_n$ in terms of $n$?

$\endgroup$
  • $\begingroup$ There has to be a duplicate somewhere on the MSE, but in the absence of one I can find, here's a hint: the top row is the set of triangular numbers. $\endgroup$ – Parcly Taxel Feb 9 '18 at 7:09
1
$\begingroup$

We have $C(i,\,j)=C(1,\,i+j-1)-i+1$, which you can write as a quadratic using $C(1,\,j)=j(j+1)/2$. Now you should be able to solve $C(i,\,j)=n$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.