4

Is there a function $f$ such that

$$f(x,y,n)=f(x+y,y-x,n+1)$$ $$f(x,y,n)\neq f(x+1,y,n)$$ $$f(x,y,n)\neq f(x,y+1,n)$$

where $x,y$ are integers, $n$ is a positive integer and the range of $f$ is a finite set? If so, what is the least number of values $f$ can attain?

EDIT: deleted

EDIT: To make the below pattern nicer here is my final suggestion for an additional condition to make this problem non trivial:

For each $x,y,n$ there should exist an $a>0,b>0$ such that for all $k,l$

$$f(x,y,n)=f(x+ak,y+bl,n)$$

(all numbers are integer, n is positive). This basically states that equal colors should have at least one regular vector grid displacement.

My goal is to reduce the number of colors!

EDIT: Sorry, for the confusion. Here is my explanation what's going on and a last attempt to adjust the conditions.

enter image description here enter image description here enter image description here

These are three consecutive steps in the animation. In the second picture the square move as to make space for new light blue squares. In the third picture the light blue squares have reached their full size and the process starts again. This is a problem I got with coloring a checker board. If anyone would like to translate a Processing Python to Java and post it on Openprocessing, I'd be happy.

SOLUTION: Thanks to Michael the animated pattern now works and looks like: enter image description here

Gere
  • 2,117
  • Note: The $n$ is necessary as $f(0,1,n)\ne f(1,1,n)$ and $f(0,1,n)=f(1,1,n+1)$ – Hagen von Eitzen Jul 10 '15 at 20:12
  • The new condition needs a new colour for each level. All previous colours stay as part of the new level, and all $f(odd,odd,n+1)$ and $f(even,even,n+1)$ are adjacent to the new colour. – Empy2 Jul 10 '15 at 20:58
  • Oh damn. You are right. I cannot get my nice pattern easily. – Gere Jul 10 '15 at 21:06
  • After a few iterations, you can't fit both green and purple on the screen... – Empy2 Jul 10 '15 at 22:44

2 Answers2

2

I can do it with range $\mathbb Z/5\mathbb Z$:

For $n=1$ define $f(x,y,n)=x+y\bmod 5$. Assume for some $n\in\mathbb N$ we have defined $f(x,y,n)$ for all $x,y$ such that properties 2 and 3 hold. We want to define $f(x,y,n+1)$. If $x\equiv y\pmod 2$, we must let $f(x,y,n+1)=f(\frac{x-y}2,\frac{x+y}2,n)$. If $x\not\equiv y\pmod 2$, we can assign $f(x,y,n+1)$ arbitrarily, except that it must differ from $f(x-1,y,n+1)$, $f(x+1,y,n+1)$, $f(x,y-1,n+1)$, $f(x,y+1,n+1)$. As only atmost four values are excluded this is possible.

Hagen von Eitzen
  • 374,180
  • True, that's good understanding. If you don't mind I'd like to add a condition, which I was unconsciously assuming but I forgot to state. – Gere Jul 10 '15 at 20:32
1

EDIT: I try mod 5 instead of mod 3. How about $$[1,3]\left[\begin{array}{cc}3&2\\3&3\end{array}\right]^n\left[\begin{array}{c}x\\y\end{array}\right]\pmod{5}$$
The matrix is to undo the linear transform in the first condition, and the vector is to make things change when you add or subtract 1 from any number.

The formulas are $$f(x,y,1)=x+3y\mod5\\f(x,y,2)=2x+y\mod5\\f(x,y,3)=-x+2y\mod5\\ f(x,y,4)=3x+4y\mod5\\repeat$$

Or, slightly simpler, $2^n(x+3y)\pmod5$

Empy2
  • 50,853