[알고리즘 수학] 마지막 공의 색깔 맞추기

바구니 안에 빨간공 120개와 파란공 30개가 들어 있다.

이렇게 들어 있는 바구니에서 다음과 같은 절차에 의해 공을 꺼낸다.

1. 두개의 공을 꺼낸다.

2. 만약 두개의 공의 색깔이 같으면 빨간공 한개, 서로 다르면 파란공 한개를 집어 넣는다.

3. 1과 2를 계속 반복한다.

바구니의 마지막 공의 색깔은 어떤 색이 될까?

 

문제풀이)

바구니 안의 공이 빨간공 120개 파란공 30개 에서 시작을 한다. 만약 두개 모두 빨간공을 꺼냈다면 빨간공이 119개,파란공 30개가 된다. 두개 모두 파란공이었다면 빨간공이 121개,파란공은 28개가 된다. 두개 모두 색깔이 다르다고 하면 빨간공 119개 파란공 30개가 된다. 

이것을 확인 했을 때 빨간공은 1개가 줄거나 1개가 늘어난다. 파란공은 0개가 줄거나 2개가 줄어든다.

따라서 1개가 남을 수 있는 경우는 빨간색만 남을 수 밖에 없다.

 

만약에 위와 똑같은 알고리즘에서 파란색 공이 홀수개였다면 파란색 공이 짝수개씩 줄어 들기 때문에 파란색 공은 0이 될 수 없기 때문에 마지막 남는 공은 반드시 파란색 공이 될 수 밖에 없다.