며칠 전 서울대 에타에 올라온 신기한 숫자 배열
1 ~ 32 까지 중복 없는 원형 숫자 배열에서 인접한 두 숫자를 더하면 항상 제곱수가 된다고 한다
여기서 제곱수란 4, 9, 16, 25, 49, ... 인 숫자로 자기 자신과 자기 자신을 곱해 얻을 수 있는 숫자이다. (2*2 = 4, 3*3 = 9, 4*4 = 16, ...)
보는 사람마다 감탄을 자아내게 만드는 이러한 신통방통한 숫자 배열을 도대체 어떻게 만들 수 있는걸까?
이 숫자 배열을 찾는 방법은 그래프 이론과 관련이 있다
싱붕이의 빠른 이해의 위해 예시를 들어보자
위 그림처럼 그림판을 켜고 1 ~ 16 까지 숫자를 적는다 (위 그림은 일부만 그림)
그 후 1 ~ 16 까지 숫자들 중 두 개의 숫자를 선택하고 더하자. 예로 1과 3를 선택하고 둘을 더하면 제곱수 4가 나온다.
더했을 때 제곱수가 나온다면 두 숫자 사이에 선을 그어 이어주고 (중요)
2 + 3 = 5 같이 더했을 때 제곱수가 나오지 않는다면 아무것도 하지 말자
이 짓거리를 뽑을 수 있는 모든 두 숫자에 대해 해주자
(악수 횟수 구글 검색, 출처: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=pascal_edu&logNo=162026349)
눈치빠른 싱붕이는 두 개의 숫자를 뽑는 방식이
초등학생 시절 치를 떨게했던 수학익힘책의 생각하는 방법 찾기 - 악수 횟수 문제와 같다는 걸 눈치챘을 것이다
모든 숫자쌍을 뽑아서 이 짓거리를 해준다면 어떤 그림이 나오냐면
위와 같은 오묘한 그림이 하나 툭 튀어나온다
거의 다왔다. 이제 싱붕이가 할 일은 한 숫자를 출발점으로 하여 연결된 선을 타고 삥 둘러서 모든 숫자 찍고 다시 출발점으로 오는 경로를 찾으면 된다!
경로를 찾았다면 경로를 따라 원형으로 숫자를 적어주면 싱붕이도 서울대 문제의 원리를 완벽히 이해한 셈이다!
이러한 경로를 그래프 이론에선 해밀턴 경로(Hamiltonian path)라고 부른다
즉 해밀턴 경로는 고향에서 출발해 전국팔도 전부 찍고 다시 고향으로 돌아오는 경로이다
위 그림의 빨간선을 따라가다보면 모든 점을 찍고 다시 시작 위치로 돌아온다
다시 원래 그림으로 돌아오자
경로를 찾으려고 봤더니 그림에 문제가 있다. 모든 숫자를 찍고 출발점으로 다시 돌아오는 경로가 없다!
눈 씼고 찾아봐도 그런 경로가 없다!!!
[1, 3, 6, 10, 15] 같은 작은 경로는 있지만 모든 숫자를 찍는 경로가 없다....
즉 1 ~ 16 까지 숫자를 쓴 것 만으론 모든 점을 찍고 돌아오는 경로가 없다
실망한 싱붕이가 있을지도 모른다. 하지만 숫자는 신의 영역이고 인간이 어찌할 수 없는 법...
신의 영역을 관찰한 싱붕이. 관찰을 통해 다음과 같은 사실을 알아낸다
관찰 1: 1 ~ 16 에 대해서 모든 점을 찍고 돌아오는 경로가 없다
관찰을 더 열심히 한다면 16 뿐만 아니라 더 나아가 31 이하의 모든 숫자에 대해서도 그러한 경로가 없다는 사실을 알 수 있다
관찰 2: 1 ~ k, k = 1, 2, 3, ... 31 에 대해서 모든 점을 찍고 돌아오는 경로가 없다
즉 1 ~ 17 도 없고 1 ~ 27 도 없고 1 ~ 31 도 그러한 경로는 없다
낌새를 눈치 챈 싱붕이는 위 사실이 31에서 멈췄다는 점에 물음표를 던질 것이다
반대로 생각해보면 1 ~ 32 까지 그리면 뭔가가 나온다는 말 아닐까?
1 ~ 32 까지 1 ~ 16 그림을 그렸던 것과 같은 방식으로 그림을 그려보자
32 까지 그렸더니 뭔가 둥근 그림이 나왔다
이제 할 일은 위 그림에서 한 숫자에서 시작해 선을 타며 모든 숫자 찍고 다시 출발 숫자로 돌아오는 경로를 찾는 일이다
놀랍게도 위 그림에서 그러한 경로가 존재한다!
그 경로는 맨 처음 서울대 짤에서 본 원형 숫자 배열이며 다시 써보면 아래 숫자 배열을 원형으로 쓴 것과 같다
[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
의심많은 싱붕이는 그림 상에서 위 숫자들을 따라가며 진짜 그런지 확인해보자
이상으로 숫자 배열을 만드는 원리를 알아보았다
한편, 아직 싱붕이의 궁금증을 해결하기엔 부족하다
위 그림을 보아하니 설마 경로가 저거 하나 밖에 없을까? 저게 끝일까하는 궁금증이 든다
뭔가 요리조리 잘 따라가다보면 다른 경로가 있지 않을까?
이 궁금증을 풀어보자
1 ~ 32 까지 그린 건 좋았는데 다른 경로를 찾기에 뭔가 그림도 크고 사람이 하기에 어려워 보이고
무엇보다 싱붕이는 너무 바쁘다
언제까지나 저 경로만 찾을 수도 없는 노릇
사람 손으로 할 수가 없다는 문제가 생긴다
사람 손으로 못한다??
-> 사람은 못한다??
-> 사람 못해
-> 누가 대신 해줬으면
-> 누가?
-> 충실한 노예가
-> 충실한 노예?? 컴퓨터??
-> 컴퓨터에게 시키면 딱이겠네!
그렇다! 이제 충실한 노예 구원투수 컴퓨터가 등판한다!
1 ~ 32 에 대해 다른 경로를 찾으라고 컴퓨터에게 시켜보자
???
싱붕이는 싱벙갤과 디씨는 잘하지만 컴퓨터와 인연이 없다는 치명적인 매력을 가지고 있었다...
참으로 슬픈 일이 아닐 수 없다
정녕 도대체 방법은 없는 것인가..?
생각하자... 생각하자...
다른 방법... 다른 방법...
아! "해줘"!
그래서 대신 "해줬다"
Building...
TTUG (뚝)
TTAG (딱)
TTUG (뚝)
TTAG (딱)
Ok.
Ok. It's <Done>!
짜 잔
스크롤 내리는 동안 순식간에 프로그램이 만들어졌다!
만들어서 돌려보면 놀랍게도 아래 경로가 하나 더 존재한다고 한다!
[1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 20, 29, 7, 18, 31, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8]
이걸 원처럼 그리면
위 처럼 나온다
의심 많은 싱붕이는 직접 확인해보자
이제 원리를 파악한 싱붕이들은 서울대 유희에 속수무책으로 당하지 않을 것이다
끝
(추가)
참고로 1 ~ 32 뿐만 아니라 1 ~ 33 도 되고 34도 되고 35도 되고 추측컨데 32 이상이면 다 되는 것 같다
1 ~ 33 의 경우를 그려보면
위 그림처럼 나오고 가능한 모든 경로는 다음 두 개 뿐이다
[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 20, 29, 7, 18, 31, 33, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
[1, 15, 10, 26, 23, 2, 14, 22, 27, 9, 16, 33, 31, 18, 7, 29, 20, 5, 11, 25, 24, 12, 13, 3, 6, 30, 19, 17, 32, 4, 21, 28, 8]
이와 비슷한 문제로 knight tour 등이 있다
일반적으로 해밀턴 경로를 찾는 문제는 세계 최대 난제이다
콤푸터에 조예가 깊은 싱붕이라면 아래가 이 글 쓰면서 적당히 만든 프로그램이니 참고해보자
? 그래프이론이 왜나옴
걍숫자쌍 존나찾는건데 그래프이론이왜나오냐고
으휴 멍청한 새끼 - dc App
십새끼가 개노잼인데 스크롤만 좆나 스압이네
밀레니엄 문제에 들어갈만한 난제임?
이건 그냥 풀기어려운 문제지 이미 풀수있으니까 밀레니엄문제는 아님
난제라길래 못푸는 문제인줄
해밀턴 경로를 구하는 문제는 NP-완전 문제인제 쉽게 말하면 저 점 하나가 늘어날 때마다 푸는데 걸리는 시간이 기하급수적으로 늘어난다는 말임. 그리고 밀레니엄 문제에 들어갈만한 난제냐는 질문에 어느정도 그렇다라고 말할 수 있는데 쉽게 말하면 모든 어려운 문제(해밀턴 경로 문제 처럼)를 쉬운 문제로 변환할 수 있는가? 라는 문제는 밀레니엄 문제에 있음
즉 해밀턴 경로 문제를 존나 빨리 풀 수 있게 변환할 수 있는 방법을 찾으면 밀레니엄 문제를 하나 풀 수 있음
디씨에서 어려운말 쓰지마 씨발아 - dc App
중간까지 보고 내렸다
와 개신기하네
임마 어디서 일함? 러스트 쓰는사람 첨보노! - dc App
이거보고 홍성대 슨상님 찾아뵈러 출발한다
애미씨발년들아 뭐라는거야
다른경로를 찾은게 아니고 걍 반시계방향으로 적은거 아니냐 숫자 순서가 똑같은데
ㄹㅇ
뭐라는거야 씨발아
우리게이 왜이리 화났노 ㅋㅋㅋㅋ진정해라 이기
이런거 몰라도 사는데 아무 문제 없다 이 급식들아 끌끌
방구석에서 밥만 먹고 딸만쳐도 사는데 지장 없다. 끌끌. - dc App
끌끌이 뭐임
냠냠. 냠.. 원래 못생긴 쓰울대 애들은 저딴거에 흥분하는게 당연. 냠냠. 냠냠냠. 냠..
열등감 안타깝노...
난 영양제 정보가 더 흥분됨
내 추천 누가 훔쳐갔노
이건 또 뭐야 ㅋㅋ
이게 뭔 개소리냐?
이거 대팍 츠쿠요미 공부법 아님?
섹스
이거 근첩단언데 ㅋㅋㅋㅋ - dc App
하필 왜 32에서 왜 되는건지 설명해주라구
아이 그 이유인 즉 31은 작기 때문이다...
숫자를 읽기가 힘들군 - dc App
왤캐똑똑함?
중간까지 읽다 그냥 내리고 개추 눌렀다
해당 댓글은 삭제되었습니다.
임마 러폭도였노 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 하여간 러스트 쓰는 새끼들중에 머리 나쁜 새끼는 한명도 못봤네
중간중간 나오는 짤들이 웃기네ㅋㅋ - dc App
퐁퐁이가 600만원 손해
http://oeis.org/A090461
결론 존나 많은 조합중에 저게 되는걸 어떻게든 찾아서 적으면 된다는 뜻
니 인생도 마찬가지임. 그 수많은 선택중 니가 당장 무엇을 할지 제대로 결정만하면 성공할 수 있음. 너는 dc하는 결정을 냈으니 인생을 조진거고
내가 머 글을 공격한것도 아닌데 갑자기 쳐 때리려하네
시발 ㅋㅋㅋㅋ왜 난데없이 때리려고하노 ㅋㅋㅋㅋ
근데 왜 갤로그 잠궈놨어 구경좀 할랬더니
에라이 시발 숫자박이 새끼들아
하버드 학생들도 이쁜여자와 야스할때 흥분을 느낀다던데 서울대생들은 멍청해서 그런가 이상한거에 흥분을 느끼네 ㅠㅠ
그래서 이건 어디어디에 쓸모있는건데
저거 자체는 ㄹㅇ 쓸모 1도 없고 저게 나오게 된 계기에 쓸모가 ㅈㄴ 많았던가 그럼 - dc App
설대생들도 대부분 공부하는거 싫어하던데 인터넷서만 저런거 보고 흥분된다고 존나 신이 내린 천재인척함ㅋㅋㅋ
그래서 님 서울대임?
ㅇㅇ
열등감보소
뭐라는거야 씨발년아
시발ㅋㅋㅋㅋㅋㅋㅋ우리게이 왜이리 화났노 ㅋㅋㅋ
서울대 시발련들 - dc App
비슷한 맥락에서 나온 수학 난제로 소련 놈들이 미국 수학을 망하게 하려고 일부러 만든 거란 농담 나오는 게 있었는데 뭐더라... 생산성 1도 없는 주제에 ㅈㄴ 궁금하기만 한 난제... - dc App
러스트충 뭐노 싸대기 마렵네
그래프(좌표x), 해밀턴 경로 이거 틀딱 수능 선택과목 이산수학에 있던 내용 아니냐
서울대는 이런 걸로 느끼노 ㅋㅋㅋㅋㅋㅋㅋㅋ
러스트 붐은 온다 - dc App
왜 32부터 됨?
31까지는 제곱수들의 합으로 나타낼 수 없나
그래서 철구보다 돈 잘범?
병신 ㅋㅋ 프로그래밍 좀 제대로 배웠으면 누구나 저런건 풀 수 있다 근데 그건 이런게 가능한걸 아니까 하는거지 저런 생각을 해낸게 대단한거지 아니면 뭔가 다른걸 하다가 우연히 찾은걸텐데 그게 진짜 재능이야 - dc App
러스트조아
넌뭐야!!
해밀턴이랑 a*알고리즘 코딩쓴거 기억나노
말하는거 진짜..어휴... - dc App
설공나왔는데 이해못함
그래서 저거보고 딸 어케 잡노
저거 손으로도 푸는법 있음. 두 수의 합으로 나올수 있는 수는 63까지. 근데 제곱이어야하니 49가 최대. 25-32 범위의 수는 옆의것과 더해서 36또는 49가 나와야함. 양변은 중앙의 것과 더해서 36또는 49가 나오는것들. 그렇게하면 3개 숫자의 조합 8개를 알 수 있음. 그런데 30조합은 6과 19로 이루어져 있음. 그 숫자는 위의 - dc App
조합과 중복되는것. 거기서 조합이 이어져서 6개연속 숫자가 됨. 중앙에 18이 오는 조합은 25,49가 될 수 있음. 36은 18이 하나 더 올 수 없으니까. 고로 이것도 먹고 들어가는거고. - dc App
이런식으로 조합들을 이어붙이면 결국 끝까지 숫자가 이어지게 할 수 있음. 짝수 제곱들은 그 절반의 숫자가 중앙에 오면 그 짝수 제곱이 될 수 없다는걸 이용하면 빠르게 품. 같은 숫자가 두 번 올 수 없으니까. - dc App
흥분은 지랄 지식적 우월감 느끼려고 비틱질 하는거 개토나오네 씹새끼들
ㅋㅋㅋㅋㅋ 바보병신아다찐따 발견~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
네다음지잡
그래서 씨발 왜 32부터 되냐고 그걸 알려줘야지
그 게 뭔데 씹덕년아
뭔소리고 "알렉산더왕식 해결" 마렵네
디시에 올라오기에는 너무 학술적 가치가 높다...
햐 그래프이론 진짜 오랜만에 보네..우리 싱붕이는 꼭 좋은 직장 가라
놀부 형수님 저 흥분데요 ♡
와 존나 신기하긴 하네 ㅋㅋㅋㅋㅋ 이런 거 보면 수학과 왜 가는 지 조금 알 거 같더라
개신기하네
존나멋있다 와..너 천재임?
존나 멋져
별 장애인새끼 다보네 ㅋㅋ
오우 - dc App