주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국23. 순열 품은 수열

2018.10.31

같이 풀어볼까?

네이버밴드 구글플러스

 

국가수리과학연구소의 23번째 문제입니다.

 

 

\large n을 임의의 자연수라 하자. 각 항이 1 이상 n 이하의 자연수 중 하나고 항의 개수는 \large n인 수열 중 모든 수가 한 번씩만 나타나는 수열을 '순열'이라고 한다. 예를 들어 \large n=4일 때 4, 1, 3, 2는 순열이고 1, 4, 3, 1은 순열이 아니다. 이때 순열의 총 가짓수는 \large n!(=\large n×\large n-1×\large n-2×…×\large 1)이다.  
‘부분수열’은 어떤 수열에서 연속되는 일부 항을 골라 만든 수열이다. 예를 들어 1, 4와 4, 3, 2, 4는 수열 1, 4, 3, 2, 4, 1의 부분수열이다.

 

문제

자연수 n이 주어졌을 때, 모든 순열을 부분수열로 가지는 수열의 최소 길이를 구하라. 

 

 

댓글 26

  • 누군가 2018.10.31 20:50:27

    n=1 일때 1

    n=2 일때 121

    n=3 일때 123121321

    n=4 일때 123412314231243121342132413214321

    1,3,9,33

    n=4일때 까지만 해보았습니다. 다 좌우대칭이네요.

    좋아요0 댓글수2
    • 누군가 2018.10.31 21:21:34

      수열의 길이가 최소가 되려면 최대한 앞의 숫자를 써야하니 1~n까지 쓴다음 1~n-1 까지쓰면 배열이 1234...n-1,n인 모든 순열이 포함됩니다.. 그 다음 수는 어떤 것이 와도 앞에 있는 수열과 겹치니 최대한 많은 수를 쓰기위해 두 숫자(1,n)의 위치만 바꿉니다. 2~n-1로 시작하여 1,n으로 끝나는 배열(2,3,4...n-1,1,n)을 씁시다.

      예시로 12345를 들면

      123451234

      여기서 마지막 3자리가 234이므로 원래 앞배치12345에서 1,5에 위치가 바뀐 51234(23451)를 배치로 하는 순열을 모두 포함시킵니다.

      123451  234152341 마지막 3자리가 341이므로 25의 위치만 바꿔 반복합니다.

      123451 234152 341253412 계속 반복하면

      123451 234152 341253 412354123 여기서 123으로 끝나는데 같은 방식으로 하면12345가 되므로 중복됩니다.( n 일때는 두숫자의 위치를 바꾸는 것을 n-1번 반복하면 원래대로 돌아옵니다.(n은 항상 바뀌고))

      최대한 숫자를 적게 써야하니 23으로 시작하는 배치를 하나를 골라해봅니다...(계속반복)

      음... 그냥 규칙을 찾자면

      1=1,3=1+2,9=1+2+6,33=1+2+6+24 에서 모든 순열을 부분수열로 가지는 수열의 최소 길이는 \sum_{k=1}^{n}k!입니다.  왜 그런지는 좀 더 생각을...

       

      (좀 더 정리한 다음 공개하려 비밀댓글로 했는데 그냥 공개합니다.)

      좋아요0
    • 바나나 2018.10.31 22:12:37

      비밀댓글 혹시 답인가요?

      좋아요0
  • muse 2018.11.01 08:05:21

    (1! + 2! + 3! + ... + n!)인가요?

    좋아요0 댓글수13
    • 수학장 2018.11.01 18:33:14

      오 누군가님이 구하신 거랑 일치하네요.. 근데 맞아도 폴리매스가 정답으로 쳐주진 않을 듯... 풀이과정 갖고 오라고 할 것 같음

      좋아요0
    • muse 2018.11.01 18:45:38

      그렇긴 하죠. 일단 답이라도 알면 풀이가 빨라지니까요.

      좋아요0
    • muse 2018.11.01 18:48:41

      아쉽게도 n=6일 때 872짜리 반례가 있습니다.

      1234561234516234512634512364513264513624513642513645213645123465123415 6234152634152364152346152341652341256341253641253461253416253412653412 3564123546123541623541263541236541326543126453162435162431562431652431 6254316245316425314625314265314256314253614253164523146523145623145263 1452361452316453216453126435126431526431256432156423154623154263154236 1542316542315642135642153624153621453621543621534621354621345621346521 3462513462153642156342165342163542163452163425163421564325164325614325 6413256431265432165432615342613542613452613425613426513426153246513246 5312463512463152463125463215463251463254163254613254631245632145632415 6324516324561324563124653214653241653246153264153261453261543265143625 1436521435621435261435216435214635214365124361524361254361245361243561 2436514235614235164235146235142635142365143265413625413652413562413526 41352461352416352413654213654123

       

      (출처: https://oeis.org/A180632)

      좋아요0
    • 수학장 2018.11.01 19:17:39

      872가 1!+2!+3!+4!+5!+6!보다 큰 수인데 1!+2!+3!+4!+5!+6!개의 수로 만들 수 있는 걸 존재하는데 못 찾은 것 아닐까요? 잘 알려지지 않은 문제라 실수가 있을 법도 할 것 같은데(일말의 희망)

      좋아요0
    • muse 2018.11.01 19:20:54

      1!부터 6!까지 더하면 873 아닌가요?

      좋아요0
    • 바나나 2018.11.01 20:40:58

      사진과 같이 계산해본결과 1!+2!+3!+4!+5!+6!=873 이란 결과를 얻었습니다

      좋아요0
    • 바나나 2018.11.01 21:33:31

      하나 더 덧붙이자면 https://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html 라는 경우의 수를 모두 구해주는 사이트를 통해 n=6일 경우를 구해보았습니다

      그 결과는 생략하겠습니다

       

      단 결과중 123564  라는 경우(부분수열)이 872자리의 수열에 포함되지 않음을 발견했습니다

      네이버 글자수 세기를 하면 872자리임을 확인할 수 있었습니다만 사진은 생략합니다

      인터넷창에서 F3 를 눌러 '찾기' 기능을 통해 검색해본 결과 현재 이 문제를 포함한 댓글의 어디에서도 123564 를 찾을 수 없었습니다

      따라서 muse님이 올리신 872자리의 수열은 n=6일때 모든 순열을 부분수열로 가지는 수열, 즉 반례라고 할 수 없습니다

       

      확인하시려면 F3를 눌러 123456 과 123564 를 입력해 비교해보시길 바랍니다

      좋아요0
    • 바나나 2018.11.01 21:41:31

      굳이 결과를 올리자면 총 720개로 아래와 같은 실행값이 나옵니다

       

      Permutations without repetition (n=6, r=6)
      Using Items: 1,2,3,4,5,6

      List has 720 entries.
      123456 123465 123546 123564 123645 123654 124356 124365 124536 124563 124635 124653 125346 125364 125436 125463 125634 125643 126345 126354 126435 126453 126534 126543 132456 132465 132546 132564 132645 132654 134256 134265 134526 134562 134625 134652 135246 135264 135426 135462 135624 135642 136245 136254 136425 136452 136524 136542 142356 142365 142536 142563 142635 142653 143256 143265 143526 143562 143625 143652 145236 145263 145326 145362 145623 145632 146235 146253 146325 146352 146523 146532 152346 152364 152436 152463 152634 152643 153246 153264 153426 153462 153624 153642 154236 154263 154326 154362 154623 154632 156234 156243 156324 156342 156423 156432 162345 162354 162435 162453 162534 162543 163245 163254 163425 163452 163524 163542 164235 164253 164325 164352 164523 164532 165234 165243 165324 165342 165423 165432 213456 213465 213546 213564 213645 213654 214356 214365 214536 214563 214635 214653 215346 215364 215436 215463 215634 215643 216345 216354 216435 216453 216534 216543 231456 231465 231546 231564 231645 231654 234156 234165 234516 234561 234615 234651 235146 235164 235416 235461 235614 235641 236145 236154 236415 236451 236514 236541 241356 241365 241536 241563 241635 241653 243156 243165 243516 243561 243615 243651 245136 245163 245316 245361 245613 245631 246135 246153 246315 246351 246513 246531 251346 251364 251436 251463 251634 251643 253146 253164 253416 253461 253614 253641 254136 254163 254316 254361 254613 254631 256134 256143 256314 256341 256413 256431 261345 261354 261435 261453 261534 261543 263145 263154 263415 263451 263514 263541 264135 264153 264315 264351 264513 264531 265134 265143 265314 265341 265413 265431 312456 312465 312546 312564 312645 312654 314256 314265 314526 314562 314625 314652 315246 315264 315426 315462 315624 315642 316245 316254 316425 316452 316524 316542 321456 321465 321546 321564 321645 321654 324156 324165 324516 324561 324615 324651 325146 325164 325416 325461 325614 325641 326145 326154 326415 326451 326514 326541 341256 341265 341526 341562 341625 341652 342156 342165 342516 342561 342615 342651 345126 345162 345216 345261 345612 345621 346125 346152 346215 346251 346512 346521 351246 351264 351426 351462 351624 351642 352146 352164 352416 352461 352614 352641 354126 354162 354216 354261 354612 354621 356124 356142 356214 356241 356412 356421 361245 361254 361425 361452 361524 361542 362145 362154 362415 362451 362514 362541 364125 364152 364215 364251 364512 364521 365124 365142 365214 365241 365412 365421 412356 412365 412536 412563 412635 412653 413256 413265 413526 413562 413625 413652 415236 415263 415326 415362 415623 415632 416235 416253 416325 416352 416523 416532 421356 421365 421536 421563 421635 421653 423156 423165 423516 423561 423615 423651 425136 425163 425316 425361 425613 425631 426135 426153 426315 426351 426513 426531 431256 431265 431526 431562 431625 431652 432156 432165 432516 432561 432615 432651 435126 435162 435216 435261 435612 435621 436125 436152 436215 436251 436512 436521 451236 451263 451326 451362 451623 451632 452136 452163 452316 452361 452613 452631 453126 453162 453216 453261 453612 453621 456123 456132 456213 456231 456312 456321 461235 461253 461325 461352 461523 461532 462135 462153 462315 462351 462513 462531 463125 463152 463215 463251 463512 463521 465123 465132 465213 465231 465312 465321 512346 512364 512436 512463 512634 512643 513246 513264 513426 513462 513624 513642 514236 514263 514326 514362 514623 514632 516234 516243 516324 516342 516423 516432 521346 521364 521436 521463 521634 521643 523146 523164 523416 523461 523614 523641 524136 524163 524316 524361 524613 524631 526134 526143 526314 526341 526413 526431 531246 531264 531426 531462 531624 531642 532146 532164 532416 532461 532614 532641 534126 534162 534216 534261 534612 534621 536124 536142 536214 536241 536412 536421 541236 541263 541326 541362 541623 541632 542136 542163 542316 542361 542613 542631 543126 543162 543216 543261 543612 543621 546123 546132 546213 546231 546312 546321 561234 561243 561324 561342 561423 561432 562134 562143 562314 562341 562413 562431 563124 563142 563214 563241 563412 563421 564123 564132 564213 564231 564312 564321 612345 612354 612435 612453 612534 612543 613245 613254 613425 613452 613524 613542 614235 614253 614325 614352 614523 614532 615234 615243 615324 615342 615423 615432 621345 621354 621435 621453 621534 621543 623145 623154 623415 623451 623514 623541 624135 624153 624315 624351 624513 624531 625134 625143 625314 625341 625413 625431 631245 631254 631425 631452 631524 631542 632145 632154 632415 632451 632514 632541 634125 634152 634215 634251 634512 634521 635124 635142 635214 635241 635412 635421 641235 641253 641325 641352 641523 641532 642135 642153 642315 642351 642513 642531 643125 643152 643215 643251 643512 643521 645123 645132 645213 645231 645312 645321 651234 651243 651324 651342 651423 651432 652134 652143 652314 652341 652413 652431 653124 653142 653214 653241 653412 653421 654123 654132 654213 654231 654312 654321

      좋아요0
    • 수학장 2018.11.01 22:11:52

      123564 없네요!! 그러면 1!+2!+...+n!이라고 추측할 수 있게 됐어요!!

      좋아요0
    • 바나나 2018.11.01 22:32:19

      아마도 그럴것같습니다

      답이라고 생각되지만 문제는 '증명' 이네요;;

      좋아요0
    • 수학장 2018.11.01 23:00:58

      뭐인지 하나도 모르고 푸는 것보단 알고 증명하는 게 더 쉽죠ㅎㅎ

      좋아요0
    • 누군가 2018.11.02 00:25:35

      123564는 두번째줄 끝과 세번째 줄 처음에 있습니다. 아마 enter 때문에 검색이 안된듯 합니다

      좋아요0
    • 바나나 2018.11.02 01:01:50

      아앗;; 그렇네요;; 그럼 반례일 수 있겠군요... 아니 반례겠네요

      혼동드려서 죄송합니다

      좋아요0
  • muse 2018.11.01 18:46:27

    https://en.wikipedia.org/wiki/Superpermutation

    이 문제네요.

    좋아요1 댓글수1
    • 아인수타인 2018.11.03 00:34:21

      ... 한글로 된 건... 없죠?

      좋아요0
  • 아인수타인 2018.11.23 22:56:24

    요즘 댓글이 영~ 안 달리는 건 기분 탓인가요? (저도 별로 안 달긴 합니다만.)

    좋아요0 댓글수1
    • 프로벤젠 2018.11.28 23:26:03

      두 문제 모두 접근하기가 어려워서 댓글이 적은 것 아닐까요?

      빨리 12월이 왔으면 좋겠네요^^

      좋아요0
  • EulerD 2018.11.29 22:52:53

    수학적 귀납법의 각이 보이는 문제인데요.. 보통 윗분들처럼 컴퓨터를 이용해서 푸는 문제들은 Algorithm을 고안해야 하는 경우가 많은데..

    좋아요0 댓글수3
    • EulerD 2018.11.29 22:56:46

      이런.. Open problem이네요

      일단 1! + 2! + ... + n!인 실예는 찾았는데,

      그게 최소인지는 모르겠네요

      좋아요0
    • EulerD 2018.11.29 22:58:07

      논문 몇개 읽어보니 Graph Theory로 접근하는 경향도 있네요..

      이것도 충분히 고려해야될 듯..

      좋아요0
    • EulerD 2018.11.29 23:04:09

      muse님 말씀대로 일단 1! + .... + n!은 조금 아닐 수 있겠네요.

      OEIS이니 비공식 자료도 아니고..

      좋아요0
  • Fermat314 2019.03.16 00:45:04

    Open Problem이어서 그런건지 이 문제를 파는 분이 별로 없는 것 같네요. 일단 현재까지 제가 알아본 것들을 써서 풀이를 좀 진척시키겠습니다.

    인터넷 등에서는 이 문제를 하루히 문제라고도 부르는 것 같은데, 저는 그냥 초순열이라고 하겠습니다.

     


    우선 n에 대한 초순열의 최소길이를 A(n)이라 하면 현재까지 밝혀진 A(n)과 그 초순열은 다음과 같습니다. 이 중 A(7)은 5907로 알려졌으나 2019년 2월달에 5906으로 기록이 갱신되었습니다.

     

    A(1)=1

    1

     

    A(2)=3

    121

     

    A(3)=9

    123121321

     

    A(4)=33

    123412314231243121342132413214321

     

    A(5)=153

    123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

     

    A(6)=872

    12345612345162345126345123645132645136245136425136452136451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123

     

    A(7)=5906

    12345671234561723456127345612374561327456137245613742561374526137456213745612347561324756134275613472561347526134756213475612345761234516723451627345162374516234751623457162345176234512673451263745126347512634571263451726345127634512367451236475123645712364517236451273645123764512346751234657123465172346512734651243765124367512436571243651724365127436512473651246375124635712463517246351274635124763512467351426735146273514672351467325146735216473521674352167345216374521634752163457216345271634521764352176453271645327614532764153276451326745132647513264571326451732645137264531726453712645372164537261453726415372645132764531276453217645231764521376452173654217365241736521473652174365217346521736452176345216735421637542163574216354721635427163542176354216735241637524163572416352741635247163524176352416735214673512465371246531724653127465312476531246753142675314627531467253146752316475321647531264753162475316427531647253164752316745321674531267453162745316724531674253167452316754231675243167523416752314675321467531246573124651372465132746513247651324671532467135246713254671235467125346712543671524367154236715432675143267541326754312675432167543261745362174536127453617245361742536174523617453261743526174325617432651742365174263517426531742651374265173426157342617534216753421765342175634217536421753462175342617354261734526173425617342651743261574362157436125743162574312657413265741236574126357412653741265734126574312567413256741235674125367412563741256734125674312576413257614325761342576132457613254761325746132576412357641253761425376124537612543761524376154237615432761543726154376215437612534761253746125376412573641257634125764312574631257436152743615724361574236157432617543621754361275436172543617524361754236175432671543627154367215436712546371254673125476312547361524736154273615472361547326145736214576321475632147653214763521476325147632154763214576231457621345762143576214537621457361245736142573614527361457236145732614753621475361247536142753614725361475236147532614735261473256147326514723651472635147265314726513472651437265147326154736215473612547316254731265471326547123654712635471265347126543716253471625374162537146253716425371624537162543716524371654237165432716543721654371265473125647132564712356471253647125634712564372156437251643275614327564132756431275643217564327156432751643257163425176342516734251637425163472516342751634257163245176324516732451637245163274516324751632457163254716325741632571463275146327154632714563271465327146352714632571643527164357216435712643517264351276435126743512647351264375126435716243517624351672435162743516247351624375162435716423517642351674235164723516427351642375146237514263751423675142376514273651427635142765314276513427651432765142375614235761423567143256714352671435627143567214356712435617243561274356124735612437561243576124356714235617423561472356142735614237516423571643251764325167432516473251643725614372564137256431725643712564731254671324567132465713246751324615732461753246173524617325416723541762354716235476123547621354762315467231546273154623715462317564231576421356742135647213564271356421735624137562413576241356724135627413562471356241735621473562174356217345621735462173564213756421357642153746215374261537421653742156374215367421537642157364215763421576432157642315674231564723156427315642371564231756243157624315672431562743156247315624371562431756234157623415672341562734156237415623471562341756231475623174562317546321745632174653217463521746325174632157463217546312754631725463175246315724631527463152476315246731524637152463175426315742631547263154276315426731542637154263175462315746235174623571462357416235746123574621357462315476235147623541726354172365417235641723546172354167253417625314762531746253176425317624531762543176524317654231765432176543127654317265431762534172653417256341725364172534617253416725431672541367251436725134672153476215347261534721653472156347215364721534672135467213456721346572136457213654721365742136572413657214365721346752136475213674521367542136752413675214376521437562143752614375216437521463725146372154637214563721465372146357214637521436752134672513647251367425136724513672541637254167325417632541736251473625174362517346257136425713624571362547136257413625714362571346275136427513624751362745136275416327541623754126375412367541237654132765413726541376251437625134762513746251376425137624513762541376524137654213765412375641237546132754613725461375246137542613754621375461237541627354126735412763541273654127356412735461273541627534126753412765341275634127536412753461275341627543162754136275143627513462715342671354267134526713425671342657143265714236571426357142653714265731426571342675134267153427615342716534271563427153642715346271354627134562713465271364527136542713652471365274136527143652713462573146257341625734612573462157346251736425173624517362541732654173256417325461732456173246517324615372461532746153247615324167532416573214657321645731264573162457316425731645273165427316524731652743165273416527314652731645723165472316574231657243165723416572314657231645732165473216574321657342165732416537241653274165324716532417653241567321456731245637124563172456312745631247563124576312456731425637142563174256314725631427563142576314256731452637145236714532671453627145367214536712453671425367145237614523716452371465237416523746152347651234765213476523147652341765234716523476152346715234617523461572346152734615237465123746521374652317465237145623714526317452631475263145726314527631452673145627314567231456732154673215647321567432156734215673241563724156327415632471563241756324157632415367241536274153624715362417536241573624153762415326741532647153264175326415732641523764152367415236471523641752364157236415273641526374152634715263417526341572634152763415267341526437152643175264315726431527643152674315264731526413752641357261435726134572613547261357426135724613572641352761435276134527613542761352476135274613527641352674135264713526417352641

     


    현재까지 알려진 하한선은 n!+(n-1)!+(n-2)!+n-3로, 아래 링크에 있습니다. 영어라서 그런지 전 아직 이해하지 못했네요.

    https://mathsci.fandom.com/wiki/The_Haruhi_Problem

    https://warosu.org/sci/thread/S3751105#p3751197

     


    일단 상한선이 1!+2!+3!+•••+n!인 것은 쉽게 증명할 수 있습니다. 이에 대해 두 가지 방법으로 접근해 보았는데, 첫 번째 방법은 간단한 증명이고, 두 번째 방법은 초순열을 만드는 알고리즘과 그 특성에 대해 분석하면서 증명하는 방법으로 첫 번째 방법보다는 어렵습니다. 이런 방법으로 만들 수 있다는 걸 보여준 것이므로 두 번째 방법이 이해가 안 되신다 하더라도 문제 해결에는 지장이 없을 것 같습니다.


    첫 번째 방법

    먼저 3을 예로 들면, 3에 대한 초순열을 123121321입니다. 이 순열은 123/231/312/213/132/321을 합친 것으로 볼 수 있습니다. 이 때 각 순열에 4를 붙인 뒤 그 순열을 한 번 더 반복해서 쓰고, 이를 합치면 4에 대한 초순열을 만들 수 있습니다.


    이해하기 쉽게 설명하자면,

     

    123->1234123
    231->2314231
    312->3124312
    213->2134213
    132->1324132
    321->3214321

    이므로 오른쪽을 다 합치면 4에 대한 초순열 123412314231243121342132413214321이 만들어집니다. 이 때 추가된 숫자는 4×(4-1)!=4!이므로, A(n)=A(n-1)+n!임을 알 수 있고, 따라서 A(n)=1!+2!+3!+•••+n!입니다.

     


    두 번째 방법

    5에 대한 초순열을 예로 들겠습니다. 1234의 순서대로 나오는 순열은 12345/23451/34512/45123/51234로 5가지가 있고, 이 5개의 순열을 나열하는 최소수열은 123451234입니다. 여기서 234를 겹치게 해서 쓰려면 23415의 순서를 가지는 수열 234152341을 쓸 수 있고, 더 뻗어나가면 123451234152341253412354123(이런 방식으로 만들어진 수열을 B(n)이라 부르겠습니다.)까지 쓸 수 있습니다. 123으로 시작하는 5개의 순열은 12345와 12354뿐인데, 이 두 순열은 이미 나왔으므로 위의 수열 B(5)에서 123을 겹치게 해서 더 쓸 수는 없기 때문입니다. 위의 B(5)를 살펴보면 1234의 순열에 5를 임의로 집어넣은 순열과, 이 순열의 순서를 하나씩 미룬 순열로 이루어져 있음을 알 수 있습니다. 다시 말해, 12345/12354/12534/15234와 이 각 순열을 하나씩 미룬 모든 순열(12345를 예를 들면, 23451과 34512, 45123, 51234가 모두 나온다는 말입니다.)이 모두 등장합니다.

    그런데 이런 방법으로 만든 모든 B(5)는 abc4라는 순열에서, abc에 123을 집어넣을 때 나오는 순열로  결정됩니다. 예를 들면 위의 예시에서 든 수열 B(5)는 첫 부분인 1234로 수열이 결정되었는데, 다른 수열 B(5)를 만들기 위해서 첫 부분을 1324나 3124, 2134 등으로 설정할 수 있습니다. 또한, 이런 방법으로 만든 모든 B(n) 내의 순열들은 각각 모두 다르면서, n에 대한 모든 순열을 포함합니다. 따라서 각각의 abc4로 만들어진 모든 B(5)를 합치면 5에 대한 초순열이 만들어집니다. 이를 일반화하면 첫 부분이 1부터 n-2까지의 수로 만들어지는 순열로 생성되는 모든 B(n)을 합치면 A(n)이 나온다는 결론을 얻을 수 있습니다. 아래에는 B(5)의 모든 예시를 썼습니다.


    123451234152341253412354123
    132451324153241352413254132
    213452134251342153421354213
    231452314253142351423154231
    312453124351243152431254312
    321453214352143251432154321


    여기서 B(n)의 길이는 (2n-1)+n(n-1)-2=n^2+n-3이고, B(n)이 총 (n-2)!개 있으므로 겹치는 걸 고려하지 않는다면 A(n)의 길이는 (n^2+n-3)×(n-2)!=n!+2(n-1)!-(n-2)!입니다.

     

    위의 B(5)를 자세히 살펴보면 맨 앞의 순열 abc와 맨 뒤의 순열 abc가 같습니다. 즉, B(n)에 대해 맨 앞의 수 (n-2)개와 맨 뒤의 수 (n-2)개는 동일합니다. 따라서 모든 B(n)을 최대로 겹치게 합칠 경우, 겹쳐지는 부분이 A(n-2)의 초순열이 되도록 B(n)을 배열할 수 있습니다. 위의 5에 대한 초순열의 예에서는 B(5)끼리의 맨 끝과 맨 마지막의 겹쳐지는 부분이 A(3)인 123121321이 되도록 만들면 되는 거죠. 따라서 겹쳐지는 부분의 길이는 (n-2)×(n-2)!-A(n-2)=(n-1)!-(n-2)!-A(n-2)이고, 이 부분을 위의 n!+2(n-1)!-(n-2)!에서 빼면 A(n)=A(n-2)+n!+(n-1)!이 됩니다.(여기서의 A(n)은 현재 설명하는 알고리즘으로 만들었을 때 생성되는 초순열의 길이입니다.) 점화식을 풀면 A(n)=1!+2!+3!+•••+n!으로 아까와 동일한 결론이 나옵니다.

     


    두 번째 방법을 보면 B(n)을 만드는 방법이 최선이고, B(n)을 겹치게 배열하는 방법에서도 최선의 방법을 따르고 있기 때문에 A(6)=873이 아닌 872라는 값이 나오는 것이 상당히 흥미롭고 예외적입니다. 새로운 알고리즘이 필요할 것 같은데, B(n)을 다른 방식으로 더 길게 만드는 방법으로 하면 A(n)을 줄이는 것이 가능해지기 때문에 그런 것 같습니다. A(6)이 123456123451623451263451236451 다음에 2가 아닌 3이 온 것과, 제가 고안한 알고리즘의 B(n)이 2개가 적절히 합쳐진 듯한 것을 고려해보면 6 이상의 n에 대해 A(n)의 최소길이를 만드는 알고리즘은 B(n)을 어떻게 만들고 B(n)끼리 어떻게 배치하느냐가 관건인 것 같습니다.


    이 문제는 A(6)과 A(7)의 순열배열 알고리즘을 좀 더 분석하면서 해결해가야 할 것 같습니다. 그리고 경험상으로는 A(6)이나 A(7)에 대해 초순열을 만드는 알고리즘을 찾아낸다 해도 n이 커질수록 새로운 알고리즘이 필요할 것 같은데, 이 알고리즘을 만드는 알고리즘을 찾아내야 할 것 같다는 생각도 듭니다.

    ​​​

    좋아요0 댓글수0