[Saeko]

While studying some math, I accidentally invented a problem that I can't seem to solve. No fancy-tootin'-high-falutin' math here, just ordinary numbers and formulas.

Let's say you have a formula with the following properties:

0) One input, one output. For example, the formula "take a number and multiply it by 5 to get the answer" has one input (some number) and one output (that number multiplied by 5). I should then be able to put all the numbers along with their answers in a list like this:

1 -> 5
2 -> 10
3 -> 15
4 -> 20
...
and so on

Call the left side the problem list, and call the right side the answer list.

1) No two problems have the same answer.

2) Every number appears exactly once in the list of answers.

This means that a formula like "take a number and add 1 to it" is not valid because it breaks rule 2. If you write out the problem and answer list for this formula

1 -> 2
2 -> 3
3 -> 4
4 -> 5
...

You can see that the number 1 never appears in the answer list.

However, a formula like "take a number and don't do anything to it" is a valid formula, which you can check. But so is the formula with the following problem-answer list

1 -> 2
2 -> 1
3 -> 4
4 -> 3
5 -> 6
6 -> 5
...

Note that a formula can be specified entirely by its problem-answer list. You don't have to come up with a rule for it like "if the number is odd then add 1 and if its even then subtract 1", but it helps if you do.

Now, what's interesting is that many of the formulas which satisfy the above 3 rules have cycles. What I mean is that if you apply the above formula to 1 over and over again, you get

1 -> 2 -> 1 -> 2 -> ... and on and on forever.

However, there are some that don't and my first challenge to you is to find one that a) satisifies the three rules above and which b) never repeats no matter which number you give it first and no matter how many times you apply the formula.

MY SOLUTION (DO NOT PEAK UNTIL YOU'VE TRIED TO SOLVE THE FIRST CHALLENGE)

Spoiler: show

One possible formula is "take a number, and if it is odd, then add 2. If it is even and greater than 2, then subtract 2. And if it is 2, then subtract 1".

The problem-answer list for this formula is

1 -> 3
2 -> 1
3 -> 5
4 -> 2
5 -> 7
6 -> 4
7 -> 9
8 -> 6
...

Proof that this is a solution:

If you start with any even number, for example, 10, you get

10 -> 8 -> 6 -> 4 -> 2 -> 1 -> 3 -> 5 -> 7 ->....

That is, you eventually get to 2, then to the odd numbers.

And for any odd number, you just keep going to the next higher odd number.

Thus, no matter what number we start with the formula never repeats that number.

----End of proof------

Now, what's interesting about this is that once you've found one solution, you've found infinitely many others. If we take the list of problems, and then apply the above rule twice, we get

1 -> 3 -> 5
2 -> 1 -> 3
3 -> 5 -> 7
4 -> 2 -> 1
5 -> 7 -> 9
6 -> 4 -> 2
7 -> 9 -> 11
8 -> 6 -> 4
9 -> 11 -> 13
10 -> 8 -> 6
...

Now, take the first and third columns as our problem-answer list, and you get another solution

1 -> 5
2 -> 3
3 -> 7
4 -> 1
5 -> 9
6 -> 2
7 -> 11
8 -> 4
...

This formula is the result of applying the first formula twice. You can do this any number of times to get a new solution each time.

You can also reverse the arrows in each of these solutions to get another solution.

Thus, we have infinitely many solutions which can all be obtained from either applying the first solution multiple times, or taking any known solution and reversing the arrows. The second challenge then, and this is what I can't solve, is to find a formula, which, when applied twice, results in the same answer list as the first formula above.

EDIT: Or prove that this can't be done.

EDIT2: If you find a solution, call it 1. Then combining it with itself, you get a new solution which you can call 2, and so on. Now if you reverse the arrows in a solution, then you get a negative numbered solution. Combining solutions is the same as adding their numbers, and if you combine 5 with -5 for example, you get the identity rule which corresponds to 0. Cool huh?

[Rancid]

Math? Fuck this shit.

[lucky]

Your functions are called "permutations" (of the positive integers). Doing one permutation and then another is called multiplying permutations (note that this is not necessarily commutative). Applying a permutation n times is called taking the n-th power of a permutation. n can be negative like you describe.

The solution to your puzzle is: it's impossible.

Let's call your permutation f. You want a permutation g such that g^2 = f. Suppose you find one.
Let a = g(1).
Since every number can be reached by f from 1, or 1 can be reached from it, we have:
a = f^k(1) for some (positive or negative) k.
So:
a = f^k(1) = g^(2k)(1) = g^(2k-1)(g(1)) = g^(2k-1)(a)
f^(2k-1)(a) = g^(4k-2)(a) = g^(2k-1)(g^(2k-1)(a)) = g^(2k-1)(a) = a
Therefore f has a cycle, which we know it hasn't. A contradiction.

[Saeko]

^ Nice! I'm gonna check this proof later.

[Saeko]

Your functions are called "permutations" (of the positive integers). Doing one permutation and then another is called multiplying permutations (note that this is not necessarily commutative). Applying a permutation n times is called taking the n-th power of a permutation. n can be negative like you describe.

The solution to your puzzle is: it's impossible.

Let's call your permutation f. You want a permutation g such that g^2 = f. Suppose you find one.
Let a = g(1).
Since every number can be reached by f from 1, or 1 can be reached from it, we have:
a = f^k(1) for some (positive or negative) k.
So:
a = f^k(1) = g^(2k)(1) = g^(2k-1)(g(1)) = g^(2k-1)(a)
f^(2k-1)(a) = g^(4k-2)(a) = g^(2k-1)(g^(2k-1)(a)) = g^(2k-1)(a) = a
Therefore f has a cycle, which we know it hasn't. A contradiction.

Ok, so after going over it a few times, I don't think that this proof works.

I think that the mistake is here:

"Since every number can be reached by f from 1, or 1 can be reached from it, we have:
a = f^k(1) for some (positive or negative) k."

This is not true for all a. In particular, if we take my first solution from above, call it f_1 then f_1(2) = 1, but then there is no k such that f_1^k(1) = 2.

Furthermore, the proof does have a counterexample. We have the permutation f_2 = f_1 by f_1. Applying the above proof to f_2 would imply that f_2 is not equal to f_1 by f_1, which would then be a contradiction.

EDIT:

Math? Fuck this shit.

A theorem a day keeps the stupid away.

[lucky]

In particular, if we take my first solution from above, call it f_1 then f_1(2) = 1, but then there is no k such that f_1^k(1) = 2.

k = -1. If f(2) = 1, then f^-1(1) = 2.

Furthermore, the proof does have a counterexample. We have the permutation f_2 = f_1 by f_1. Applying the above proof to f_2 would imply that f_2 is not equal to f_1 by f_1, which would then be a contradiction.

The proof wouldn't work for f^2 = f*f because the first step of the proof would be false for f^2: it's not true for f^2 that everything is reachable from 1 forwards or backwards (for instance, 2 isn't). f^2 has 2 separate connected components.

This actually leads to another, perhaps more intuitive, proof of impossibility: for any permutation p, p^2 splits infinite connected components into 2 disjoint components. Since your permutation has only one infinite component, the square root cannot exist.

[Saeko]

The proof wouldn't work for f^2 = f*f because the first step of the proof would be false for f^2: it's not true for f^2 that everything is reachable from 1 forwards or backwards (for instance, 2 isn't). f^2 has 2 separate connected components.

This actually leads to another, perhaps more intuitive, proof of impossibility: for any permutation p, p^2 splits infinite connected components into 2 disjoint components. Since your permutation has only one infinite component, the square root cannot exist.

I think you're right. Very interesting.

EDIT:

In English, what Lucky is saying is that the first solution, if you draw out its history looks like this:

... -> 10 -> 8 -> 6 -> 4 -> 2 -> 1 -> 3 -> 5 -> 7 -> 9 ->...

It consists of a single piece.

But if you apply it twice you get

... -> 10 -> 6 -> 2 -> 3 -> 7 -> ...
... -> 8 -> 4 -> 1 -> 5 -> 9 -> ....

which has two disconnected pieces.

Presumably then, applying the formula 3 times produces 3 pieces and so on.

[Heisenberg]

Maths, not math. Bloody colonials.

[Bulaba Khan Jones]

You'd think that ever since AMERICA colonized the British Isles thousands of years ago and then fought on their behalf for their war of independence from Napoleon in 1776 that the British would be grateful to us and not mouth off. Instead, you try to tell us how to say "math" properly? Pssht. Bloody colonials, indeed.

[Saeko]

Maths, not math. Bloody colonials.

No. It's spelled mathematics, not mathsematics. Goddamn limeys.

[noemon]

Bloody barbarians all!

Μαθηματικα.

[Prosthetic Conscience]

In English, what Lucky is saying is that the first solution, if you draw out its history looks like this:

... -> 10 -> 8 -> 6 -> 4 -> 2 -> 1 -> 3 -> 5 -> 7 -> 9 ->...

It consists of a single piece.

But if you apply it twice you get

... -> 10 -> 6 -> 2 -> 3 -> 7 -> ...
... -> 8 -> 4 -> 1 -> 5 -> 9 -> ....

which has two disconnected pieces.

Presumably then, applying the formula 3 times produces 3 pieces and so on.

I was using a visual picture like that last night, but could quite get the proof of why you can't find the function you were looking for into words. I guess you can put it as:
if your first solution is a single piece, ie one containing all the positive numbers (which I think is the full set of numbers you have restricted yourself to, though I have seen that specified anywhere), then it will be impossible to find any function that inserts a number between any pair in that list of numbers, since all numbers are already in it, and you can't have a number appear twice.

[Nets]

I got the first part with the same function Saeko found. (I knew f(z)=z+1 worked for Z, and Z is just N relabeled, so I knew there had to be something that worked for N.)

Didn't get a chance to think about the second part yet.

[Nets]

dlt

[Nets]

dlt

[Ummon]

Are you saying that 0 is not a number? I don't understand why 0 -> 1 would be a violation of rule 2.

[Saeko]

Are you saying that 0 is not a number? I don't understand why 0 -> 1 would be a violation of rule 2.

You have to decide what number system to use beforehand. In my case, I chose the natural numbers (1,2,3,...) which commonly do not include 0.

If you are using the natural numbers with 0, then 0 -> 1 is fine, but then no number goes to 0.

[Ummon]

Can you clarify rule 3?

(You didn't explicitly state it in the post)

I'm not sure, but I have a feeling that lucky's outputs might repeat on successive applications of the same function, but I'd have to check. I like these little challenges.

[Saeko]

Can you clarify rule 3?

(You didn't explicitly state it in the post)

I'm not sure, but I have a feeling that lucky's outputs might repeat on successive applications of the same function, but I'd have to check. I like these little challenges.

There is no rule 3. The third rule is rule 2, and the first rule 0. You see? This is why you shouldn't use voodoo like 0 kids.

[AuRomin]

2) Every number appears exactly once in the list of answers.

I chose the natural numbers

Assuming all natural numbers as the set of numbers in which every number appears exactly once, you would have to start at infinity in order to reach all even numbers. Infinity is not a number and therefore cannot be used in your function. I don't see how this is a valid answer.

Please inform me of how or if I'm wrong.