강의자료/이산수학문제풀이 13

[정보올림피아드대비]13. 시계문제

시계문제는 시계의 시침과 분침을 연구하는 문제입니다. 시계의 둘레를 60칸으로 나누면 분침이 60칸 움직일때 시침은 5칸 움직입니다. 그러므로 시침의 속도는 분침의 5 / 60 = 1/12 입니다. 따라서 분침과 시침이 현재 만나 있는 상태에서 다음에 만나는 시간은 분침이 이동하는 시간 x = 60 + x * 1/12 이 됩니다. 따라서 x * 11/12 = 60 이므로 x = 60 * 12/11 = 65 와 5/11 분 후에 만나게 됩니다. 시계문제는 다양하고 또 많은 지식도 들어가 있습니다. 여기서 기본 공식을 소개하면 처음 시각에 따라잡아야 할 칸 수 / (1-1/12) = 따라잡는 격시간(분) 이고 그 중 (1-1/2)는 매분 분침이 시침보다 더 간 칸수입니다. 1. 현재 시각은 3시입니다. 분침..

[정보올림피아드 대비]12. 비둘기집의 원리를 이용한 문제

비둘기집의 원리는 다음과 같습니다. 비둘기집은 2개이고 비둘기는 3마리입니다. 비둘기가 저녁에 잠을 자기 위해 들어가야 되는데~ 그렇다면 반드시 한개의 비둘기 집에는 비둘기가 2마리 이상 존재하게 된다는 원립니다. 이러한 원리를 다음과 같이 정의 됩니다. n개의 배둘기집과 n+1마리의 비둘기가 있다고 가정한다. 만약 각 비둘기집에 한마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 존재한다. 그런데 비둘기는 모두 n+1마리 이므로 이것은 모순이다. 따라서 어느 비둘기집에는 두마리 이상의 비둘기가 있다. 이것을 일반화된 원리로 정의를 하면 다음과 같이 정의 된다. n개의 별개의 사물을 m개의 용기에 담으면 적어도 한개의 용기는 n/m 이상의 사물을 담고 있어야 한다. 1. 어느..

[정보올림피아드대비]11.소가 풀을 먹는 문제

목장에 같은 속도로 자라는 풀밭이 있는데 27마리 소가 6주 또는 23마리 소가 9주 동안 먹을 수 있습니다. 그러면 21마리 소가 몇주 먹을 수 있습니까? 이런 유형의 문제를 소가 풀을 먹는 문제라고 합니다. 이러한 문제를 푸는데 중요한 것은 풀의 총량이 변하고 매일, 매주마다 같은 속도로 자라며 시간이 많이 지날수록 풀의 총량도 많아지는 것입니다. 풀의 총량은 두개 부분입니다. 1) x시간 전에 풀밭에 있는 풀의 양 2) x시간 후에 풀밭에 매일(매주) 새로 자라는 풀의 양입니다. 그렇다면 위의 문제를 분석해 봅시다. 27마리 소가 6주동안 먹은 풀 : 원래의 풀 + 6주간 자라는 풀 23마리 소가 9주동안 먹은 풀 : 원래의 풀 + 9주간 자라는 풀 따라서 27마리 소가 6주동안 먹은 풀의 양은 1..

[정보올림피아드대비]10. 약수,배수,최대공약수,최소공배수를 이용한 문제

1. 약수와 배수 a,b,c 는 자연수 이고 b ≠ 0 , a ÷ b = c , 즉 자연수 a 나누기 b 는 c 이고 나머지는 없다면 a를 b의 배수 라고 하고 b는 a의 약수라고 합니다. 예) 15 ÷ 3 = 5 에서 15는 3의 배수이고 3은 15의 약수입니다. 2. 소수와 합성수 한 수가 1과 그 수 자체를 제외하고 다른 약수가 없을때 그 수를 소수라고 합니다. 한 수가 1과 그 수 자체를 제외하고 다른 약수가 있을때 그 수를 합성수라고 합니다. ※ 단, 1은 소수도 합성수도 아닙니다. 3. 소수와 소인수 분해 만약 한 소수가 어떤 수의 약수이면 이 소수를 어떤 수의 소인수라고 합니다. 어떤 합성수를 소인수들의 곱으로 표시했을 때 이것을 소인수분해라고 합니다. 예) 30을 소인수 분해 하면 2 * ..

[정보올림피아드대비]9. 나누어 떨어짐을 이용하는 문제(배수판정법)

1. 수의 나누어 떨어지는 성질 성질1 : 만약 a,b,c 가 모두 c 에 의하여 나누어 떨어지면 그들의 합과 차도 모두 c에 의하여 나누어 떨어집니다. 즉 만약 c|a,c|b 이면 c|(a±b) 도 성립됩니다.(단, 여기서 c|a 의 의미는 a가 c로 나누어 떨어진다는 의미입니다.) 예) 2|10,2|6 이면 2|(10+6), 2|(10-6) 입니다. 성질2 : 만약 b와 c의 곱이 a를 나누어 떨어지게 하면 b와 c도 a를 나누어 떨어지게 할 수 있습니다. 즉 만약 bc|a 이면 b|a,c|a 도 성립합니다. 예) 2*5|30 이면 2|30,5|30 이 성립됩니다. 성질3 : 만약 b와 c가 모두 a를 나누어 떨어지게 하고 b와 c가 서로소이면, b와 c의 곱도 a를 나누어 떨어지게 합니다. 즉 b|..

[정보올림피아드대비]8.조합에관한문제

조합은 Combination 이라고 하며 순서를 생각하지 않고 나열하는 경우를 말한다. 즉 123 과 321 은 같은 경우로 생각하는 경우이다. 이러한 문제는 중고등부 유형이나 혹은 알고리즘 유형에서 나오는 문제이다. 다음의 문제를 풀어 보자. 문제풀이) 더보기 1) 남자 13명 중에서 3명을 뽑는 경우의 수는 첫번째 13명중에서 1명을 뽑는 13가지 두번째 첫번째 뽑힌 사람을 제외하고 12명 중에서 1명을 뽑는 12가지 세번째 는 남은 11명 중에서 1명을 뽑는 11가지 즉 13P3 = 1716 이다. 여기서 남자에게 번호를 1~13까지 번호를 붙여 본다면 1번,2번,3번을 선택한 경우는 123,132,213,231,312,321 과 같이 6가지이다. 하지만 이렇게 6가지의 경우는 동일하게 하나로 선택..

[정보올림피아드대비]7. 순열에 관한 문제(곱의법칙,합의법칙)

더보기 문제풀이) 더보기 2학년부터 4학년 학생중 학점이 3.0 이상인 학생은 2학년 - 22명 3학년 - 28명 4학년 - 18명 2학년 3.0 이상인 학생이 3학년 3.0 또는 4학년 3.0 이상인 학생과 중복 되는 경우가 없으므로 경우의 수는 22 + 28 + 18 = 68 가지 이다. [문제풀이] 더보기 문제풀이) 더보기 1) 한가지만 선택하는 경우이므로 한가지를 선택하면 다른 것을 선택 할 수 없다. 따라서 합의 법칙에 해당한다. 5+2+4+3 = 14 2) 각각 하나씩 선택을 해야 하므로 곱의 법칙에 해당한다. 5 * 2 * 4 * 3 = 120 문제풀이) 더보기 첫째자리에 4가지를 선택 할 수 있다. 둘째자리에 첫째자리에서 선택한 1가지를 제외한 3가지를 선택할 수 있다. 셋째 자리에 첫째자..

[정보올림피아드대비]6.숫자로 진 만들기(복면산연산)

숫자로 진을 만드는 것은 일정한 조건에 맞게 여러가지 도형으로 배열하는 문제입니다. 숫자진은 일종의 숫자 그림으로 숫자진 그림에 관한 문제의 종류는 다양하지만 여기서는 밀봉형 숫자진,부채꼴 숫자진,복합형 숫자진에 대해서 알아 보겠습니다. 1. 1~8의 8개의 자연수를 각각 아래 그림의 8개의 동그라미 안에 써 넣어 사각형 각 변 위의 3개의 숫자의 합이 모두 14가 되게 하고, 또한 숫자 1은 사각형의 한 꼭짓점 위에 있게 하려고 합니다. A의 위치에는 어떤 숫자가 들어가겠습니까?(숫자만 입력하세요.) 문제풀이) 더보기 왼쪽 상단 1 위치부터 시계 방향으로 a,b,c,A,d,e,f 로 그림을 그려 보면 1 + a + b = 14 --(1) b + c + A = 14 --(2) A + d + e = 14 ..

[정보올림피아드대비]5. 기하문제-평면

1. 도형의 둘레 - 사각형의 둘레 구하기 사각형 둘레는 a + a + b + b 이므로 2 * (a+b) - 삼각형의 둘레 구하기 삼각형의 둘레는 a + b + c ※ 여기서 피타고라스 정리에 의해 직각 삼각형의 빗변 c의 제곱은 다른 두변 a,b의 제곱의 합과 같다 증명) 이렇게 연장선을 그려서 하나의 정사각형을 만들어 보자. CDFH 의 넓이 = 삼각형 ABC의 넓이 * 4 + 사각형 AEGB의 넓이 CDFH 의 넓이 = (a+b)^2 = a^2 + 2ab + b^2 사각형 AEGB의 넓이 = c * c 삼각형 ABC의 넓이 = a * b / 2 이므로 a^2 + 2ab + b^2 = c * c + 4 * a * b / 2 따라서 a^2 + b^2 = c^2 - 원의 둘레 원의 둘레는 원의 반지름과..

[정보올림피아드 대비]4. 기하 문제-선분

1. 다음의 도형에서 몇개의 선분이 있는지 세어 보세요.(숫자만 입력하세요.) 문제풀이 더보기 각 점의 위치에 1,2,3,4,5 의 번호를 붙여 줍니다. 1번에서 그릴수 있는 선분은 (1,2)(1,3)(1,4)(1,5) 4개입니다. 2번에서 그릴수 있는 선분은 (2,3)(2,4)(2,5) 3개 입니다. 3번에서 그릴수 있는 선분은(3,4)(3,5) 2개입니다. 4번에서 그릴 수 있는 선분은(4,5) 1개입니다. 따라서 1+2+3+4 = 10개입니다. 2. 아래 그림에서 각이 모두 몇개 있습니까? 문제풀이 더보기 각 점의 위치에 1,2,3,4,5 의 번호를 이용하면 1번에서 그릴수 있는 각은 (1,2)(1,3)(1,4)(1,5) 4개입니다. 2번에서 그릴수 있는 각은 (2,3)(2,4)(2,5) 3개 입니..