위키득계정 ↗
과학

나머지류와 두 원소의 합이 제한된 부분집합

나머지류와 두 원소의 합이 제한된 부분집합과학
기초 개념
합동과 나머지류
분류 기준
양의 정수 m으로 나눈 나머지
금지되는 짝
합이 0이 되는 나머지의 조합
최댓값 증명
상한 도출과 실제 구성
정수를 나머지별로 분류하고 서로 보완적인 나머지의 짝을 이용해 부분집합 크기의 최댓값을 구하는 방법.

정수를 일정한 양의 정수로 나눈 나머지에 따라 분류하면, 많은 수 사이의 덧셈 조건을 적은 수의 경우로 바꿀 수 있다. 특히 서로 다른 두 원소의 합이 특정 정수의 배수가 되지 않도록 부분집합을 구성하는 문제에서 유용하다.

합동과 나머지류

두 정수 a와 b의 차가 m의 배수일 때 a와 b는 m을 법으로 합동이라고 하며 a ≡ b (mod m)으로 쓴다. 이는 두 정수를 m으로 나눈 나머지가 같다는 뜻이다. 나머지 r에 해당하는 원소들의 집합을 A_r로 두면 원래 집합은 A_0부터 A_(m-1)까지 나누어진다.

두 원소의 합과 보완적인 나머지

a의 나머지가 r이고 b의 나머지가 s이면 a+b의 나머지는 r+s의 나머지와 같다. 따라서 두 수의 합이 m의 배수인지 여부는 원래 수 전체를 더하지 않고 나머지만으로 판단할 수 있다.

1 ≤ r < m인 경우 A_r와 A_(m-r)에서 각각 한 원소를 고르면 그 합은 m의 배수다. 이 조건을 피하려면 두 나머지류를 동시에 사용할 수 없다. A_0에서도 서로 다른 두 원소를 선택하면 그 합이 m의 배수가 되므로 최대 한 원소만 고를 수 있다.

홀수인 법에서의 최대 크기

m이 홀수일 때 0이 아닌 나머지들은 (1, m-1), (2, m-2)와 같은 서로 다른 짝으로 묶인다. 각 짝에서는 원소 수가 더 많은 쪽의 나머지류를 선택하면 된다. 선택한 한 나머지류 내부의 두 원소는 합이 m의 배수가 되지 않는다. 따라서 각 짝의 큰 원소 수를 더하고, A_0가 비어 있지 않으면 1을 더한 값이 최대 크기다.

예를 들어 1부터 20까지의 수를 5로 나누면 각 나머지류에 원소가 4개씩 있다. (1,4)와 (2,3)의 짝에서 각각 한쪽을 고르고 나머지 0인 수를 하나 고르면 최대 크기는 4+4+1=9다. 나머지가 0, 1, 2인 수만 사용하되 0인 수는 하나만 사용하는 방식으로 이를 실제로 구성할 수 있다.

짝수인 법과 조건의 범위

m이 짝수일 때에는 나머지 m/2인 두 원소의 합도 m의 배수가 되므로 해당 나머지류에서 최대 한 원소만 선택한다. 또한 이 방법은 ‘서로 다른 두 원소’라는 조건을 전제로 한다. 같은 원소를 두 번 사용하는 경우까지 금지하면 나머지 0인 원소 등의 취급이 달라진다.

참고 자료

MIT Mathematics for Computer Science: Congruences — 합동, 나머지와 덧셈의 성질