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

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이 주어졌을 때, 모든 순열을 부분수열로 가지는 수열의 최소 길이를 구하라. 

 

 

댓글 19

  • 누군가 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