수학동아 - 폴리매스

폴리매스 문제

아직 아무도 답을 모르는 문제에 도전하세요!

[대한수학회] 대26. 돌아온 틱택토(Tic-Tac-Toe) 게임

수학동아 2019.02.01 09:36 조회 4377

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

대한수학회 26번

돌아온 틱택토(Tic-Tac-Toe) 게임

문제 출제자 : 신희성 인하대학교 수학과 교수

틱택토(Tic-Tac-Toe) 게임은 가로세로 3칸씩 총 9칸으로 이뤄진 사각형 판에서 두 사람이 하는 게임이다. 두 플레이어는 번갈아가며 한 사람은 검은색, 다른 한 사람은 흰색 돌을 빈 칸에 놓고, 행과 열 또는 대각선에 자기 돌 3개를 놓으면 승리하고 경기를 멈춘다. 회전하거나 대칭했을 때 진행이 같아도 다른 경기로 생각한다.

[문제]

1 두 플레이어가 돌을 무작위로 놓을 때 가능한 경기의 수를 구하여라.

2 위 문제에서 처음 시작한 플레이어가 이긴 경기의 수를 구하여라.

3 두 플레이어가 최선의 수를 두어 진행할 때, 진행 수순을 구하여라.

※알립니다※

muse 친구의 풀이가 최종 정답으로 확인되면서

26번 문제도 '해결'입니다!

이전글 대25. 다면체로부터 얻어지는 수열

다음글 대27. 레이저 속 광자의 개수를 세라!

문제 찜하기 목록보기

댓글 작성하기

EulerD Lv.1 2019.02.01 20:03

1. 돌리거나 뒤집어서 같은 두 틱택토는 다른것으로 취급.

2. 같은 틱택토라도 돌을 놓는 순서가 다르다면 다른 틱택토로 취급

제 해석이 맞는 것인지 모르겠네요..

댓글 작성하기 좋아요0 댓글수3
- muse Lv.6 2019.02.01 21:30
  
  글쎄요. 제가 생각할 때는
  
  1. 돌리거나 뒤집어서 같은 두 틱택토는 같은 것으로 취급.
  
  2. 같은 틱택토라도 순서가 다르면 다른 것으로 취급.
  
  인 것 같습니다.
  
  좋아요0
- muse Lv.6 2019.02.01 21:57
  
  수학동아에서 정확한 정의를 알려주지 않는 한은 풀기 힘들 것 같습니다.
  
  좋아요0
- 승민짱 Lv.1 2019.03.20 06:48
  
  네 EulerD님 해석이 맞는거 같네요
  
  (회전하거나 대칭했을 때 진행이 같아도 다른 경기로 생각한다) 부분에서 다른 돌리거나 뒤집어서 다르면 다른 경기라네요
  
  그리고 누가 먼저 하는지는 상관이 없나요???
  
  좋아요1
EulerD Lv.1 2019.02.01 20:11

#1

이 문제의 핵심은 틱택토에서 승리한 경우 더이상 말을 놓지 않는다는 것입니다.

그러니까, 돌이 단 5개만 놓일수도, 9개 전부 놓일수도 있습니다.

어느사람이 몇번째 말을 놓았을때 승리하는지에 따라 case를 나누었습니다.

참고로 검은색 말이 먼저하는 사람, 흰색이 나중에 하는 사람입니다.

그리고 그 안에서 어느 위치에 3개가 연달아 있어 승리하는지와 누가 승리하는지에 따라 또 case를 나눕니다.

마지막으로, 끝까지 끝나지 않는 경우는 흰색의 위치 4개만 승리하는 사람이 없도록 정하고 나머지 위치에 검은색 말이 있다고 생각하면 됩니다.

풀이가 노가다성이 다분한 풀이일테니 좀 끊어서 올리겠습니다.

댓글 작성하기 좋아요0 댓글수2
- EulerD Lv.1 2019.02.01 20:15
  
  계산을 어떻게 할 지 계획해보겠습니다.
  
  각각의 case에 대해 고려해야 할 상황은 나머지 말들(제가 올린 사진에서는 일부 말들만 그려져 있습니다)과, 회전, 돌 놓는 순서입니다.
  
  아직 문제에서 회전을 어떻게 처리해야하는지 잘 모르겠습니다.(문제 이해가 잘 안됩니다)
  
  일단은 회전, 대칭했을때 같은것은 같은 배치로 고려하는게 조금 더 편할 지도 모르겠습니다.
  
  좋아요0
- EulerD Lv.1 2019.02.01 20:16
  
  이 방법으로 계산하면 2번도 동시에 해결할 수 있겠지요??
  
  좋아요0
EulerD Lv.1 2019.02.01 20:23

3번은 틱택토는 무조건 비기는 것으로 알려져 있기 때문에...........왠만한 경우 비기게 둘 수는 있지만,

이 문제에서 요구하는 최선을 다하는 수순은 각 말을 놓은 후의 수순들을 무작위로 했을때 가장 이길 확률이 높은 수순을 고려하라는 것 같습니다.

댓글 작성하기 좋아요0 댓글수3
- EulerD Lv.1 2019.02.01 20:26
  
  일단 알려진 바로는 시작플레이어가 귀에 놓는 것이 유리하고
  
  그다음 플레이어는 중앙에 놓는 것이 유리하다고 알고있습니다.
  
  좋아요0
- EulerD Lv.1 2019.02.01 20:30
  
  참고할 만한 사진들입니다.(출처: Wikimedia)
  
  좋아요1
- 아루키데메스 Lv.5 2019.02.03 07:12
  
  이것들이 다 뭔가여??
  
  좋아요0
muse Lv.6 2019.02.01 21:58

우선 돌리거나 뒤집었을 때 같은 두 틱택토를 다르다고 놓고 풀어 보겠습니다.

댓글 작성하기 좋아요0 댓글수4
- muse Lv.6 2019.02.01 22:03
  
  문제가 상당히 모호하여서 무엇을 의미하는지 정확히 모르겠습니다.
  
  돌리거나 뒤집어서 같은 것을 서로 다른 보드라고 보았을 때:
  
  1) 두 플레이어가 무작위로 돌을 놓을 때 경기 중 가능한 배치의 개수(초기 상태 포함): 549946
  
  2) 두 플레이어가 무작위로 돌을 놓아 경기가 종료되었을 때 가능한 배치의 개수: 255168
  
  3) A가 이긴 경우의 수: 131184
  
  4) B가 이긴 경우의 수: 77904
  
  5) 무승부인 경우의 수: 46080
  
  돌리거나 뒤집어서 같은 것을 서로 같은 보드라고 보았을 때:
  
  1) 68752
  
  2) 31896
  
  3) 16398
  
  4) 9738
  
  5) 5760
  
  이 안에 문제 출제자가 의도한 답이 있겠죠?
  
  좋아요0
- muse Lv.6 2019.02.01 23:36 비밀댓글
  
  비밀 댓글이 등록 되었습니다!
- EulerD Lv.1 2019.02.01 23:38
  
  프로그래밍으로 푸신건가요?
  
  좋아요0
- muse Lv.6 2019.02.01 23:46
  
  네.
  
  좋아요0
muse Lv.6 2019.02.01 23:10

틱택토 게임의 경우 두 플레이어가 최선으로 플레이하면 무승부라는 것이 알려져 있는데 이 문제에서 최선의 수라는 것이 무엇을 의미하는 것인가요? 단순히 최선으로 했을 때를 구하라면 다양한 가짓수가 나올 것 같은데요.

댓글 작성하기 좋아요0 댓글수1
- EulerD Lv.1 2019.02.01 23:39
  
  어떤 수 이후에 무작위로 두었을때 이길 확률이 가장 높은 것???
  
  좋아요0
인천 오일러 Lv.2 2019.02.02 00:39

A PHP Error was encountered

Severity: Warning

Message: mkdir(): Permission denied

Filename: libraries/Common.php

Line Number: 202

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 202
Function: mkdir

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: file_put_contents(/DATA/upload/polymath/latex/d0d22db8c526c57cb5d35df880cc298c.gif): Failed to open stream: No such file or directory

Filename: libraries/Common.php

Line Number: 213

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 213
Function: file_put_contents

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

(3번 문제)가능한 경우 몇몇을 검토해 보았습니다. 비슷한 결과가 나오는 과정들은 생략하였습니다. 보아하니 처음에 귀퉁이에 놓으면 다음 사람이 임의로 돌을 놓을 때 $\frac{7}{8}$ 의 확률로 이기네요.

1-4와 같은 경우까지 합치면 확률이 더 올라갑니다. 두 명 다 최선을 다하고 몇수 앞을 보는 알파고들 이라고 하면 1-2 ,1-3 ,1-5 ,1-6 중 하나로 전개 될 것으로 예상됩니다. 두 명이 다 최선을 다하면 다 비깁니다. /resources/comment/2019/02/34bfff4e455cf37a92890e49937f8846.show

댓글 작성하기 좋아요0 댓글수0
muse Lv.6 2019.02.02 01:02

답은 아래와 같습니다.

X1 -> Y5 -> X9 -> Y2 -> X8 -> Y7 -> X3 -> Y6 -> X4

X1 -> Y5 -> X6 -> Y2 -> X8 -> Y7 -> X3 -> Y9 -> X4

X1 -> Y5 -> X6 -> Y2 -> X8 -> Y9 -> X4 (7) ->　Y7 (4) -> X3

X1 -> Y5 -> X6 -> Y3 -> X7 -> Y4 -> X8 (9) -> Y9 (8) -> X2

X1 -> Y5 -> X6 -> Y8 -> X2 -> Y3 -> X7 -> Y4 -> X9

X1 -> Y5 -> X6 -> Y9 -> X2 -> Y3 -> X7 -> Y4 -> X8

X1 -> Y5 -> X6 -> Y9 -> X3 -> Y2 -> X8 -> Y4 (7) -> X7 (4)

X1 -> Y5 -> X6 -> Y9 -> X7 -> Y4 -> X2 (3) -> Y3 (2) -> X8

X1 -> Y5 -> X6 -> Y9 -> X8 -> Y2(3, 7, 8) -> X4/7(4/7, 2/3, 2/3) -> Y(7/4, 3/2, 3/2) ->　X3(2, 8, 7)

결과는 모두 무승부입니다.

풀이 (왼쪽 링크를 누르세요)

댓글 작성하기 좋아요0 댓글수0
김우현 기자 Lv.5 2019.02.02 02:53

문제를 풀 때 필요한 조건이 불충분했군요.

친구들이 남긴 의문을 교수님께 전달드렸으니 조금만 기다려주세요!

댓글 작성하기 좋아요0 댓글수0
muse Lv.6 2019.02.02 08:25

흥미롭군요.

게임을 하는 사람이 상대방은 완전히 무작위로 돌을 둔다고 보고 모든 수를 둘 확률이 같다고 볼 때, 이길 확률이 가장 큰 움직임을 하게 만들어 봤습니다.

1: X5
2: Y1
3: X3
4: Y4
5: X7

의 결과가 나왔습니다.

코드는 아래와 같습니다.

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int rows[8][3] = {
0, 1, 2,
3, 4, 5,
6, 7, 8,
0, 3, 6,
1, 4, 7,
2, 5, 8,
0, 4, 8,
2, 4, 6
};

struct tictactoe{ /// 틱택토 구조체를 만듭니다.
/// 3x3 사이즈의 보드를 만드는데, 돌이 없으면 0, 돌이 있으면 몇 번째로 놓인 돌인지를 씁니다.
/// 이때 A가 처음 시작합니다.
/// 일차원 배열로 보드를 만드는 법.
/// [0] [1] [2]
/// [3] [4] [5]
/// [6] [7] [8]
vector<int> board;

/// 이 상황에서 말을 더 놓았을 때 a가 이기는 경우의 수, b가 이기는 경우의 수, 전체 경우의 수(무승부 포함).
int a_win = 0;
int b_win = 0;
int all_cnt = 0;

/// 지나간 턴 수입니다.
int turns;

/// 현재 상황에서 말을 하나 더 놓았을 때 진행할 수 있는 틱택토 판의 모임입니다.
tictactoe* child[9];

tictactoe(){ /// 0-틱택토 생성자.
board.assign(9, 0);
turns = 0;
}

~tictactoe(){ /// 틱택토 소멸자.
for(int i=0; i<9; i++){
if(child[i]){
delete child[i];
}
}
}

tictactoe(vector<int> board): board(board){ /// 틱택토 생성자.
// printf("made tictactoe:");
// for(int i=0; i<9; i++) printf(" %d", board[i]);
// puts("");
turns = 0;
for(int i=0; i<9; i++){ /// 지나간 턴 수 체크.
if(board[i]) turns++;
}
for(int i=0; i<8; i++){ /// 이긴 사람이 있는지 체크.
if(board[rows[i][0]]%2 == board[rows[i][1]]%2 &&
board[rows[i][1]]%2 == board[rows[i][2]]%2 &&
board[rows[i][0]] && board[rows[i][1]] && board[rows[i][2]]){
if((board[rows[i][0]]&1) == 1) a_win = 1;
else b_win = 1;
all_cnt = 1;
break;
}
}
if(turns == 9) all_cnt = 1;
}

void make(){ /// 모든 경우의 수를 만듭니다.
if(a_win || b_win) return;
for(int i=0; i<9; i++){
if(board[i] == 0){
board[i] = turns+1;
child[i] = new tictactoe(board);
child[i] -> make();
board[i] = 0;
a_win += child[i] -> a_win;
b_win += child[i] -> b_win;
all_cnt += child[i] -> all_cnt;
}
}
}

void find_way(){
if(turns == 9) return;
double max_possibility = -0.1;
int idx = -1;
for(int i=0; i<9; i++){
if(child[i] == 0) continue;
double tmp = (double)((turns&1)?(child[i] -> b_win): (child[i] -> a_win))
/ (child[i] -> all_cnt);
if(max_possibility < tmp){
max_possibility = tmp;
idx = i;
}
}
if(idx == -1) return;
printf("%d: %c%d\n", turns+1, (turns&1)?'Y':'X', idx+1);
child[idx] -> find_way();
}
};

int main(){
/// 0-tictactoe를 만듭니다. 초기 상태 틱택토로, 0-벡터와 비슷한 개념입니다.
tictactoe* zero_tictactoe = new tictactoe();
zero_tictactoe -> make();
zero_tictactoe -> find_way();
delete zero_tictactoe;
}

댓글 작성하기 좋아요0 댓글수1
- 인천 오일러 Lv.2 2019.02.02 08:49
  
  가정이 굉장히 흥미롭습니다. 저도 다른 흥미로운 가정을 세워보고 싶네요.
  
  좋아요0
아인수타인 Lv.12 2019.02.02 10:12

허얼... 하루만에 21개 실화임...

댓글 작성하기 좋아요1 댓글수0
김우현 기자 Lv.5 2019.02.02 22:37

문제와 질문의 표현을 일부 수정했습니다. 배열보단 '진행'에 초점을 맞춰 풀어보세요!

댓글 작성하기 좋아요0 댓글수4
- 3dasdd Lv.1 2019.02.09 07:54
  
  김우현 기자님 수학동아 오류 제보를 어디에다 해야 될지 모르겠어서 여기 올리겠습니다 이제서야 봤는데 2019년 2월호 83p에 3번째 시어핀스키 카펫이 잘못 나와있는 것 같아요 한번 확인해주실수 있나요? 감사합니다
  
  좋아요0
- 아인수타인 Lv.12 2019.02.09 09:58
  
  어? 그러네요? 3단계에 한가운데가 파란색으로 꽉 채워야 하지 않나요?
  
  좋아요0
- 김우현 기자 Lv.5 2019.02.10 00:02
  
  제보 감사합니다.
  
  담당 기자에게 연락해 확인해 보겠습니다!
  
  좋아요0
- 최기자 Lv.4 2019.02.12 18:33
  
  안녕하세요!
  
  확인해 보았습니다. 그림이 잘못 그려진 것 맞네요~. 죄송합니다. 한 가운데가 크게 파란색으로 칠해진 것이 맞습니다. 정정하겠습니다~!
  
  좋아요0
21세기오일러 Lv.11 2019.02.02 23:17

3번에서 양쪽다 최선의 수를 두면 다음수순이 되는것 같습니다.

물론 저모양을 돌린 모양도 나오지요.

댓글 작성하기 좋아요0 댓글수0
muse Lv.6 2019.02.03 02:20

그럼 1번은 255168, 2번은 131184입니다.

댓글 작성하기 좋아요0 댓글수0
아인수타인 Lv.12 2019.02.05 02:27

(제 생각엔) 추가문제 나올 것도 같네요.

댓글 작성하기 좋아요0 댓글수0
Cantor Lv.3 2019.02.11 22:30

1 9 6

4 2 5

7 8 3

댓글 작성하기 좋아요0 댓글수0
김우현 기자 Lv.5 2019.02.12 18:50

현재까지 올라온 풀이는 현재 멘토님이 확인 중!

댓글 작성하기 좋아요0 댓글수2
- sincostan Lv.7 2019.02.28 09:35
  
  그런데 확인하는 거 맞나요? 왜 이렇게 오래 걸리지?
  
  좋아요0
- 김우현 기자 Lv.5 2019.02.28 18:21
  
  멘토님이 일부 풀이는 교수님께서 판단할 필요가 있다는 의견을 보내왔습니다.
  
  고로 교수님께 확인 요청 드릴게요~
  
  좋아요0
sincostan Lv.7 2019.02.13 07:31

처음엔 댓글이 많이 달려오다가 갑자기 확 주네요~

댓글 작성하기 좋아요0 댓글수0
김우현 기자 Lv.5 2019.03.04 22:51

현재 교수님께서 풀이를 검토 중입니다! 조금만 더 기다려주세요!!

댓글 작성하기 좋아요0 댓글수0
muse Lv.6 2019.03.22 05:06

풀이를 제출한 지 2달이 다 되어 가는데 아직도 정답 여부를 알지 못하고 있습니다.

검토 결과가 언제쯤 나오나요?

댓글 작성하기 좋아요0 댓글수4
- code Lv.5 2019.03.23 08:10
  
  (바쁘신가 봐요)
  
  좋아요1
- 김우현 기자 Lv.5 2019.03.26 01:17
  
  검토가 늦어져 죄송합니다. 다시 한 번 요청 드렸어요!
  
  새학기가 시작되서 그런지 교수님께서 무척 바쁘신 것 같아요.
  
  좋아요0
- 김우현 기자 Lv.5 2019.04.14 22:55
  
  다음 주 중에 최종 정답 여부가 나올 예정! 오래 기다려줘서 고마워요!!
  
  좋아요0
- 김우현 기자 Lv.5 2019.04.15 18:21
  
  마침내 검토가 끝났습니다~. muse 친구가 교수님의 의도하신대로 프로그래밍을 이용해 잘 풀어줬네요.
  
  대한수학회 26번 문제도 '해결'입니다!
  
  좋아요0

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property Article_model::$best_cnt is deprecated

Filename: ver3/Article_model.php

Line Number: 18

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/models/ver3/Article_model.php
Line: 18
Function: _error_handler

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 322
Function: model

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 392
Function: getFloatingMyInfo

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property Article_model::$popular_cnt is deprecated

Filename: ver3/Article_model.php

Line Number: 19

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/models/ver3/Article_model.php
Line: 19
Function: _error_handler

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 322
Function: model

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 392
Function: getFloatingMyInfo

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property Contents::$article_model is deprecated

Filename: core/Loader.php

Line Number: 353

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 322
Function: model

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 392
Function: getFloatingMyInfo

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: 8192

Message: Creation of dynamic property CI_Loader::$article_model is deprecated

Filename: core/Loader.php

Line Number: 925

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 434
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 559
Function: get_footer

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

수학동아 - 폴리매스

본문바로가기

닫기

지금 바로
로그인해보세요

로그인 하기

로그인 하면 내가 찜한 문제와 수행 평가를 한곳에서 볼 수 있어요!