function application [closed]

Question

Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement. For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following statements hold:

down(x+1,y)=(x,y+1)

down(0,y+1)=(y,0)

cane(p)= 0 if down(p) is undefined

cane(p)=1+cane(down(p)) if both down(p) and cane(down(p)) are defined.

(NOTE: p above is a pair.)

For every x∈ℕ and y∈ℕ such that x+y ≤ 2 (there are six such pairs), calculate the value, if there is one, of down(x,y) and also of cane(x,y). Put your answers in two tables, one for down and one for cane, of this form:

table

Hint: It might help you for the later parts of this question if you he k these two functions with more values for x and y.

Describe in words how the function cane and its auxiliary helping function down work, and what they accomplish. Explain any wider significance ane these functions might have. My question is how am I supposed to fill in this table;

for example if I take in x to be 0 and y to be 0 then my down function would be as follows;

down(0+1,0)=(0,0+1)==(1,0)=(0,1) and down(0,0+1)=(0,0)==(0,1)=(0,0) I believe then that when x=0 and y=0 then the position in the table is "undefined" and true for all other coordinates of the table because they form a trail back to (0,0).

Could someone please help me understand this?

Answer 1

The down function is moving along (something essentially equivalent to) the usual Cantor pairing function $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, since it moves from each point on a diagonal $x+y=\text{constant}$ to the next point until the diagonal runs out at the y-axis, and then it jumps to the next lower diagonal.

Meanwhile, the cane function counts how many times that happens before you hit the origin. So the cane function is the precisely a version of the usual Cantor pairing function. Your function differs from the usual function in that it swaps $x$ and $y$ from the usual function, since Cantor's function goes down and to the right, rather than up and the to left as with your recursion; but this is an inessential difference. In the end, the function maps a pair $(x,y)$ to the code of that pair.

In fact, the function $\text{cane}(x,y)$ is a quadratic polynomial in $x$ and $y$, and I challenge you to figure out the precise formula. All you need to do is to count the number of points on earlier diagonals, which is a triangular number, and then count the number of points on the current diagonal up to the point $(x,y)$. This gives a quadratic formula for $\text{cane}(x,y)$.