Skip to main content
deleted 19 characters in body
Source Link
Dan Piponi
  • 8.3k
  • 5
  • 64
  • 92

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. There's no choice. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. There's no choice. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

added 162 characters in body
Source Link
Dan Piponi
  • 8.3k
  • 5
  • 64
  • 92

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. There's no choice. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. There's no choice. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats!

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. There's no choice. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

Source Link
Dan Piponi
  • 8.3k
  • 5
  • 64
  • 92

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. There's no choice. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats!