많이 알려진 문제이긴 하지만.... 재미 있는 문제들

1) 파티에 25명의 사람이 모였다. 어느 사람이 여기 모인 사람 중 생일이 같은 사람이 적어도 한쌍은 있다에 내기를 한다. 어느 쪽에 거는 것이 유리할까?

2) 전체 인구의 1퍼센트가 걸리는 질병에 대해서 누군가 질병을 가지고 있음을 판단해내는 검사의 신뢰성은 80%이다. 그런데 질병이 없는데도 질병이 있는 것으로 검사결과가 잘못 나오는 거짓 양성의 확률은 10%이다. 양성판정을 받은 사람이 의사에게 자신이 진짜 병에 걸렸을 확률은 어느 정도 일까?

1. 90% 정도 2. 70%정도 3. 40%정도 4. 10% 정도

3) 250톤의 물을 아무런 기구의 도움 없이 허공에 떠 있게 하려면?


















































































답)
1. 전체 25명의 사람 중 2인 쌍을 만들 수 있는 전체 경우 수는 25C2 = 253

한 쌍의 사람이 생일이 같을 확률 = 1/365
( 어떤 사람의 생일이 1월1일이라면 다른 사람이 동일하게 1월 1일일 확률은 1/365 이므로 )

생일이 같은 쌍이 하나도 없을 확률은 ( 1 - 1/365 ) ^ (253) = (364/365)^(253) = 0.4995
(50%가 되지 않는다. 그러므로 생일이 같은 쌍이 있다는 것에 거는 것이 유리한다.)


2. 천명의 사람이 검사를 받았다면(그중 병에 걸린 사람은 1%,10명 이라고 하자) 그 중 진짜 병이
걸린 10명의 사람 중 양성판정을 받는 사람은 8명 , 병이 없는 사람 990명 중 10%는 양성판정을
받으므로 99명이 양성판정를 받는다. 전체 양성 판정 받는 사람은 99+8 = 107명
이중 실제 병을 가진 사람은 8명이므로 양성판정을 받고 실제 병이 걸렸을 확률은 8/107, 8%가
되지 않는다. (믿음의 엔진 - 루이스 월퍼트 , 에코의 서재 )에서


3. 구름을 만들면 된다. (평행우주, 미치오 카쿠,김영사)에서

똑 같은 수를 더하거내 빼는데 계산 순서에 따라 결과가 달랐다... 보통은 계산 중 실수가 있다고 생각 할 것이다. 그러나 아래 계산을 유심히 보라


1)
1-1/2+1/3-1/4+1/5-1/6+1/7-1/8+1/9-1/10+1/11-1/12+1/13-1/14 ..... = T
= (1-1/2) -1/4 + (1/3-1/6) -1/8 +(1/5-1/10) - 1/12 + (1/7-1/14) ....
= 1/2-1/4+1/6-1/8+1/10-1/12+1/14......
= 1/2(1-1/2+1/3-1/4+1/5-1/6+1/7-1/8+1/9-1/10+1/11-1/12+1/13-1/14 ....)

∴ T = 1/2(T) -> T = 0

2)
1-1/2+1/3-1/4+1/5-1/6+1/7-1/8+1/9-1/10+1/11-1/12+1/13-1/14 .....
= (1-1/2)+(1/3-1/4)+(1/5-1/6)+(1/7-1/8)+(1/9-1/10)+(1/11-1/12)+(1/13-1/14) .....

각 괄호의 항은 모두 0보다 크므로 그합이 0일 수 없다. 실지로 위 급수는 log2로 수렴한다.

ln(1+x)=x-1/2 * x^2 + 1/3 * x^3 - 1/4 * x^4 + 1/5 * x^5 - .... Maclaurin 급수전개
x = 1 이면
log2 = 1-1/2+1/3-1/4+1/5-1/6+1/7-1/8+1/9-1/10+1/11-1/12+1/13-1/14 .....

3)
T ≠ 0 (T=log2) 임에도 T = 1/2(T) 인 것은 모순이다.

4)
피타고라스 학파는 무리수의 비밀을 누설하는 이를 살해함므로 비밀을 유지했다.
이제 당신은 산술의 비밀을 알게 되었다. 당신의 생명을 소중히 여기라





답이랄까... 는 아래에





























































































































































계산은 틀리지 않았습니다.
실지로 급수가 더하는 순서를 바꾸면 결과가 다르게 나오는 조건부 수렴 급수입니다.
(고등학교 수학에서 공비가 -1< R <1 일때 수렴한다는 주건부수렴과는 다른 개념입니다.)

저도 잘 모르겠습니다. 이런 성질을 가진 급수가 있다는 것은 리만에 의해 보고되었다고 합니다.
"리만 가설"이라는 책에서 위 급수를 소개하고 있습니다.

그냥 개인적생각으로 무한번째 항과 무한번째 항으로부터 무한번 떨어져 있는 항을 합한다는 일종의 초작업 후의 초작업이 이런 이상한 결과로 나타난게 아닐까하는 느낌입니다.

동일한 오류를 포함 하는 좀 더 간단한 예는...

1 - 2 + 3 -4 +5 ....
= (1-2) + (3-4) + (5-6)+.... <0
또
= 1 + (3-2) + (5-4) + .... > 0


무한은... 참으로 ... 알송달쏭한 것....

앞에서 보면 동그라미 , 옆에서 봐도 동그라미
위에서 보면 네모인 도형...

어떻게 생긴 도형일까요?










































이렇게 생긴도형 입니다.



원기둥 두개가 직교할 때 중첩되는 부분으로 이루어진 도형입니다.

아마 누구나 어릴 적에 몇 번은 해본 게임일거다.

방법은 일단 상대는 모르는 4자리 숫자를 하나 정한다.(상대도 마찬가지)
게임참가자를 A,B라 할때
A는 B가 정한 숫자를 추측한다. B는 A가 추측한 숫자와 자신이 정한 숫자를 비교하여
결과를 A에게 알려준다. (A가 추측한 숫자가 B정한 숫자에 자리수가지 일치할 경우는
스트라익으로, 포함은 되지만 자리수가 맞지 않으면 볼로 표현한다. 예를 들어
1S 1B는 총 2개의 숫자가 B가 처음 정한 숫자열에 있는데 1개는 자리수까지 맞고, 1개는 자리수가 맞지 않은 상태임을 나타낸다.)
반대로 B가 A가 정한 숫자열를 추측하고 A는 결과를 알려준다.
위와 같은 질문을 번갈하 하면서 먼저 상대방의 숫자열을 추측하는 게임이다.

문제는 최선의 전략으로 4자리 숫자를 추측할 경우 평균 몇회만에 맞출 수 있느냐하는 것이다.









































































답: 5.22회

1. 위 결과는 프로그램으로 문제풀이를 1000회 실시한 평균 값이다.
(저는 이 알고리즘이 최선이라고 생각하지만 제생각이 100%맞다는 보장은 없습니다.)

프로그램화된 추측 알고리즘은 아래와 같다.
일단 해 집합을 정의하는데 답이 될 수 있는 문자열을 모두 포함하는 집합이다.

해집합 R(i) = { i번째 질문까지 만족하는 문자열} 으로 정의한다.

예를 들어 설명하자면

R(0) = {0123,0124,0125 ... 9876} (원소의 갯수는 총 5040개)

첫번째 시도에서 0123를 추측했고 결과가 0S 0B 라면
R(1) = { 4567,4568,....,9876} (원소의 갯수는 총 360가지, 아래 참조)

다음 과정은 해집합에 있는 한 수를 선택하여 그 결과를 질의 한다.
최종적으로 해집합의 원소의 수가 1개가 될 때까지 과정을 반복 한다.

실제 프로그램의 핵심 루프는 아래와 같다.

for i = 0 to 9
for j = 0 to 9
for k = 0 to 9
for l = 0 to 9
if i,j,k,l에 공통된 수자가 있으면 계속 루프를 돌도록
pstr = i & j & k & l ' i=0, j =1, k =2 , l = 3 일때 숫자열 0123 생성
if 이전 질의 결과를 모두 만족하는지 확인
만족한다면 숫자열을 상대방에게 알리고 결과를 요청
만족하지 않는다면 계속루프
next i
next k
next j
next i

예를 들어 첫 추측을 0123 으로 했는데 결과가 1b라면
끝자리부터 하나증가하면서 1b를 만족시키는 숫자열을 찾는다.

01234 는 0123 과 3s로 1b가 아니다.
01235는 0123 과 3s로 1b가 아니다.
.....
0987 은 0123 과 1s로 1b가 아니다.
1234 는 0123 과 3b로 1b가 아니다.
....
...
1567은 0123 과 1b이다.

그러므로 다음 추측은 1567로 한다. (1567은 해집합 R(1)의 한 원소이다)

결과가 만약 0s 2b로 나왔다면
1567에서 또 숫자를 증가시켜 가면 0123과 1b 이고 1567과는 2b인 숫자를 찾는다.
2658이 바로 그런 숫자열이다. (2658은 해집합 R(2) 한 원소이다)

2. 이 전략은 최선일까?

각 단계의 해집합은 이전 질의를 만족하는 원소로만 구성되어 있고 다음 추정은 그 해집합에 있는 한 원소로 하는 것은 직관적으로 타당해 보인다. 그러나 사실은 아니다. 반례가 있다.

A는 B의 수자를 마지막 자리를 제외하고 다 알고 있다.
추축한 숫자열은 123 * 이거 *에 대체될 수 이 수 있는 숫자는 4,5,6,7 4개라고 하자

해집합은 {1234,1235,1236,1237 } 이다. 다음 추측은 1234로 할 것이다.

1) 답이 1234 일 경우
1회에 성공
2) 답이 1235 일 경우
1234 오답이 되면 1235로 2회에 성공
3) 답이 1236일 경우 - 3회에 성공
4) 답이 1237일 경우 - 4회에 성공

성공까지의 시도회수 평균은 =1/4 *1 + 3/4*1/3*2 + 3/4*2/3*1/2*3 + 3/4*2/3*1/2*1*4 =
(1+2+3+4)/4 = 10/4 =2.5회

이번에는 다른 방법으로 풀어보자

9054 를 질의하면 1S 이면 답이 1234 이고 1B이면 1235 이고 아무것도 없으면 답은 1236이나
1237이 된다.
정리하면

1) 답이 1234 나 1235 이면 2회만에 정답
2) 답이 1236이면 첫번째 질의에서 0S0B 이므로 1234 ,1235가 아니라는 것을 알 수 있으므로
1236을 선택 - 2회 성공
3) 답이 1237이면 3회 성공

성공까지의 시도회수 평균은 =0*1/2 + (1/2 *2 + 1/2*1/2 * 2 )+ 1/2 * 1/2 * 3 = 2.25 회

문제는 다음 추측의 문자열을 해집합에서만 선택한다는 것이 문제인 것같다. (해집합외의 문자열로 질의하는 것이 더 좋을 수도 있다는 것이 위 예로 알 수 있다.

그래서 프로그램을 일부수정 했는데 , 매 질의때 마다 01234 ~ 9876 까지 모든 문자열에 대해
해집합의 문자열과 비교하여 가능한 모든 결과의 확률을 계산하다. 이로부터 전달되는 정보엔트로피를 계산할 수 있다. 이 경우 정보엔트로피는 질의로 전달되는 정보량을 의미하게 되므로 이 값이 큰 것이 좋은 질의이다.(정보엔트로피는 가능한 모든 경우에 대해 -P * log P , P는 각 경우의 확률이다. 정확한 수식은 http://ko.wikipedia.org/wiki/%EC%A0%95%EB%B3%B4_%EC%97%94%ED%8A%B8%EB%A1%9C%ED%94%BC 을 참조)

앞에 예에 대해 정보 엔트로피를 구해보면
해집합은 {1234,1235,1236,1237}

1234로 질의 할 경우
4S 일 경우 1가지 경우 1/4
3S 일 경우 3가지 경우 3/4

정보엔트로피 = - (1/4) * log2 (1/4) - (3/4) * log2 (3/4) = 0.811

9045로 질의 할 경우
1S 일 경우 1가지(1234) 1/4
1B 일 경우 1가지(1235) 1/4
0일 경우 2가지(1236,1237)

정보엔트로피 = - (1/4) * log2 (1/4) - (1/4) * log2 (1/4) - (1/2) * log2 (1/2) = 1.5

예상한대로 9045가 더 좋은 질의임을 엔트로피 계산으로 부터 알 수 있을 것 같다.


3. 추가
첫번째 프로그램은 답을 맞추는데 평균 5.55 회
두번째 프로그램은 답을 맞추는데 평균 5.52 회
그다지 큰 차이는 없다.

다음은 첫번째 프로그램으로 30000만회 문제풀이 결과의 통계값을 기록해본다.
(2번째 프로그램은 연산시간이 너무 많이 걸려 1000회 실시하는데 대략 하루가 걸렸다)

정답을 맞추기 위한 시행 회수
평균 : 5.55
표준편차 : 1.08

1회에 맞추는 확률 : 0.04 %
2회에 맞추는 확률 : 0.25 %
3회에 맞추는 확률 : 2.66 %
4회에 맞추는 확률 : 13 %
5회에 맞추는 확률 : 31 %
6회에 맞추는 확률 : 36 %
7회에 맞추는 확률 : 15 %
8회에 맞추는 확률 : 2.8 %
9회에 맞추는 확률 : 0.12 %

가능한 총 문자열의 갯수 : 5040
위 경우의 정보엔트로피 : 12.3

첫번째 시도에서 얻는 정보량
최대엔트로피(각 경우의 동일한 확률일 경우) : 3.91
실제엔트로피(아래 리스트의 확률을 이용) : 2.77

0 s 0 b 360 가지 7.14 %
0 s 1 b 1440 가지 28.57 %
0 s 2 b 1260 가지 25.00 %
0 s 3 b 264 가지 5.24 %
0 s 4 b 9 가지 0.18 %
1 s 0 b 480 가지 9.52 %
1 s 1 b 720 가지 14.29 %
1 s 2 b 216 가지 4.29 %
1 s 3 b 8 가지 0.16 %
2 s 0 b 180 가지 3.57 %
2 s 1 b 72 가지 1.43 %
2 s 2 b 6 가지 0.12 %
3 s 0 b 24 가지 0.48 %
3 s 1 b 불가능
4 s 0 b 1 가지 0.02%

문제가 가지는 엔트로피는 12.3
첫 시도에서 획득되는 정보량은 2.77

갑순이는 지하철을 타고 가다 재미있는 기사가 난 신문을 보게 되었다. 나중에 자세히 보기 위해 신문을 접어서 손지갑에 넣어 두기로 했다.
그래서 신문을 반으로 접고 또 반으로 접고 또 반으로 접었다. ...(15번)
(신문의 두께는 0.1mm 이다.)

그러나 갑순이는 결국 지갑에 신문을 넣을 수 없었다

왜 ???


답은 밑에



















































답 0.1mm신문이 15회 접어지면 두께가 3.2m가 된다. ( 0.1 X 2^15 = 0.1 X 32768 )
3.2m나 되는 물건을 손지갑에 넣을 수는 없을 것이다.