폴리매스

흠...그러면 이 8x8 배열에서 1개를 뺀 그 모양에 있어서 한바퀴 다 돌고 자기 자신한테 올 수 있다면 어느 지점에서든지 가능하다는 것이 된다는 것일 가능성이 있겠군요

아니면 이게 무한평면이니까 다른 8x8을 침범하고 그 침범한 부분만큼은 계속 안 채우는 방법도 있지 않을까요?

예를 들어 아래 그림(8x9)에서와 같이 아래쪽의 큰 X는 문제에서 준 빈칸이고 위의 두 칸은 아래에서 채우니까 퍼즐 맞추듯이 계속 진행할수 있지 않나요?

저 방법이 불가능한 것도 밑에 나온 방법으로 보일 수 있겠네요, (검은 칸 흰 칸 비교하면)

더 정확하게는 '64개의 칸으로 이루어진 테셀레이션 배열에서 나이트는 임의의 한칸을 제외하고 모든 정사각형을 다 지나고 합동인 모양에서의 같은 위치로 이동할수 있다'인 듯 해요.

그것만으로는 부족한 것 같아요. 계속 한 방향으로만 이동하면 안 되고 회오리 모양으로 체스판들을 채워나가야 전체를 채울 수 있을 거예요.

그러면 ssamktwon님의 말씀을 바탕으로 다시 세워보면 한 테셀레이션에서 1개를 제외한 모든 정사각형을 지난 뒤 위,아래,양 옆 중 그 어떠한 다른 테셀레이션이던지 이동이 가능하다는 것인가요??

그런 것 같은데요..

폴리매스 프로젝트에 기하 문제도 많이 나왔었습니다. 예를 들어 국가수리과학연구소 10번 문제인, 몇 개나 들어갈까?가 있ᅌᅥ요. 기하 문제를 풀고 싶으면 그거 한 번 도전해보세요. 이미 풀린 문제지만요.

2번 문제도 있어요.....사각형 채우기 문제인데 해답이 아직 나오지 않았습니다!

여기서는 한체스판을 다채우고 가는게 아니라 다른체스판으로 넘어가면서 채워야 할것같습니다.

w.l.o.g.

흰색이 빈칸이라 하자.흰 칸이 검은 칸보다 딱 1칸 더 많으므로

흰-검-흰-검...-흰으로 테셀레이션을 채울 수 있다면 거기서 다른 판의 흰색으로 이동하면 되므로 증명이 약간 보완이 필요할 것 같아요.

cf)체스판끼리는 모두 다 같은 체스판(흰색은 흰색끼리 붙여놓는 경우)

흰색과 검은색은 증명을 위해 제가 칠한 것이지, 실제 체스판처럼 색이 칠해져 있는 걸 이어 붙인 것이 아닙니다. 원래 체스판을 생각하지 말고 저 무한평면에 검은색과 흰색을 번갈아 칠했다고 생각하십시오.

근데 체스판이 무한해서 저런 논리를 쓰기 힘들 것 같습니다. 게다가 흰색판이랑 검은 판이 1대1 대응을 할 수 있기에 더더욱...

구머님 잘 이해가 안 되는데 흰색 판과 검은색 판이 1대1 대응한다는 게 무슨 뜻이죠?

한 칸 한 칸을 말하시는 건가요?

네네

수가 같지 않은데 어떻게 1대1 대응을 하죠?

어차피 검은 칸이나 흰 칸이나 자연수 집합에 대응을 시킬 수 있으니...

무한 집합 2개는 1대1 대응한다는 거군요......

그게 100프로 성립하진 않지만(ex무리수의 집합은 자연수와 1대1 대응을 못 시키죠!), 보통은 그게 성립하는 것 같습니다. 하지만 충분히 확장을 시킬 수 있을 것 같은 좋은 아이디어네요, 감사합니다.

 검정, 하양의 둘의 기수가 같습니다.

여백 패르마님 흰 색과 검은 색 수가 어떻게 같아요

둘 다 무한히 크고 1대1 대응이 가능할 수도 있지만 무한에도 크기가 있어요. 예를 들어 는  이지만 답은 입니다. 흰 색과 검은 색 칸은 둘다 무한히 크지만 수는 다르다고 할 수 있습니다.

개수X기수O  

아 잘못 쓰신 게 아니었구나..... 죄송합니다.

기수는 농도하고 같은 뜻입니다.

저는 기사가 여행하는 것이 불가능할 것 같은 생각이 듭니다. 저는 불가능하다고 가정하고 풀어보겠습니다. 다른 분들은 가능하다고 하고 풀어주세요. 가능할 수도 있으니까요.

불가능한 거 맞는 듯 해요.

A4용지 반 팩정도 노가다 했는데 한바퀴 못돌아요

의 체스판에 갈 수 있는 경로를 먼저 봐야겠습니다. 

그리고 체스판  에서 위 두 줄, 오른쪽 두줄, 줄에서 멈출 수 있어야 가능합니다.

여백 패르마님 그 방식으로는 못 풀어요.... 검은 색 판과 흰색 판의 수가 다르기 때문에 유한한 크기의 체스판에서는 불가능합니다. 즉, 체스판을 모두 채운 후 다른 체스판으로 넘어가는 방식은 불가능한 방법입니다

무한하다고 해서 꼭 불가능한 것은 아닙니다. 정의를 하는 게 좀 까다로울 수는 있습니다만, 무한에서의 기사의 여행은 다음과 같이 명확하게 정의할 수 있습니다.

"자연수 집합에서 '불완전한 무한 체스판'의 각 칸으로 가는 일대일 대응이 존재하여, 이웃한 자연수에 대응되는 체스판의 칸이 나이트가 한 번에 이동할 수 있는 위치 관계에 있다."

기사가 무한히 여행을 한다 했으므로 될 수 있습니다.

방법은 좋지만 해밀턴 경로를 찾는 방법은 아직 정의되지 않아서....... 힘들 것 같네요.

https://ko.wikipedia.org/wiki/%ED%95%B4%EB%B0%80%ED%84%B4_%EA%B2%BD%EB%A1%9C

해밀턴 경로를 찾아보니 그 예시로 기사의 여행이 나오네요.

이를 참고해 보면 좋을 듯 합니다.

오레의 정리라는 해밀턴 경로의 필요조건을 보고 한번 대입해보려고 했지만 실패했습니다. 임의의 인접하지 않은 점 u,v에 대하여 이면 해밀턴 경로라는 것인데, 이고, 이기 때문에, 네.... 볼 것도 없군요. 하지만, 충분조건이 아닌 필요조건이니 기사의 여행이 불가능하다는 뜻은 아닙니다. 디랙의 정리라는 필요조건도 역시 마찬가지입니다.

최단경로찾기 문제말씀하시는것 같은데...

이런식으로 하면 될것같긴합니다만...

아니죠 오른쪽 왼쪽 위 아래 모두 무한합니다 왼쪽 오른쪽에도 빈 공간을 놓아야죠

그리고, 제 생각에는 거리 값이 무한대이면 갈 수 있는 경로가 두 가지 이상인 것 같습니다. 즉, 갔다가 돌아올 수 있는 길이 있다는 겁니다. 그러면, 갈 수 있는 칸 중

1. 현재 칸보다 거리 값이 1 큰 칸으로 가는 시행을 무한히 합니다.

2.그런 다음, 거리 값이 1 작은 칸으로 가는 시행을 다시 무한히 해서 거리 값이 1인 다른 칸으로 이동합니다.

3. 같은 시행을 반복하다 거리 값이 1인 칸이 없어지면 2번 시행을 거리 값이 2인 칸으로 이동하는 것으로 바꿉니다

4. 같은 시행을 반복하다 거리 값이 k인 칸이 없어지면 2번 시행을 거리 값이 k+1인 칸으로 이동하는 것으로 바꿉니다.

5. 무한히 반복합니다.

이렇게 하면 모든 칸을 기사가 여행할 수 있지 않을까요?

제가 이해를 못한 것 같은데 "1. 현재 칸보다 거리 값이 1 큰 칸으로 가는 시행을 무한히 합니다."가 무슨 뜻이죠? 무한히 하면 무한한 시간이 걸릴텐데 2단계는 언제 하나요?

글쎄요... 그냥 제 아이디어를 말해본 것입니다.

그런데, 무한히 많이 어딘가로 갔다가 오는 시행을 하지 않는다면, 아무리 커도 유한한 공간을 왔다갔다하는 것입니다. 그러면 제가 앞에서 말했듯이, 검은 색 칸과 흰 색 칸의 개수가 1대1 대응을 하지 않기 때문에, 어떤 방법이든 어떤 시행을 무한히 반복했다 다시 다른 시행을 무한히 반복하는 것을 해야 하지 않을까요?

개수도 일대일 대응을 합니다. 사실 무리수와 유리수의 개수는 일대일 대응을 못하겠지만, 모든 가산 무한은 크기가 같고 무한*3=무한이기때문에 전에 수학장 님이 말하신 극한으로는 절대로 크기를 비교할 수 없습니다. 

아 그건 압니다. 제가 방금 검은 색 칸과 흰 색 칸이 일대일 하지 않는다고 한 건

아무리 커도 유한한, 즉 매우 크지만 무한하지 않은 평면에서 그렇다고 한 겁니다. 제가 앞서 말한 시행처럼 시행1 무한히 많이 했다가, 다시 다른 시행2를 무한히 하는 경우가 아니라면 매우 크지만 무한하지 않은 평면에서 계속 도는 것이 아니냐고 말한 겁니다.

ssamtkwon님이 제가 말한 거리 값이 1 큰 칸으로 이동하는 시행을 무한히 많이 하면 시간이 무한히 걸릴 텐데, 2번 시행은 언제 하냐고 물으셨길래, 제가 1번 시행을 유한하지만 매우 많이 한다 하더라도, 그렇게 하면 유한하기 때문에 검은 색 칸과 흰 색 칸이 1대1 대응을 하지 않을 것이라고 대답한 것입니다.

그리고, 방금 생각났는데, ssamtkwon님이 말씀하신 의견을 받아들여 이렇게 귀납적으로 정의해봅시다.

1. 현재 칸보다 거리 값이 1큰 칸으로 가는 시행을 거리 값이 n이 될 때까지 합니다.

2. 그런 다음 거리 값이 1 작은 칸으로 가는 시행을 계속 해서 거리 값이 1인 다른 칸으로 이동합니다.

3. 1, 2번 시행을 반복하다 거리 값이 1인 다른 칸이 없어지면, 1번과 2번을 각각 이렇게 바꿉니다.

-현재 칸보다 거리 값이 1 큰 칸으로 가는 시행을 거리 값이 n+1이 될 때까지 합니다.

-그런 다음 거리 값이 1 작은 칸으로 가는 시행을 계속 해서 거리 값이 2인 다른 칸으로 이동합니다.

4. 1,2번 시행을 반복하다 거리 값이 k인 칸이 없어지면, 1번과 2번을 각각 이렇게 바꿉니다.

-현재 칸보다 거리 값이 1 큰 칸으로 가는 시행을 거리 값이 k+n+2가 될 때까지 합니다.

-그런 다음 거리 값이 1 작은 칸으로 가는 시행을 계속 해서 거리 값이 k+1인 다른 칸으로 이동합니다.

어떤 n이 존재하여, 이런 시행을 반복하면 모든 칸을 여행할 수 있을 지도.... 증명은 못 했습니다.

이거 확인 부탁드림니다.

연구원님께서 '불완전한 체스판'의 경우 검은 칸과 흰 칸의 수가 무한하기 때문에, 칸 수의 차를 쉽게 얘기할 수 없다는 의견을 주셨어요! 위에 달린 댓글을 보면 친구들도 이와 관련해서 활발하게 논의하고 있으니, 의견을 보태주세요!!

아 그렇군요..

ㅋㅋㅋㅋㅋㅋㅋㅋ 글쎄요 이게 체스판의 크기가 무한하다 보니 그런 패턴으로 될까요?

Simon 친구의 열정에 감탄하고 갑니다..!!

(짝수,짝수)와 (홀수,홀수)인 경우를 경우A

(짝수,홀수)와 (홀수,짝수)인경우를 경우B라고 하면

A-B-A-B-A-B가 반복되는데

B와 A는 개수가 다르니까 B가 모자를것 같아요

그런 의견은 전에도 있었으나, 안타깝지만 체스판의 크기가 무한하기 때문에 그렇게 단정지을 수는 없다고 결론이 나왔습니다. 그 의견을 사용하려면 좀 더 엄밀한 증명이 필요할 것 같습니다. 자연수 집합과 짝수 집합이 일대일 대응하듯이 무한집합은 크기가 달라도 일대일대응할 수 있기 때문입니다

그런데 혹시 그거 아세요? 불완전한 체스판 4개를 이었을 때는 검은색과 흰색의 개수가 다르기 때문에 여행이 불가능하답니다.(와!!!)

네, 그런 규칙은 유한에서만 적용될 거 같네요. 위의 댓글에도 나와 있지만 두 칸의 수의 차를 쉽게 예기할 수 없어서...

흰색 칸과 검은 색 칸의 개수가 모두 가산무한이기 때문에 무한에서는 적용시킬 수 없습니다.

한붓그리기와는 다르네요.

죄송합니다. 앞에서 나온 아이디어 였네요

체스판이 유한이라면 불가능합니다. 그런디 무한이라면 어떨지 잘 모르겠네요.

궁금한점이 있는데,이게 성립한다고 해도(개수가 같아도) 결국 바깥에 두줄에 있는 검은색칸의 개수가 남게 되니까 결국 일대일대응이 안된다는 소리 아닌가요??

그리고 그냥 궁금한건데 일대일대응이 안되니까 체스판의 개수가 유한할때 기사의 여행은 불가능하다의 대우로 기사의 여행은 가능하다 체스판의 개수가 무한할때라고 보면 안되나요???

명답이네요ㄷㄷ 일단 제 생각에는 풀이에 별다른 오류가 없는 것 같습니다. 미리 축하드려요!

제 설명이 무한을 개수로 비교하려 하던 오류와 비슷하다는 의견이 있어 설명을 보충하도록 하겠습니다.

무한히 큰 체스판을 채우려면 무한한 움직임 끝에 모든 칸 중 기사가 가지 못한 칸이 하나도 없어야 합니다. 또한 체스판들로 이루어진 일정 부분(A) 안에 이렇게 가지 못한 곳이 하나도 없기 위해서는 흰 칸과 검은 칸의 차만큼 일정 부분에서 나갔다가 들어오는 과정이 있어야 하죠. 그러려면 일정 부분이라고 한 곳을 두르고 있는 외부 둘레(B)를 그만큼 지나야 합니다. 즉 최소한 흰 칸과 검은 칸의 차만큼은 B의 검은 칸을 지나가야 하는데, A가 체스판을 n×n개 포함한 정사각형 모양일 때 흰 칸과 검은 칸의 차는 n^2에 비례하지만, B의 검은 칸의 개수는 n에 대한 일차함수로 나타나므로 언젠가는 개수의 차가 둘레의 검은 칸의 수보다 커지게 되어 A 안에 기사가 가지 못한 곳이 생깁니다. 저는 그 예로 A가 체스판을 33×33개 가진 정사각형일 때를 보였습니다.

또한 풀이에서 A에는 흰 칸이 검은 칸보다 많으므로 검은 칸이 아닌 흰 칸에서 나가 흰 칸으로 들어와야 합니다. 그러면 B의 검은 칸을 밟아야 하는데, 이 부분이 제 풀이의 오류였습니다. 하지만 B의 흰 칸과 검은 칸의 개수가 같으므로 이후 풀이에는 문제가 없습니다. 글을 수정할 수 없어 이렇게 정정하도록 하겠습니다.

정답입니다! 확인 버튼에 오류가 있어서 수정되는대로 조치할게요!

17세대가 나오는 k의 존재성을 밝히는 과정에서, 경로가 칸이 늘어나는것에 비해 더 많이 늘어난다는 설명이 더 정확할 것 같네요.

이 설명이 아니면 수렴할 가능성을 배제하지 못해서 오류가 발생하네요.

세대라는 가정을 한것은 좋은것 같습니다. 다만 저는 이게 일대일대응이 안된다는 사실이랑 다른점을 찾기 어려움이 있네요 조금만 더 풀이를 자세히 해주힌다면 감사하겠습니다 

단순히 일대일대응으로만 보는것이 아니라 각각의 체스판에서의 일대일 대응을 이루는 과정이 불가능하다는 것을 밝힌 것입니다. 파스칼님 풀이도 마찬가지입니다. #한발늦었다 ㅠㅠㅠㅠ

김다인 멘토의 검토 결과.. 17세대가 나타난다는 증명이 명확하지 않다고 합니다~!

아 착오가 있었나보네요 파스칼 님이 맞다는 거에요

그리고 저 풀이는 p: "기사의 여행이 가능하다"->q: "체스판이 무한하다"의 논리에서(이건 성립하는 명제) q->p 또한 성립한다고 말하는 것과 같기 때문에 오류가 발생합니다.

논리의 과정은 이렇습니다.

검은색칸과 흰색칸은 둘다 무한하므로 일대일대응이다.

그런데, 각각의 판을 기준으로 보니 하나의 검은 칸이 부족한건 사실이라, 그 판을 채우기 위해서는 다른 판의 검은 칸을 밟아야 한다.

문제는 이렇게 바뀐다. '다른판에서 검은 칸을 뺏어오는 과정이 계속될수있는가'

이걸 푼거죠

그 부분은 애초에 생각할 필요가 없는게 만약 기사의 여행이 가능하다면, "순서와 상관없이" 저 정사각형 모양 내의 칸들을 체스말이 다 들러야하는데, 그것이 불가능하다는 것을 파스칼 님이 잘 보여줬고, 따라서 추가적인 설명이 필요하지 않습니다.

잠시 착각했네요.

변형시킨 순서대로 표를 정리했습니다.

혹시나 오류를 찾으시면 꼭 알려주시기 바랍니다. 

위에 파스칼님은 불가능하다고 하네요

8*8-1 체스판에서 기사의 여행이 가능하긴 하지만 문제는 그 형태의 체스판을 무한히 연결한 형태라 님이 제시한 방법으로는 할 수 없을 것 같네요

김다인 멘토가 검토한 결과  8*8-1에서 문제가 만족한다고 해서 무한 체스판에서도 만족하는 것이 아니라는 의견을 줬어요~!