계수가 0·1뿐인 다항식, 2를 넣은 값 하나가 식을 알려 줘요

계수 0/1 조건에서 P(2)=Q(2)가 P=Q를 보장하는 이유와 P(2)=13의 유일한 식을 검토해요.

전자 부품이 촘촘히 놓인 회로 기판

사진: Ashley Pomeroy · CC BY 4.0 · 원본 출처

P(2)=Q(2),P,Q의 각 계수는 0 또는 1.P(2)=Q(2),\qquad P,Q\text{의 각 계수는 }0\text{ 또는 }1.

P와 Q는 차수에 제한이 없는 다항식이며, P=0이나 Q=0도 허용해요. 두 식은 반드시 같은 다항식일까요? 이어 같은 계수 조건에서 P(2)=13인 P를 구해요.

두 식이 다르다고 가정하고, 계수가 다른 항 중 차수가 가장 큰 것을 n이라 해 볼까요? P−Q에서 그 항의 계수는 1 또는 −1이고 나머지 계수는 −1, 0, 1 중 하나예요. n≥1이면 x=2에서 낮은 차수 항들이 모두 반대쪽으로 더해져도 그 크기는

1+2+⋯+2n−1=2n−1<2n1+2+\cdots+2^{n-1}=2^n-1<2^n

입니다. 가장 높은 항의 값을 지울 수 없으므로 P(2)−Q(2)는 0이 아니에요. n=0이면 차는 상수 1 또는 −1이어서 역시 0이 아니에요. 가정과 모순되므로 P=Q입니다.

13=8+4+1,P(x)=x3+x2+1.13=8+4+1,\qquad \boxed{P(x)=x^3+x^2+1.}

이 식이 조건에 맞고, 앞의 증명이 유일성도 보장해요. 13이라는 값만 보고 차수가 정해진다고 설명하기보다 계수 조건을 어디에 사용했는지 표시하게 해요.

계수를 모든 정수로 허용하면 P=x와 Q=2는 서로 다른데 P(2)=Q(2)=2입니다. 한 값으로 다항식을 구별한 이유는 입력을 2로 골랐다는 사실과 계수가 0 또는 1이라는 조건이 함께 있기 때문이에요.

출처·착안: Always, Sometimes, Never Shapes. 문항과 풀이는 새로 작성했다.

이 글 공유하기

개인정보 및 방문 통계 안내