[대학교이상] 이거 풀이좀 알려줄사람?

[익명(basis9029)]

에타 올라온 문젠데 해설을 봐도 이해가 안댐

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(basis9029)]

@수갤러1(123.215) 25가 암만생각해도 정답인듯

[익명(175.236)]

최대한 빨리 끝내는게 답이 아니었고 한쪽이 항상 0점이 되는게 최적임 그래서 1차원 랜덤워크인듯

[익명(175.236)]

7.54는 성격이 착한거고 ∞는 악마새끼들인듯

[둥실라이드(wood0186)]

내가 이글을 찾기위해 수잘갤을 어슬렁 거리고 있었다면 믿어줄래?

[익명(147.47)]

승리 확률 따져보니 각 팀은 자신이 승리했을 때, 만약 상대가 자기보다 점수가 높으면 상대 점수를 1 깎고, 상대가 자기보다 점수가 이하이면 자기 점수를 1 높이는 게 승리확률을 최대화하는 전략으로 계산됨.

[익명(147.47)]

증명은 간단히 쓰면 팀이 A팀, B팀이라 할 때 A가 5-a점 , B가 5-b점 받은 상황에서 A, B가 최선을 다해 게임을 할 때 A가 승리할 확률을 p(a, b)라 두면 다음과 같은 점화식들이 성립하는 걸 사용 시 증명됨; 1) p(a, b)+p(b, a)=1 2) 2<=b<=5에서 p(1, b)=0.5+0.5*min(p(1, b-1), p(2, b))

[익명(147.47)]

3) 2<=a<=4에서 p(a, 5)=0.5*p(a-1, 5)+0.5*min(p(a, 4), p(a+1, 5)) 4) (a, b)가 (1, b), (a, 1), (a, 5), (5, b)꼴 순서쌍이 아니면 p(a, b)=0.5*max(p(a-1, b), p(a, b+1))+0.5*min(p(a, b-1), p(a+1, b))

[익명(147.47)]

이거 열심히 풀어 p값들 계산해 보면 위에서 말한 전략이 최선의 전략임을 알 수 있었음. 뭔가 직관적으로는 당연해 보이는데, 직접 승리확률 점화식을 구해 푸는 것보다 더 쉬우면서도 충분히 엄밀한 증명은 아직 찾지 못함...

[익명(147.47)]

아무튼 저 사실을 쓰면, A팀이 5-a, B팀이 5-b점 얻은 상황에서 승패가 결정나기까지 더 해야 하는 게임 라운드 수의 기댓값을 X(a, b)라 할 때, 대칭성에 의해 X(a, b)=X(b, a)이고 1<=a<b일 때 X(a, b)=1+0.5*(X(a-1, b)+X(a+1, b)), X(a, a)=1+X(a-1, a)라는 점화식을 얻을 수 있음.

[익명(147.47)]

(단 이때 X(0, b)=X(a, 0)=0으로 정의함.) 이제 X 점화식 풀면 0<=k<=a에 대해 X(a-k, a)=a^2-k^2이 얻어지고, 따라서 X(a, a)=a^2이니 글쓴이 말대로 X(5, 5)=25가 정답일 것 같음. 일단 내 풀이는 이런데 혹시 애매한 점 있으면 지적 부탁해

[익명(basis9029)]

해설 고마워요

[익명(147.47)]

윗댓 쓴 사람인데 다시 풀어보니 답은 11이 맞는듯... 문제 지문 중 우승 확률을 낮추지 않는 한 최대한 경기 일찍 끝내려 한다는 문장을 까먹어서 잘못된 답인 25를 얻었음

[익명(147.47)]

일단 위에 쓴 (내 점수)-(상대 점수)가 0 이상이면 내 점수 높이고 아니면 상대 점수 깎는다는 건 '승리 확률을 최대화'하는 조건만이 주어졌다면 최선의 전략이 맞음. 하지만 문제는 '우승 확률을 낮추지 않는 한 게임을 최대한 빨리 끝낸다'는 조건도 내걸었기에 문제가 됨.

[익명(147.47)]

위 풀이에서 구한 p값들을 보면 아래와 같이 나옴. 아래 행렬에서 행번호가 a, 열번호가 b임. 0.5, 0.75, 5/6, 7/8, 0.9 0.25, 0.5, 2/3, 0.75, 0.8 1/6, 1/3, 0.5, 0.625, 0.7 0.125, 0.25, 0.375, 0.5, 0.6 0.1, 0.2, 0.3, 0.4, 0.5

[익명(147.47)]

p값들을 보면 a-b가 1이 아닌 모든 경우(즉 (A팀 점수)-(B팀 점수)가 -1이 아닌 모든 경우)에선 가능한 두 선택지의 확률이 다 달라서 어떤 선택지를 고를지가 딱 하나로 정해지는데, a-b=1이면 두 선택지는 각각 남은 점수를 (a-1, a-1)로 할지, (a, a)로 할지가 되고, 둘 다 확률이 1/2라 두 선택지가 모두 가능해짐.

[익명(147.47)]

따라서 이 경우엔 문제에서 말한 대로 최대한 게임이 빨리 끝나게 해야 되고, 결국 A가 자신의 점수를 높이는 선택지(즉 남은 점수가 (a-1, a-1)이 되는)를 골라야 함. 이전의 풀이에서는 이 '확률이 같으면 최대한 빨리 게임이 끝나게'를 잊고 있다가 a-b=1일 때 (a, a)로 간다는 식으로 전략을 잘못 정해서 25가 나왔음...

[익명(147.47)]

아무튼 저 사실을 쓰면, A팀이 5-a, B팀이 5-b점 얻은 상황에서 승패가 결정나기까지 더 해야 하는 게임 라운드 수의 기댓값을 X(a, b)라 할 때, 다음 사실이 만족됨을 대칭성+점화식으로 구할 수 있음. 1) X(a, b)=X(b, a) 2) X(a, 0)=X(0, b)=1 3) X(a, a)=1+X(a-1, a)

[익명(147.47)]

4) 2<=a<=5에 대해 X(a-1, a)=1+0.5*(X(a-2, a)+X(a-1, a-1)), 5) 1<=k<=a-2에 대해 X(a-k, a)=0.5*(X(a-k-1, a)+X(a-k+1, a))+1 이제 X 점화식 풀면 최종적으로 X(5, 5)=11 나와서 답은 11임이 구해지게 됨.

[익명(147.47)]

아 잘못적었네 X(0, a)=X(b, 0)=0임

[수갤러 1(122.40)]

답 11 맞고 markov model 짜고 수렴시키니 바로 나오네(즉 그냥 식으로 풀림)
https://pastebin.com/pMFmzayA