네 입력에 0과 1을 정하는 함수, 왜 16개가 아니라 4개일까?

X=\{0,1,2,3\},\qquad f:X\to\{0,1\}

모든 x∈X에서

f(f(x))=1-f(x)

를 만족하는 함수의 개수를 구하라. 네 입력마다 두 값 중 하나를 고르니 2⁴개라는 답을 검토한다.

어떤 함수값 c=f(x)는 0 또는 1이다. 조건은 f(c)=1−c이므로, c=0이면 f(0)=1이고 c=1이면 f(1)=0이다. 이 관계 때문에 0과 1이 모두 함수값으로 쓰인다. 결국

\boxed{f(0)=1,\qquad f(1)=0}

이 강제된다.

이미 정해진 값	자유롭게 정할 값
f(0)=1, f(1)=0	f(2), f(3)는 각각 0 또는 1

따라서 함수는 2²=4개다. 거꾸로 이 네 함수는 f(x)=0일 때 f(f(x))=f(0)=1, f(x)=1일 때 f(f(x))=f(1)=0이므로 모든 입력에서 조건을 만족한다.

2⁴는 합성 조건을 붙이기 전의 개수다. 각 선택이 여전히 자유로운지 먼저 확인하고, 마지막에는 네 후보의 충분성까지 검산한다.

출처·착안: Dan Meyer, 「Plates Without States」. 문항과 풀이는 새로 작성했다.