| [ QuizWit ] in KIDS 글 쓴 이(By): guest (게쭈환상) <ppp037.109-253-2> 날 짜 (Date): 1999년 11월 25일 목요일 오전 02시 08분 18초 제 목(Title): 동전나누기 (마지막답) 0,1이란 숫자들이 짝수개가 있는데 어레이안에 들어있습니다. 컴퓨터가 이걸 쏘팅을 하는데, 절대 숫자의 크기를 비교를 못하고 그냥 0은 1로 1은 0으로 플리핑하는 오퍼레이션만 가능합니다. 이럴경우 이짝수개의 숫자를 반으로 나누었을때 양쪽에있는 0의 숫자가 같아지게 할수있는가 하는문제하고 동전문제는 동치네요. 근데 백날 플리핑해봐라. 우연히 같아질수는 있지만, 이게 어떻게 같아집니까. 문제에 조건이 아무래도 빠진것같네요. 인포메이션이 더필요합니다. 컴퓨터로 알고리듬짤수있어야할건데 못짤겁니다. 위조건만가지곤. 증명. 가장 4개로 앞면이 3개있다고 가정하고 (앞면,뒷면) 이라는 노테이션쓰면 우선 (2,0),(1,1) 으로 파티션이 됩니다. (2,0)에서 한개르 플리핑하면 당연히 같아지는데 (1,1)에서 한개를 플리핑할경우는 확률 1/2로 같아지거나 달라질수있습니다. 즉 (1,1)에서 플리핑을 하면 (2,0)이나 (0,2)가 될수있습니다. 하지만, 어둠속이기 때문에 (2,0)인지 (0,2)인지 결코 알수없고 고로 절대로 확률 1인가능성으로 두파티션의 동전을 플리핑만가지고 같게는 할수가 없습니다. 즉 인포메이션이 더필요해요. 어휴 그냥 답을 말해 힌트,좀더 힌트,마지막힌트.... 등등으로 사람긁지말아~ 그러다 오이듀알샥 마사지 해줄꺼야. |