sisuforbrd   1년 전

안녕하세요,
문제에서 최적의 전략으로 문제를 풀 때 최대 행동 횟수를 구하는 방식에 대해 한 가지 의문점이 있어 의견 남깁니다.

예를 들어, 카드가 4쌍(총 8장) 있고, 카드 종류를 각각 1, 2, 3, 4라고 가정해 보겠습니다.

  • 1행동: 카드 1과 카드 2를 뒤집어 서로 다른 종류임을 확인
  • 2행동: 카드 3과 카드 4를 뒤집어 서로 다른 종류임을 확인

이 시점에서 모든 카드의 위치와 종류를 파악할 수 있으므로, 이후에는 어떤 카드를 뒤집더라도 이미 확인된 짝을 맞출 수 있습니다.
즉, 남은 4쌍의 카드를 각각 제거하는 데 추가 4회의 행동이 필요하므로, 총 6회의 행동으로 게임을 마칠 수 있습니다.

따라서 최대 행동 횟수는

p+⌈p2⌉

로 계산되어야 하며, 이 경우 p = 4이므로 4+⌈4/2⌉=4+2=6회가 되어야 합니다.

문제에서 만약 다른 방식으로 계산되었다면, 위 반례(카드 종류가 1,2,3,4인 경우)를 참고하여 수정이 필요하다고 생각합니다.

추가로, 카드가 5쌍(총 10장) 있고, 카드 종류를 각각 1,2,3,4,5라고 가정한다면

  • 1행동: 카드 1과 카드 2를 뒤집어 서로 다른 종류임을 확인
  • 2행동: 카드 3과 카드 4를 뒤집어 서로 다른 종류임을 확인
  • 3행동: 카드 5와 카드 ?(5를 제외한, 뒤집지 않은 1~4 중 하나)를 뒤집어 서로 다른 종류임을 확인

마찬가지로 이 시점에서 모든 카드의 위치와 종류를 파악할 수 있으므로 이후에 어떤 카드를 뒤집더라도 이미 확인된 짝을 맞출 수 있습니다.

따라서 이같은 경우에는 5+⌈5/2⌉=5+3=8회의 행동으로 게임을 마칠 수 있습니다.

확인 부탁드립니다.

lycoris1600   1년 전

최적의 전략을 사용했을 때 최대 횟수가 나오는 케이스(worst case)는 다음과 같습니다.

말씀하신 대로, 1 2 3 4의 카드가 2장씩 존재하며, 이를 각각 11 12 21 22 31 32 41 42라고 하겠습니다.

시행 1. 11 21
시행 2. 31 12
시행 3. 11 12
시행 4. 41 22
시행 5. 21 22
시행 6. 32 31
시행 7. 42 41

다음 방법으로 7회가 나오게 됩니다.

sisuforbrd   1년 전

앗...!! ㅎㅎ 그렇네용 생각해보니 새로운 카드를 밝히는 초반 뽑기에서 하나는 새로운 종류의 카드를 뽑고, 나머지 하나는 이미 나온 종류의 또 다른 카드를 뽑아서 모든 종류의 카드를 뽑는 횟수를 지연시킬 수가 있군용..!!

친절하게 알려주셔서 감사합니당

wizardrabbit   1년 전

안녕하세요, 말씀하신 주장에 대한 반례를 제시해 보아도 될까요? 저는 카드가 4쌍인 상황을 이야기해 보겠습니다.

질문자님이 말씀하신 최악의 상황의 경우, $8$장의 카드 중 $1$ ~ $4$장의 카드의 종류가 모두 다른 상황이었습니다. 이 경우 $2$회의 시행착오를 통해 네 종류의 카드의 위치를 모두 확보하고, 그 다음 이어지는 $4$회의 시도에서는 아직 펼쳐보지 않은 카드들 중 아무거나 하나를 고른 후, 펼쳐본 카드들 중 그 종류에 대응하는 카드를 고르면 항상 정확하게 맞출 수 있으므로 해당 시나리오에서는 최악 $2 + 4 = 6$회의 시도를 해야 맞출 수 있는 것은 맞는 것 같습니다.

하지만 이것보다 더 최악인 상황이 있을 것 같습니다. 사실, $4$장의 카드를 펼쳐 모두 다른 종류의 카드임을 확보한 상황은 나름 유리한 상황일 수도 있어 보입니다.

최악의 시나리오

preview

카드들은 위와 같이 배치되어 있습니다. 최선을 다해 이 게임을 클리어해 보겠습니다. 최악의 상황을 상정했으므로 운은 최악인 상황입니다.

  • $1$번째 시도: $1$번째 카드, $2$번째 카드를 순서대로 고르고 펼쳤습니다. 두 수는 $1$과 $2$로 서로 다르니 원래대로 되돌렸습니다. 그 대신 종류 $1$, $2$의 카드가 어디 있는지는 알게 되었습니다.
  • $2$번째 시도: $3$번째 카드, $4$번째 카드를 순서대로 고르고 펼쳤습니다. 두 수는 $3$과 $2$로 서로 다르니 원래대로 되돌렸습니다. 그 대신 종류 $3$의 카드가 어디 있는지는 알게 되었습니다.
    • $4$번째 카드를 먼저 고른 경우와는 다릅니다. 이 경우 플레이어는 종류 $2$의 카드가 어디 있는지 알기 때문에 바로 $4$번째 카드에 이어 $2$번째 카드를 공개해 카드를 맞추려고 할 것입니다.
    • 그리고, 말씀해 주셨던 최악의 경우와 달리 이 상황에서는 $2$번의 시도를 하고도 모든 종류의 카드의 위치를 확보하지 못했습니다.
  • $3$번째 시도: $5$번째 카드, $6$번째 카드를 순서대로 고르고 펼쳤습니다. 두 수는 $4$와 $1$로 서로 다르니 원래대로 되돌렸습니다. 이제서야 모든 종류의 카드의 위치가 확보됩니다.
    • 그러니까, $3$번째 시도에서도 운이 나빠 종류의 위치가 확보되지 않은 종류 $4$의 카드를 펼칠 시에는 남은 카드들 중 종류 $4$가 있는 카드의 위치를 모르므로 운이 좋지 않을 경우 또 맞출 수 없는 상황이 생깁니다.
  • $4$ ~ $7$번째 시도: 모든 종류의 카드가 확보되었으니 확보하지 않은 아무 카드를 펼친 후 그 종류에 맞는 확보된 카드를 고르면 항상 맞습니다. 여기서부터는 적중률이 $100%$입니다.

따라서, 이 상황에서는 시도 횟수가 $7$회가 되었습니다. 플레이어가 일부러 바보같은 선택을 한 것이 아닌, 정말로 정보가 부족해 최악의 선택을 한 상황이 되었습니다.

카드가 $5$쌍인 상황도 비슷한 예시를 적용해 보실 수 있을 것 같습니다. 만약 잘못된 점이 있다면 알려주세요!

sisuforbrd   1년 전

와...!! 너무 친절하게 알려주셔서 감사해용 ㅠㅠ 제가 가장 '운이 없는 경우'를 충분히 고민하지 못했던 것 같습니다...!!

elic121   1년 전

쉽게 말하면 계속 다른 종류를 뽑는다는 가정이 최악이 아니네요

댓글을 작성하려면 로그인해야 합니다.