작업 네 개에 기계 네 대, 왜 배정이 불가능할까요?

A,B,C,D 네 작업을 서로 다른 기계 1,2,3,4에 하나씩 맡긴다. 가능한 기계는 아래와 같으며 한 기계는 한 작업만 받아요. 기계와 작업의 전체 수가 같고 모든 작업에 후보가 있으니 배정 가능하다는 주장을 판단해 볼까요?

C와 D를 어디에 놓을지부터 여러 경우를 시도할 필요가 없어요. A와 B 두 작업만 떼어 보면 두 작업을 받을 수 있는 기계가 하나뿐이에요. 다른 작업의 후보가 많아도 이 두 작업의 부족을 대신 메울 수 없어요.

작업 집합 U에 서로 다른 기계를 배정하려면 그 작업들이 선택할 수 있는 기계의 합집합 N(U)에 적어도 |U|개가 있어야 해요.

여기서는 이 조건이 하나라도 실패하면 불가능하다는 필요조건만 사용했어요. 모든 부분집합이 이 조건을 만족할 때 항상 가능하다는 일반 정리를 이 짧은 예로 증명한 것은 아니에요.

학생에게 후보 수를 네 행 각각 세게 한 뒤, 두 행을 합쳐 서로 다른 후보를 세게 해요. 중복되는 선택지 하나를 두 자원으로 읽었는지 확인할 수 있어요. 타일링 원문의 이웃 칸 부족을 작업 배정이라는 자체 유한 집합으로 옮기되, 판의 색칠 규칙이나 원문 도판을 복제하지 않았어요.

착안 원문: Aigner-Ziegler / Mathematical Tiling Problems. 문항의 좌표·조건·논증은 새로 구성했어요. 원문 도판이나 활동 지시의 번역이 아니에요.