정치/경제/사회 게시판
모든 문제는 고등학교 과정에 나와있던 수학 지식들을 바탕으로 해결됩니다.
첫번째 문제
A를 평면 위의 2n개의 점의 집합이라 한다. 이들 점의 어느 3개도 동일직선 위에 있지 않다. 이들 점 중 n개를 빨간색으로 칠하고, 나머지 n개를 푸른 색으로 칠한다.
이때, 아래 사실을 증명하라
n개의 폐성분(양 끝점을 포함하는 선분)을 만들면 어느 2개도 공유점을 갖지 않고, 또 각 선분의 양끝점은 서로 다른 색을 갖도록 할 수 있다.
두번째 문제
다음과 같은 규칙으로 게임을 한다. 정이십면체의 주사위로 최고 다섯번까지 던져서, (마지막에 나온 눈의 수)와 1000 을 곱한 값을 금액(원)으로 주기로 한다.
n번(n의 범위는 1이상 4이하)을 던져서 나온 눈을 보고 나서 n+1 번째에 던질 것인가 아닌 가를 정할 수 있다.
n번쨰 어떤 눈이 나왔을 떄가 n+1번쨰에 던지는 것이 가장 유리한가? 또 이 게임에 건 돈이 16000원이라면, 이 게임에 도전하는 것이 이득인가 손해인가?
세번쨰 문제
공간에 평면 a가 있다. 공간의 점P를 지나 평면 a에 수직인 직선이 a와 만나는 점을 P의 a위로의 정사영이라 하고, 공간도형 V의 각 점의 a 위로의 정사영 전체가 만드는 a위의 도형을 V의 a위로의 정사영이라 한다.
한 번의 길이가 1인 정사면체 V를 평면 a 위로의 정사영의 넓이를 S라 하면, V가 여러 위치로 변할 때 S 의 최대값, 최소값을 구하라.

정확한 증명은 지금 생각이 안나고 대충 생각해 보면,
(1) 일단 점이 2개, 빨간색 하나, 파란색 하나 있으면 당연히 되고요.
(2) 점이 2*K개가 있을때, 그런식으로(어느 선분도 서로 만나지 않게) 짝을 지을수 있다고 가정하면 (Induction Hypothesis)
점이 2*(K+1)개가 있을때도, 마찬가지로 짝을 지울수 있다는걸 증명하면 되는데요.
대충 맨 가장자리에 있는 두점 (빨간색 하나, 파란색 하나)를 골라서 제외하고, 나머지 2*K개에 대해서 짝을 지은 다음에, 아까 제외한 두 점을 다시 이어줘서, 새로 이은 선분이랑 만나는 선분들끼리 partner change를 하면 될것 같은데.. 정확하게 할려니까 생각을 좀 더 해야 되겠네요.
본고사 문제라니 좀 반갑네요. 1번 문제의 속사정은 복잡한데요, 이 문제의 핵심은
"햄-샌드위치 자르기"라는 아주 유명한 정리입니다. 간략히 말씀드리면 햄이 있는 샌드위치가 있을 때
칼을 이용해서 햄과 샌드위치가 정확하게 1/2이 되도록 자르는 cut이 존재한다는 것입니다.
http://en.wikipedia.org/wiki/Ham_sandwich_cut
(이 문제는 계산기하학 문제이기도 한데요, arrangment의 Zone의 정리,
또는 second order-Vornio graph의 dual에서 특이점이 존재한다는 식의 증명으로도 설명이 됩니다.... )
문제는 고등학생들이 푸는 것이라 이런 식으로 설명할 수는 없을 것 같고요,
gatebeam 말씀대로 induction을 쓰면 됩니다.
1) n=2 일때 가능합니다. 당근이죠... 점이 2개 밖에 없으니
2) 2*k 이하에서 가능하다고 가정합니다.
3) 2(k+1)일때가 문제인데요
가장 밑에 있는 점을 하나 잡습니다. 그 점을 색을 빨간색(R)이라고 합시다.
그 점에 작대기를 설치하고 그 끝에 못을 박아서 작대기가 반시계 방향으로 휙 - 돌아가게 합니다.
첫번째 걸리는 놈이 나옵니다. 그 점을 x_j 라고 합니다. 만일 그 놈이 파란색이면 증명끝...
(왜냐하면 그 두 점을 빼고 난 점들고 구성한 뒤에 그 두 좀 x_i와 x_j를 연결하면 되죠. 아무런 문제없이.
만일 x_j가 다시 빨간색이라면 그 작대기를 회전시킵니다. 그러면 그 작대기 왼쪽에 빨간색과 파란색이
나오게 됩니다. 그것의 갯수를 각각 R( ), B( )라고 합시다. 그런데 어떤 3점도 일직선 상에 없으므로
그 작대기(line L)을 한 점씩 지나도록 탁 탁 옮길 수 있습니다. 한 칸씩 옮길때 마다 R( )이 +1 증가하거나
B( )가 +1 증가 합니다. 이렇게 옮기면 어떤 점에서 반드시 R()과 B()가 같아지는 점이 나옵니다.
L의 왼쪽에 있는 점들에서 빨간점을 +1, 파란점을 -1로 계산합니사. x_end에 도달하면 그 점수는 0이 되어야 합니다.
왜냐하면 점의 갯수가 같기 때문에 n(+1-1)=0 이기 때문에요. 그런데 시작할 때는 +2입니다. x_end에서 거꾸로
돌려도 +2가 됩니다. 따라서 L이 돌때 반드시 그 합이 0인 점이 나타납니다. 그 점을 중심으로 양분하면
양쪽이 2(k)보다 작은 점들로 구성이 됩니다. 그래서 그 나눠어진 점들에 대하여 돌리면 된다는 이야기,,,
(술 깨는데는 그림 그리는 것이 최고라 밑에 한번 그려보았습니다. )
(i) 주사위를 한번만 던질 경우 기대값은 6.5 입니다.
(ii) 주사위를 두번 던질수 있는 경우, 처음 던진 값이 기대값(6.5) 보다 크면 그냥 스톱하고, 아니면 던집니다.
이때 최종 기대값은 (한번만 던질 경우 값)*(확률) + (두번던지게 될경우 값)*(확률)
1/12*(7+8+9+10+11+12) + 6/12*6.5 = 8 입니다.
(iii) 세번던질수 있을 경우: 마찬가지로 처음 던져서 위의 기대값 (8) 보다 크거나 같으면 스톱, 아니면 다시 던져서 (ii)를 적용합니다.
최종 기대값
1/12*(8+9+10+11+12) + 7/12*8 = 8.833
(iv) 네번 던질경우: 마찬가지로 (8.83)보다 크면 스톱, 아니면 고 (iii).
1/12*(9+10+11+12) + 8/12*8.833 = 9.389
(v) 다섯번 던질경우: 마찬가지로 (9.389)보다 크면 스톱 아니면 고 (iv)
1/12*(10+11+12) + 9/12*9.389 = 9.792
추가: 지금보니 정 12면체가 아니라 정 20면체군요. 뭐 비슷하게 풀면 됩니다.
정치/사회게시판 최신댓글