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

X={0,1,2,3}, f:X→{0,1}이며 모든 x에서 f(f(x))=1−f(x)입니다. 이 조건은 f(0)=1, f(1)=0을 강제해요. f(2),f(3)만 각각 두 선택이 남아 함수는 4개예요. 2⁴는 조건을 붙이기 전의 개수예요.

연결된 금속 기어와 기계 지지대

사진: San Diego Air & Space Museum Archives · Public domain · 원본 출처

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

모든 x∈X에서

f(f(x))=1−f(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이 모두 함수값으로 쓰여요. 결국

f(0)=1,f(1)=0\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」. 문항과 풀이는 새로 작성했다.

이 글 공유하기

개인정보 및 방문 통계 안내