오늘은 「조합을 세는 법」에 대해서 공부해볼까!

이 사각형에서 스타트 지점부터 골인 지점까지 가는 방법은 몇 개가 있을지 알겠니?






그럼 2개로 분할해서 2X2일 때는 몇 가지 방법으로 갈 수 있을까?

이런 식으로 12가지 방법이 있습니다.

그럼 여기서 더 분할해서 3X3일 때

자, 이것처럼 184패턴이야!






더욱 분할해서 4X4일 때

8512더라고!







다음은 5X5일 때

뽀미언니는 이제 직접하기 힘드니까, 컴퓨터로 계산하겠습니다

자, 나왔네요!126만 2816 패턴!

6X6일 때는, 5억 7578만 564패턴! 굉장하네!

자, 다음은 7X7! 이라고 하고 싶지만, 이 컴퓨터로 계산하면 엄청 시간이 걸리게 되니

슈퍼컴퓨터를 가지고 왔습니다!

나왔어요! 7893억 6005만 3252 패턴!

다음은 8X8! 부탁할게! 슈퍼컴퓨터!

4시간 경과

다들 일어나렴! 3266조 5984억 8698만 1642 패턴이야!





자아! 다음은 9X9야!

아까는 4시간 정도 걸렸으니까, 이번엔 2, 3일은 걸릴 지도 모르겠네

오늘은 외박해야겠는 걸?






6년 경과





뽀미언니다

결과가 나왔어! 어서 오렴!

다들 나이를 먹었구나! 자아, 수업을 시작할게!

뽀미언니...

9X9일 땐 이럴수가! 4104경 4208조 7026억 3249만 6804 패턴! 현기증이 날 정도네!





자아, 다음은 10X10이야!





8X8은 계산에 4시간 반이 걸렸고, 9X9인 이번엔 6년 반이 걸렸어요!

10X10 같은 걸 계산하면

뽀미언니가 죽어버려! 하지 마요!










......알고 있단다

네...?

그래도 말야. 난 모두에게 「조합 폭발의 굉장함」을 알려주고 싶어! 말리지 마렴!

뽀미언니!!!!

언니!!!!








그 이후 25만년이 흘렀다...









드디어, 나왔어

10X10일 때는 1자 5687해 5803경 0464조 7500억 1321만 4100만 패턴!

아이들의 자손에게 연락해야지

아, 얘들아, 뽀미언니 로봇인데 10X10일 땐 말이지!

누구세요! 잘못 거신 전화예요!








자, 다음은, 11X11이야













11X11을 이 스타일로 계산하면, 290억년이 걸립니다. (우주의 나이는 추정 137억년)

하지만 현재 최첨단 알고리즘 기술을 사용하면, 똑같은 문제를 겨우 몇 초만에 알아낼 수 있습니다. 16X16의 문제라도 몇 십 분이면 끝이 나지요.

뽀미언니에게 알려주고 싶다......