Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

f(f(x)) = -x

Puzzle

Is it possible to write a function int f(int x) in C that satisfies f(f(x)) == -x? Without globals and static variables, of course.

Source

Heard from a fellow student at UC Berkeley in 1997.

Solution

f(0) must equal 0. If not, then f(0) must equal some non-zero b, so f(b) must equal 0, in which case, f(f(b)) ≠ -b. If f(0) = 0, it follows that f(a) ≠ 0 for any non-zero a. And for non-zero a, f(a) ≠ a.

For non-zero a, let f(a) = b, where b ≠ 0. It follows that f(b) = -a, f(-a) = -b and f(-b) = a. In other words, if f(f(x)) == -x for all x, then the set of non-zero integers gets divided into disjoint cycles of size 4, where each cycle is of the form {a, b, -a, -b}. There are two positive and two negative integers in any such cycle. Any function f that divides non-zero integers into such cycles suffices. There are many such functions if we allow all positive and negative integers in the domain. However, when the domain is k-bit numbers for any k, the total number of numbers that can be represented is even, and one of these numbers is always 0. So the number of positive and negative integers allowed by k-bit representations is never the same! Therefore, we can never divide the non-zero integers among the set of k-bit numbers into disjoint cycles of the form {a, b, -a, -b}. Therefore, no f exists such that f(f(x)) == -x in C for k-bit numbers, for any k.

Previous Puzzle: Cap Colors

An evil troll once captured a bunch of gnomes and told them, "Tomorrow, I will make you stand in a file, ordered by height such that a gnome can see exactly those gnomes that are shorter than him. I will place either a white cap or a black cap on each head. Then, starting from the tallest, each gnome has to declare aloud what he thinks the color of his own cap is. In the end, those who were correct will be spared; others will be eaten, silently." The gnomes set thinking and came up with a strategy. How many of them survived?

Next Puzzle: Card Shuffling

A perfect in-shuffle of a deck of 52 cards is defined as follows. The deck is cut in half followed by interleaving of the two piles. So if the cards were labeled 0, 1, 2, ..., 51, the new sequence is 0, 26, 1, 27, 2, 28, ... With repeated in-shuffles, shall we ever get back the original order? In how many iterations?

16 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.