KOI :: 2015 시도예선 중고등부 수학문제 풀이

2015 시도예선 중고등부 수학문제

###3번 문제

출제의도

: 문제의 경우의 수를 잘 파악할 수 있는가

문제 난이도

:  ★★☆☆☆

문제 풀이

아래와 같이 a+b+c+d 를 각 박스에 공을 몇개 담는지로 문제를 변형시킨다.

문제의 조건을 보면 a, b, c, d 는 1이상이다.

따라서 식을 a + b + c + d = 6 이렇게 변형한다.

그러면 6개의 공과 3개의 칸막이를 조합하는 문제가 된다.

확률과 통계 공식에 의해 

(6+3)C3

= (9*8*7) / (3*2*1)

= 84 

###4번 문제

출제의도

: 귀납적인 방법으로 문제해결

문제 난이도

:  ★★☆☆☆

문제 풀이

이 문제는 수학적 귀납법으로 증명을 할 수 있다.

만약 5원짜리와 8원짜리로 n원을 만들 수 있다면 n+5 원짜리를 만들 수 있다.

n+1 을 만들 수 있다면 n+6 원짜리를 만들 수 있다.

n+2 을 만들 수 있다면 n+7 원짜리를 만들 수 있다.

n+3 을 만들 수 있다면 n+8 원짜리를 만들 수 있다.

n+4 을 만들 수 있다면 n+9 원짜리를 만들 수 있다.

.....

이와같은 방법을 반복하면 n에서 부터 연속으로 5개를 만들 수 있다면 된다.

보기에서부터 보면

24 = 8*3

25 = 5*5

26 = 5*2+8*2

27 = 불가능

28[n]     = 5*4 + 8   

29[n+1] = 8*3 + 5    

30[n+2] = 5*6         

31[n+3] = 5*3 + 8*2

32[n+4] = 8*4        

따라서 n=28 이다.

###8번 문제

출제의도

: 여러가지 경우의 수 고려

문제 난이도

:  ★☆☆☆☆

문제 풀이

제곱 수 : 1, 4, 9, 16, 25, 36, 49, 64, 81, ...

89 = 81 + 4 + 4

이렇게 해서 3개라고 답을 체크 할 수 있지만 더 줄일 수 있는지 확인해 봐야한다.

실제 답은

89 = 64 + 25로

2가 된다.

###13번 문제

출제의도

: 더 작은 문제로 큰문제 해결하기

문제 난이도

:  ★★★☆☆

문제 풀이

문제를 간단하게 생각해 봐야한다.

4*4 크기의 경우 모든 칸을 비울 수 있는지에 대한 작은 문제로 변형한다.

위와 같이 블록을 저런 모양으로 변형 시키고

맞춰보면 된다.

 위의 오른쪽 아래서 4가지 경우가 돠 된다.

위와 같은 방법으로 왼쪽 위, 왼쪽 아래, 오른쪽 위도 된다.

결국 맵이 커져도 성립이 된다.

따라서 못 비우는 칸은 없다

###13번 문제

출제의도

: 최소 해 찾기

문제 난이도

:  ★★☆☆☆

문제 풀이

전체 사람들의 구술 평균 : 15

가장 왼쪽에서 부터 15개를 채워주면 된다.

10 13 26 11 15 12 18 13 25 7

15  8 26 11 15 12 18 13 25 7

15 15 19 11 15 12 18 13 25 7

15 15 15 15 15 12 18 13 25 7

15 15 15 15 15 15 15 13 25 7

15 15 15 15 15 15 15 15 23 7

15 15 15 15 15 15 15 15 15 15

총 7번

###15번 문제

출제의도

: 주어진 조건에서의 최소 공간복잡도 구하기

문제 난이도

:  ★★★★★

문제 풀이

독이 와인을 먹었을 때의 결과는 죽는다(1) 산다(0) 이다.

각 와인에다가 번호를 메긴다.

와인의 번호를 이진수로 표현한다.

이진수 표현으로 바꿨을 때의 번호에서 1이 들어가는 번째의 쥐한테 해당 와인을 먹인다.

예를 들어 51의 경우 110011(2) 이므로 5번, 6번 9번, 10번 쥐한테 먹인다.

이런식으로 먹이면 최대 10마리의 쥐가 죽게된다.

왕은 착하니깐 쥐의 죽음이 최소가 되길 원하니깐 더 줄일 수 있는지 확인해야한다.

쥐가 10마리가 죽게되는 경우는 1가지 경우밖에 없다.

이 경우는 와인의 번호를 0번부터 메기게 되면

기존 : 1~1024

새로 : 0~1023

맨 마지막번호가 1111111110(2) 이기 때문에 9마리가 된다.

쥐가 9마리 죽게 되는 경우는

0111111111(2)

1011111111(2)

1101111111(2)

1110111111(2)

...

1111111101(2)

1111111110(2)

이렇게 10가지 이다.

이 수가 나올경우 뒤로 수를 1씩 더해서 이를 방지하면 된다.

그러면 와인이 총 1000병이였으니깐

와인의 번호가 0~999 번에서

번호가 1씩 밀려 총 0~1009 까지 경우가 된다.

하지만 쥐는 총 10마리이기 때문에 1024까지의 경우까지 표현할 수 있다.

따라서 최소 8마리가 답이다.