이산수학 비둘기집 원리 모음

소개글

비둘기집 원리 문제모음(기출) 입니다.

목차

없음

본문내용

※ 3X3 바둑판에 수 -1, 0, 1을 써 넣으면 각각의 행에 있는 수들의 합, 각가의 열들에 있는 수들의 합, 그리고 대각선에 있는 수들의 합을 계산하여 8개의 수를 얻을 수 있다. 8개의 수가 서로 다를 수 있는지를 결정하라.

다를 수 없다.

-1, 0, 1을 더하여 나오는 결과들은 -3, -2, -1, 0, 1, 2, 3 으로 총 7개의 숫자가 나온다. 여기서 비둘기 집 원리를 적용하면 7개의 비둘기를 8개의 집에 넣는 것이 되므로 8개의 수 중에서 최소한 2개는 같은 값이 나온다.

n의 배수 문제

정리: 모든 정수 n에 대해서, n의 배수 중에는 0과 1만을 포함하는 십진수가 반드시 존재한다.
▪n을 양의 정수라 하고,
▪n+1개의 정수 1, 11, 111, …, 111× × ×1(1이 n+1개)가 있다고 하자.
▪어떤 정수를 n으로 나누었을 때, 가능한 나머지의 개수는 최대 n개이다.
(나머지의 가능한 범위는 0 ~ n-1 이므로)
▪따라서, 비둘기 집 원리에 의해 상기 n+1개의 정수 중에서 적어도 두 수는 나머지가 같게 된다. 이들 두 수를 각각 x와 y라 하자(x > y).
▪이 두 수 x와 y의 차를 z(= x – y)라 했을 때, z는 n으로 나누어 떨어지고, 이 수는 0과 1로만 표현된다.
(x mod n = y mod n 이므로, z mod n = 0이 된다.)

참고 자료

없음