Seeking a derangement $S: \{0,1\}^4 \to \{0,1\}^4$ for which changing one bit in the input always changes at least two bits in the output

94 Views Asked by At

Kindly asking for any hints about the following question:

Define a function $ S : \{0,1\}^4 \to \{0,1\}^4$ with this conditions:

1- For any $x$, $\ S(x) \neq x $

2- for any $x \neq y$, $\ S(x) \neq S(y).$

3- Changed one bit in the input always changing at least two bits in the output.

2

There are 2 best solutions below

0
On BEST ANSWER

After not getting systematically, I looked for solutions (there seem tobe gazillions) by backtracking Try this $$ 0000\mapsto 0001\\ 0001\mapsto0010\\ 0010\mapsto0100\\ 0011\mapsto0111\\ 0100\mapsto0110\\ 0101\mapsto1000\\ 0110\mapsto0011\\ 0111\mapsto1101\\ 1000\mapsto1010\\ 1001\mapsto0101\\ 1010\mapsto1111\\ 1011\mapsto1100\\ 1100\mapsto1001\\ 1101\mapsto1110\\ 1110\mapsto0000\\ 1111\mapsto1011$$

0
On

One solution would be the function that shifts each bit to the left (except from $0000$ and $1111$). Mathematically, it can be described as \begin{align*} f(x)=\begin{cases} 1111 &\text{if }x=0000\\ 0000 &\text{if }x=1111\\ 2x \mod{15} &\text{else} \end{cases} \end{align*} EDIT: I just realized that the third condition is not fulfilled.