Two questions on clock arithmetic

120 Views Asked by At

I have two questions on clock arithmetic, both of which I have solved, but I am looking for neater proofs.

Let us suppose we have a circle named $\mathbb{Z}_n$ with $n$ equally spaced points on it labelled $0,1,\cdots n-1$ in the clockwise direction. By clock arithmetic I mean that $x+1$ is the point just after $x$ in the clockwise direction.

$1$. Let $\{a,b\}\subset \mathbb{Z}_n$ so that $\{a+t,b+t\}\ne \{a,b\}\forall t=1,2\cdots n-1$ . Then $\{a+i,b+i\}\ne\{a+j,b+j\}\forall 0\le i<j\le n-1$.

My proof: The hypothesis says that $a$ and $b$ are not on a diameter. Hence no $\{a+i,b+i\}$ is also on a diameter.

$2$. Let $\{a,b\}\subset \mathbb{Z}_n$ with $a>b$ in the ordinary integer ordering sense. Define the distance $d(a,b)$ between $a$ and $b$ as the minimum of the lengths of the two paths from $a$ to $b$ and from $b$ to $a$. By length of a path from $x$ to $y$ we mean the smallest positive $z$ with $x+z=y$. What is a formula for $d(a,b)$? So in $\mathbb{Z}_{19}, d(1,0)=1=d(0,18)$.

My solution: $d(a,b)=a-b$ if $1\le a-b\le \lfloor n/2\rfloor$ and $d(a,b)=n-a+b$ otherwise.

Can someone give an alternate "better looking" formula, possibly one which avoids using $<$ implicitly or explicitly?

2

There are 2 best solutions below

3
On

For the first, you can note that if the conclusion were false, $\{a+i-j,b+i-j\}$ would vilate the hypothesis.

For your second, if $a=1,b=2$ in $\Bbb Z_n$, your formula gives $d(a,b)=n-1$ instead of $1$. You need some absolute value signs to fix this.

3
On

I would present the distance function as

$$d(a,b)=\min(\vert a-b \vert, n - \vert a-b \vert).$$

The casework may be less concrete, but it makes up for it with clarity.