민서 개발일기

5. 돌 무더기 게임 (9점)

문제

   A, B 두 사람이 다음과 같은 게임을 한다.

   두 사람은 테이블 하나에 서로 마주 보고 앉아있다.

   테이블 위에는 세 개의 돌 무더기가 있고, 각 무더기에는 각각 1개, 2개, 3개의 돌이 있다. A부터 시작해서 돌아가면서 게임을 진행하는데, 세 돌 무더기 중 하나를 고르고, 가져가고 싶은 개수만큼의 돌을 가져간다.

   단, 돌을 최소한 한 개는 가져가야 한다. 돌을 가져간 다음, 테이블에 돌이 남아있지 않다면, 이 사람이 이긴다.

   A, B 모두 항상 자신이 이기기 위해서 최선을 다한다. 이 때 게임의 결과는 어떻게 될까?

1. A가 항상 승리한다.

2. B가 항상 승리한다.

3. A가 승리할 수도, B가 승리할 수도 있다.

정답

2번

풀이

이 문제는 NIM game에서 유래된 게임으로 A, B와 같이 2명이서 하는 경우에는 필승법이 존재한다.

바로 플레이어의 차례일 때 불균형상태인 돌들을 균형 상태로 맞춰주면 된다.

이때 균형상태는 세 줄의 돌들을 2의 거듭제곱의 합으로 표현했을 때 2의 거듭제곱이 쌍으로 존재하는 것을 의미한다.

예를 들어 지금 문제의 경우에는 1,2,3 개가 있는데 1=1, 2=2, 3=2+1 이므로 1이 2개, 2가 2개가 존재한다.

이에 대한 증명은 구글에 NIM game이라고 검색하면 나온다.

A, B 모두 항상 자신이 이기기 위해서 최선의 수를 선택한다고 하였으므로 지금 돌 무더기는 균형 상태이기 때문에

A는 어쩔 수 없이 불균형상태로 만드는 수밖에 없고 결국 균형 상태로 만드는 B가 항상 승리하게 된다.

나는 NIM game 을 이 링크를 통해 공부하였다. 새로운 알고리즘을 알게 된 것 같아서 기분이 좋았다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=nyseul&logNo=220009539606

4. 발표 순서 (8점)

문제

   조별 발표를 위해 A부터 F까지 6개 조에 대한 발표 순서를 정하려고 한다.

   모든 가능한 발표 순서를 알파벳 순서로 나열해보면 ABCDEF부터 FEDCBA까지 720가지가 있는데, 그중 CBADEF는 몇 번째인가?

1. 241

2. 253

3. 265

4. 385

5. 409

정답

3번

풀이

경우의 수를 구하는 문제이다.

자릿수 마다 나올 수 있는 경우의 수를 구해보면

맨 왼쪽 자릿수는 5 * 4 * 3 * 2 * 1 = 120번째마다 알파벳이 바뀐다.

CBADEF이므로 맨 왼쪽이 C가 나오려면 최소 241번째가 돼야 한다.

2번째 자릿수는 4 * 3 * 2 * 1 = 24번째마다 알파벳이 바뀐다.

2번째 자릿수가 B가 나오려면 241 + 24 = 265번째가 된다.

나머지 자릿수는 알파벳 변동이 없는 초기값이므로 정답은 265번째 3번이다. 

3. 동전과 확률 (8점)

문제

   10개의 동전이 있는데, 앞면은 모두 같은 모양이지만 뒷면은 x개의 동전에는 A, 10 − x개의 동전에는 B 라고 표시가 되어 있다. 이 10개의 동전들이 앞면이 위가 되게 놓여 있다. 이 중 공평하게 두 개를 한번에 골라서 뒤집었을 때, 둘 모두 뒷면에 A가 나올 확률이 0.4 이하가 되는 가장 큰 x의 값은?

1. 8

2. 7

3. 6

4. 5

5. 4

정답

3번

풀이

두 뒷면에 A가 나올 확률이 40% 이하중 가장 큰 값이여야 하므로 가장 높은 확률부터 차례대로 확률을 모두 구해보면 된다.

1. 64% ( 40% 이상 )

2. 49% ( 40% 이상 )

3. 36% ( 40% 이하 ) | 실제 문제를 풀때는 여기서 정답을 적는다.

4. 25% ( 40% 이하 )

5. 16% ( 40% 이하 )

고로 답은 3번이다.

2. 구슬 경로의 수 (8점)

문제

   아래 그림과 같은 통로에 구슬을 떨어뜨리면 통로를 빠져나올 때까지 지나는 경로는 구슬을 떨어뜨릴 때마다 다를 수 있다. 통로 안에서 구슬이 아래에서 위로는 움직일 수 없다고 가정할 때, 구슬이 지날 수 있는 서로 다른 경로는 몇 가지 존재하는가?

1. 12

2. 24

3. 35

4. 64

5. 128

정답

3번

풀이

이건 단순한 경우의 수 계산 문제이기 때문에 구간별로 총몇번 올 수 있는지 더해주면 된다.

그렇기에 총 경우의 수는 35가지 답은 3번이다.

1. 상금 배분 (8점)

문제

   한국 시리즈 야구 결승은 7전 4선승제로 4번을 먼저 이기는 팀이 우승한다.

   A팀과 B팀이 맞붙었는데, 처음 2경기를 A팀이 이긴 상태에서 사회적 거리두기로 더 이상 경기를 진행하지 않기로 했다.

   A팀과 B팀의 실력은 동일하여 이길 확률은 같고, 승패를 결정하는 다른 요인이 없다고 하자.

   한국 시리즈 우승 상금은 16억원이고, 이를 A팀이 2승으로 앞선 상태에서 A팀과 B팀의 우승확률을 가지고 배분하려고 한다.

   A팀에게 얼마를 배정하는 것이 공정할까?

1. 8억원

2. 10억원

3. 13억원

4. 14억원

5. 15억원

정답

3번

풀이

A팀은 이미 2번을 이겼기 때문에 2번만 더 이겨주면 되는 상황

A팀이 2번 연속 우승할 때와 1번지고 2번 우승할 경우, 2번지고 2번 우승할 경우, 3번지고 2번 우승할 경우의 확률을 구해 더해준다. 

이긴 팀 | A가 이길 확률

AA | 1/4
BAA | 1/8
ABA | 1/8
BBAA | 1/16
BABA | 1/16
ABBA | 1/16
BBBAA | 1/32
BBABA | 1/32
BABBA | 1/32
ABBBA | 1/32

A가 이길 확률 26/32 즉, 13/16이므로 3번이다.

이때 주의해야할 점은 BBAAB 같은 경우는 이미 A가 2번 우승했기에 BBAA 상황과 겹치게 된다. 고로 A가 한번 이상 지고 2번 이겨 우승할 경우의 수를 구할 때 A가 우승할 경우의 2번 중 한번은 무조건 마지막 판에 우승해야한다.