폴리매스

엔곰 2017.03.03. 22:56

아마도 '가장 적은 횟수로' 아닐까요?

85 2017.03.03. 23:52

엔곰  그럴수도 있겠네요. 같은 시간동안 1회씩 간다고 하면 더빨리 가니까요.

수학자 2017.03.04. 11:30

두 방법 A와 B에 대한 비교를 생각해 보면, 자연수 N이 존재하여, 각 방법으로 n번 이동했을 때 가장 왼쪽에 있는 벼룩의 위치(가장 오른쪽이나 평균 등도 고려해볼 수 있음)가 n>N일 때마다 항상 A 방법이 B 방법보다 오른쪽이라면, A 방법은 B 방법보다 더 빨리 오른쪽으로 이동할 수 있는 전략이라고 정의할 수 있을 듯 합니다

프로벤젠 2017.03.05. 20:46

아니면 언제나 빨라질 수 있는 방법을 말하는 건가요?

85 2017.03.05. 23:41

이문제의 애매한 것은
문제 자체가 아니라
가짱 빨리 이동할수 있는 전략인가? 라는것이
어떤 방법을 가르켜 주지 않으니
제생각에는 수학자님처럼 차례대로 이동시키는 방법과 거꾸로 차례대로 이동시키는 방법 총 3개를 두고 찾아야 될것 같습니다.

프로벤젠 2017.03.07. 20:51

그러면 수정된 정보에서 수정된 N은 어떠한 의미가 있죠? N이 1일 경우에는 모든 경우에서 성립함을 보여라. 라는 말이 되지 않나요?
궁금해서 질문드립니다.

c 언어 2017.03.13. 01:48

엔곰님 말대로 벼룩이 움직일때 한차례, 한차례를 기준으로만 본다면 엔곰님 말이 맞지만 문제에서는 한번할때 최대로 움직이는 것이 아니고 여러변 하였을때의 빠르게(같은 횟수면 최대로)움직일수 있게 하는 것입니다.
첫번째로 이동할때는 최대가 아니더라도 그 다음에 간 거리가 최대인 경우도 있을수 있으니 여러번 움직였을때 결과값으로 비교를 해야 될거 같습니다. 아니면 여러번 움직였을때의 값보다 한차례 한차례 최대로 간 경우가 더 먼거리를 간다는 것을 증명해도 될거 같고요.

엔곰 2017.03.13. 01:53

c 언어  결국 한 차례를 하고 어떤 벼룩이 가장 먼거리로 갈 수 있다면 그 다음 차례에도 그 벼룩을 기준점으로 잡아 양단 이동을 할 수 있을 것이고, 마지막 An의 벼룩까지 똑같은 방식으로 하면 모두 양단 이동시키는 방법이 n번 이동하는 방법들 중 가장 오른쪽으로 멀리 보낼 수 있는 방법이라는 것을 알 수 있습니다.

1번째 이동에 무슨 방법을 선택하는 다시 왼쪽부터 B1~Bn이라고 잡게 되면 그 모든 과정이 낱개로 나눠서 푸는것과 동일하므로 오류는 없는 것 같습니다.

프로벤젠 2017.03.16. 23:17

엔곰  그런데 ㅅ(람다)의 값이 0에 수렴하면 A1을 잡든, Ak(n>k>1인 자연수)를 잡든 An에 굉장히 가까이 붙어있어 항상 오른쪽이라고만은 볼 수 없지 않을까요?

혹은 ㅅ(람다)가 무한대에 수렴하면, 똑같은 원리로 어떤 점을 잡던지 동일하지 않을까요?

엔곰 2017.03.16. 23:20

프로벤젠  0에 수렴할 정도로 작아진다 해도 λ가 0이 아닌 이상 조금의 차이라도 #(A₁,A_n)과 #(A₂,A_n)은 조금의 차이라도 나게 되어있습니다. A₁과 A₂가 같은 점이 아니고, λ도 0이 아니기 때문에 0이 아닌 람다에선 항상 양단 이동이 최적의 전략이라 볼 수 있을 것 같습니다.

프로벤젠 2017.03.16. 23:39

엔곰  BC=AB*ㅅ(람다) ㅅ은 양의 실수 따라서 BC는 AB에 비례한다. BC의 최대는 AB의 최대를 잡는 것과 같다. 그렇기 때문에 양단이동이 최선의 선택이다.

음.. 엔곰님의 말씀이 맞는 것 같네요. 양단이동이 가장 좋은 선택이네요.

이건 제가 추가로 생각해 본 건데, AC의 길이를 최대로 하기 위해서는 어떻게 잡는 것이 가장 좋을까요?

엔곰 2017.03.17. 00:04

프로벤젠  람다가 일정한 상태라면 AC=AB+BC=AB+λAB=(λ+1)AB이므로 AB가 길수록 AC도 길죠. 따라서 마찬가지로 양단이동할 경우 AC가 가장 길다고 볼 수 있겠군요!

프로벤젠 2017.03.17. 00:16

엔곰  그러면 AC의 길이가 아닌, 가장 왼쪽의 점과 가장 오른쪽의 점의 길이의 최댓값은 어떻게 하는게 최선의 방법일까요?

여전히 양단이동이 최선의 방법인가요, 아니면 처음에는 A₂를 옮기고, 나머지는 B₁, C₁,~~를 옮기는 것이 가장 길어질까요?

엔곰 2017.03.17. 00:54

프로벤젠  S(A,B)=A,B 사이의 거리.

벼룩이 있는 서로 다른 점 A₁, A₂, ... , A_n이 있다. 여기서 N번의 이동을 하고 (N은 n이하의 자연수), 양 끝점 사이의 거리가 가장 길게 하는 전략을 구하자.

우선 N=2일때의 경우를 보자.
i)양단 이동을 하는 경우
→A₁이 An+λS(A₁,An)으로 이동. 다음은 An+λS(A₁,An)+λ[S{An+λS(A₁,An),A₂]으로 이동.

ii)A₂부터 이동시키고, A₁을 이동시키는 경우
→A₂가 An+λS(A₂,An)으로 이동. 다음은 An+λS(A₂,An)+λ[S{An+λS(A₂,An),A₁]으로 이동.

i)An+λS(A₁,An)+λ[S{An+λS(A₁,An),A₂]
ii)An+λS(A₂,An)+λ[S{An+λS(A₂,An),A₁]

에서 i)와 ii)를 비교했을때 An은 공통이므로 빼주고, 양변에 λ를 나누면

i)S(A₁,An)+S{An+λS(A₁,An),A₂}
ii)S(A₂,An)+S{An+λS(A₂,An),A₁}

뒤의 두 식을 비교했을 때 같거나 i)가 더 크다는 것을 알 수 있다. 따라서 빼주면

i)S(A₁,An)
ii)S(A₂,An)

에서도 i)가 더 크다는 것을 알 수 있다.
즉, N=2일때를 비롯해 같은 방식으로 n이하의 모든 N에서 양단이동이 가장 최적의 전략이라는 것을 알 수 있다.

프로벤젠 2017.03.17. 16:39

엔곰  풀이 과정 중 밑에서 5~7줄 부분에서
S{An+λS(A₁,An),A₂}와 S{An+λS(A₂,An),A₁}에서
An+λS(A₁,An)가 An+λS(A₂,An)보다는 더 오른쪽에 있지만,
A₁이 A₂보다는 더 왼쪽에 있어
S{An+λS(A₁,An),A₂}와 S{An+λS(A₂,An),A₁}의 길이 비교가 어떻게 된 것이지 궁금합니다.

엔곰 2017.03.17. 16:45

프로벤젠  사실 저도 이 부분이 조금 걸리긴 했습니다만, 최대한 설명해보겠습니다.

i)S(A₁,An)+S{An+λS(A₁,An),A₂}
ii)S(A₂,An)+S{An+λS(A₂,An),A₁}에서

S{An+λS(A₁,An),A₂}=점 An+λS(A₁,An)과 점 A₂ 사이 거리
S{An+λS(A₂,An),A₁}=점 An+λS(A₂,An)과 점 A1 사이 거리

S(A₁,A₂)=k라고 가정하겠습니다.
그럼
S{An+λS(A₂,An),A₁}=S{An+λS(A₂,An),A₂}+k=S{An+λS(A₂,An)+k,A₂}라는 식이 성립하게 됩니다.

S{An+λS(A₁,An),A₂}=S{An+λS(A₂,An)+λk,A₂}라는 식도 성립하게 됩니다.

따라서 최종 두 식을 비교하면 되는데...
다시 보니, λ>1/λ=1/λ<1로 범위를 나눠 풀어야 겠군요.

즉,
λ>1이면 [A₁>A₂...로 하는 양단 이동]
λ=1이면 [A₁이동=A₂이동]
λ<1이면 [A₂>A₁... 로 하는 양단 이동]

--------------------------------------------
이거 틀린 풀이입니다.
밑에 수정본 적어놨습니다.

엔곰 2017.03.17. 16:52

프로벤젠  혹, 오류가 있다면 답글 부탁드립니다.

프로벤젠 2017.03.17. 16:55

엔곰  맞는 것 같습니다. 오 대단하시네요^^

엔곰 2017.03.17. 18:43

프로벤젠  죄송합니다.. 중간에 오류가 있었던 것 같네요.

i)양단이동: S(A₁,An)+S{An+λS(A₁,An),A₂}
ii)A2부터: S(A₂,An)+S{An+λS(A₂,An),A₁}에서

i) S(A₁,An)+S{An+λS(A₁,An),A₂}: S(A₁,A₂)=k라고 가정하겠습니다.
그럼
S(A₁,An)+S{An+λS(A₁,An),A₂}=S(A₂,An)+S{An+λS(A₁,An),A₂}+k=S(A₂,An)+S{An+λS(A₁,An),A₁}라는 식이 성립하게 됩니다.

즉 i 정리) S(A₂,An)+S{An+λS(A₁,An),A₁}
ii) S(A₂,An)+S{An+λS(A₂,An),A₁}

따라서 최종 두 식을 비교하면 ,
λS(A₁,An)>λS(A₂,An)이므로 λ>0인 모든 λ에 대해 i)가 항상 커지게 됩니다.

즉 <양단이동>의 경우가 최적의 전략임을 알 수 있습니다.

프로벤젠 2017.03.18. 12:01

엔곰  두 풀이에서 어떤 차이점이 있었던 건가요?
컴퓨터로 보니 두 풀이를 동시에 보기 힘드네요ㅠㅠ
그리고 저는 위 풀이에서 틀린점을 못찾겠네요..

그리고 N=2일때, A₂를 옮기고 A₃를 옮기면 양단이동보다 더 길어지는 반례를 발견한 것 같습니다.

프로벤젠 2017.03.18. 12:31

프로벤젠 http://blog.naver.com/sungc3h8?Redirect=View&logNo=220961072096&categoryNo=9&isAfterWrite=true&isMrblogPost=false&isHappyBeanLeverage=true&contentLength=4511

λ=0.5, S(A₁,A₂)=1, S(A₂,A₃)=1, S(A₃,An)=8

네온 2017.03.18. 13:17

프로벤젠  위 풀이에선 앞에 더할 출발점을 안 더했습니다.

프로벤젠 2017.03.18. 14:44

네온  벼룩이 이동하는 것이기 때문에 양단 이동의 경우에는 A₁, A₂의 위치는 고려하지 않는 것이 맞지 않을까요?

네온 2017.03.18. 14:52

프로벤젠  출발점+간거리를 해야 도착점의 위치가 되므로 출발점을 더해야 한다는 말입니다.

프로벤젠 2017.03.18. 15:43

네온  제가 제시한 내용은 대한 수학회에서 제시한 문제를 풀다가 궁금증이 있어서 올린 질문에 대한 반례입니다^^

엔곰 2017.03.22. 23:55

프로벤젠  반례에는 문제가 없네요.

양단이동이 N₂→N₁으로 가는것보다 항상 좋다는 제 풀이는 맞는것 같습니다.

프로벤젠 2017.03.23. 00:56

엔곰  그러면 언제나 A₁을 움직이지 않고 그 다음으로 가장 왼쪽에 있는 A₂ ,B₂,---가 최선의 방법이지 않을까요? 저도 시간날 때 증명해 보겠습니다.

엔곰 2017.03.23. 01:12

프로벤젠  이제 마무리를 할 때네요..
윗 증명으로 양단이동이 최선의 전략이라는 풀이가 나왔고, 이제 고민할 것은 반례가 나오지 않는 이상 한 가지일 것 같습니다.

[A₁ 포함 양단이동 or A₁제외 양단이동]

프로벤젠님이 제시하신 A₂>A₃ 반례도 결국 A₁을 제외한 양단이동에 포함되는 것이죠..

A₁을 포함하면 멀리 갈 것이지만 맨 왼쪽 벼룩이 짧아진다는 단점이 있고,
A₁을 제외하면 비교적 멀리는 못 가겠지만 맨 왼쪽 벼룩이 A₁으로 고정된다는 이점이 있습니다.

그럼 하나씩 따져보겠습니다.

(N=2일때 구한 뒤 일반화)

i)A₁을 포함한 양단이동
즉 A₁→A₂로 했을 때 최종 양쪽 벼룩의 거리는
S(A₃, An+λS(A₁,An)+λS{A₂,An+λS(A₁,An)}

ii)A₁을 제외한 양단이동
즉 A₂→A₃로 했을 때 최종 양쪽 벼룩의 거리는
S(A₁, An+λS(A₂,An)+λS{A₃,An+λS(A₂,An)}

S(A₁,A₂)=k, S(A₂,A₃)=m이라고 두자.

둘 다 있는 괄호 안의 An을 지우고 λ를 나눈다.

A₁포함: S(A₃, An+λS(A₁,An)+λS{A₂,An+λS(A₁,An)}
=S{A₃, S(A₁,An)+S{A₂,An+λS(A₁,An)}

A₁제외:S(A₁, An+λS(A₂,An)+λS{A₃,An+λS(A₂,An)}
=(k+m)+S(A₃, S(A₂,An)+S{A₁,An+λS(A₂,An)}

출발점은 A₃로 같으므로S를 지워주고 대소 관계를 따져도 무관하다.

A₁포함:S{A₃, S(A₁,An)+S{A₂,An+λS(A₁,An)}
=S(A1,An)+S{A2,An+λS(A1,An)}
=(k+m)+S(A₃,An)+S{A₂,An+λS(A₁,An)}

A₁제외:
(k+m)+S(A₃, S(A₂,An)+S{A₁,An+λS(A₂,An)}
=(k+m)+S(A₂,An)+S{A₁,An+λS(A₂,An)}

(k+m)을 지워주면,

A₁포함:
S(A₃,An)+S{A₂,An+λS(A₁,An)}

A1제외:
S(A₂,An)+S{A₁,An+λS(A₂,An)}
=m+S(A₃,An)+S{A₁,An+λS(A₂,An)}

S(A₃,An) 지워주면,

A₁포함:
S{A₂,An+λS(A₁,An)}

A1제외:
=m+S{A₁,An+λS(A₂,An)}
=m+k+S{A₂,An+λS(A₂,An)}

출발점 A₂로 같으므로 S지우고 An도 지우고 대소 따지면:

A₁포함:λS(A₁,An)=λS(A₂,An)+λk

A₁제외:m+k+λS(A₂,An)

λS(A₂,An), k를 지우면 최종적으로

A₁포함:(λ-1)k

A₁제외:m

즉
(λ-1)×(A₁,A₂거리)>(A₂,A₃거리) 면 A₁포함 양단이동이,
(λ-1)×(A₁,A₂거리)<(A₂,A₃거리) 면 A₁제외 양단이동이 최선.

이라는 어쩐지 복잡한 답이 나왔군요.
오류거 있을 것만 같은 불길한 느낌..

프로벤젠 2017.03.23. 22:42

엔곰  풀이과정에서 오류는 없어 보이지만, 답이 너무 더럽네요...

그러면 기본적으로 λ가 1 이하면 무조건 A₁제외 양단이동이 최선이겠네요.

그러나 λ가 1보다 큰 양수면 굉장히 이상하네요. 깔끔하게 나올 것 같았는데 말이죠.

그러면 이것이 최종답변이겠죠? 혹시 더 깔끔하게 바꿀 수 있는 방법이 있을까요?

엔곰 2017.03.23. 23:54

프로벤젠  이게 최종일 것 같네요.

엔곰 2017.03.23. 23:54

프로벤젠  이게 최종일 것 같네요.

프로벤젠 2017.03.25. 13:31

엔곰  오랫동안 도와주셔서 감사합니다.^^

엔곰 선수의 증명은 벼룩이 두 번 이동할 때에 한해 양단 이동이 벼룩을 가장 멀리 보낸다는 뜻이에요. '이동을 단 두 번 실시한 결과를 비교하는 것으로 증명이 끝나서는 안 된다는 출제자의 의견이 있었습니다. 따라서 이 문제는 아직 풀리지 않았습니다.

벼룩이 이동하는 위치가 정해져 있다는 것이 더 이상 나갈 수 없다는 뜻이니까요, 거리가 일정하게 오른쪽으로 가다가 멈추면 해당사항이 없어지네요.