| [ QuizWit ] in KIDS 글 쓴 이(By): constell (나의 꿈) 날 짜 (Date): 1997년07월17일(목) 12시36분46초 KDT 제 목(Title): Re: [문제] 바둑돌 옮기기 제가 문제를 맞게 이해했는지 모르겠는데, 답을 보시고 맞게 이해했는지 살펴 주세요. 각 동전마다, "현재 내가 나의 원래 위치에서부터 시계방향으로 몇번 돌았는지"를 keep하고 있다고 합시다.(0~5) 처음 상태에는 다 0일 거고, 시계방향으로 돌면 +1 또는 -5 (= 1 mod 6), 반시계방향으로 돌면 -1 또는 +5 (= -1 mod 6)만큼 더해주면 됩니다. 이 여섯개의 값들의 합을 생각하면, 처음에는 0입니다. 한 스텝 움직이면, 이 합의 변화는 항상 0(mod 6)입니다. 따라서 이 '총합'은 항상 0(mod 6)입니다. 그런데 만약 동전들이 다 한군데로 모였다면, 반드시 이 총합은 0 + 1 + .. + 5 = 15 =\= 0 (mod 6)이 되어야 합니다. 따라서 불가능합니다. Invariant를 찾는 유형의 문제 같은데요.. |