äžçäžåšæ è¡
åã倧ããã®ç«æ¹äœãïŒå暪ã«äžŠã¹ããã®ãèããã
ãã®ãšããïŒã€ã®ç«æ¹äœãç¹ãã£ãŠããã°åé ç¹ã¯åããã£ãŠããã®ã§ããã«äžã€ã®é ç¹ããããã®ãšèãããš
äžéšã«ã¯ïŒïŒåã®ããŸãäžéšã«ãïŒïŒåã®é ç¹ãæã¡
äžéšã®åé ç¹ãå·Šäžéšã®å¥¥ããæèšåãã«é ç¹1,2,3,4,5,6,7,8,9,10
åããé ç¹1ã®çäžãé ç¹11ãšããŠãæèšåãã«åºéšã®é ç¹ã12,13,14,15,16,17,18,19,20
ã®çªå·ãã€ããŠããã
ãã®ãšãã
[A]åºçºç¹ãæå®ããŠèŸº(åããã£ãæã¯äžã€ã®èŸºãšããã)ã蟿ã£ãŠ
ã ãã¹ãŠã®é ç¹ãäžåºŠãã€èšªããããã³ãŒã¹ãäœéãå¯èœãã調ã¹ãŠæ¬²ããã
(1)åºçºç¹ãé ç¹1ãšæå®ããå Žåã
(2)åºçºç¹ãé ç¹2ãšæå®ããå Žåã
(3)åºçºç¹ãé ç¹3ãšæå®ããå Žåã
次ã«
[B]å
šéšã®é ç¹ãäžåºŠãã€èšªããŠãåºçºç¹ã«æåŸæ»ã£ãŠããããã³ãŒã¹ã¯äœåŠãåºçºç¹ã«ããŠããã°ã
ã æãå€ãååšã§ãããïŒ
ã ãŸãããã¯äœéããïŒ
GAIæ§ãããã«ã¡ã¯ã
äžçæžãã ãšæããŸãããWikipediaäžçæžãã®ãäžçæžãå¯èœãã©ããã®å€å®æ³ãã«ãããšã
ïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒåŒçšéå§ïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒ
ããé£çµã°ã©ããäžçæžãå¯èœãªå Žåã®å¿
èŠååæ¡ä»¶ã¯ã以äžã®æ¡ä»¶ã®ããããäžæ¹ãæãç«ã€ããšã§ããïŒãªã€ã©ãŒè·¯åç
§ïŒã
ã»ããã¹ãŠã®é ç¹ã®æ¬¡æ°ïŒé ç¹ã«ã€ãªãã£ãŠãã蟺ã®æ°ïŒãå¶æ° âéçãèµ·ç¹ã«æ»ãå ŽåïŒéè·¯ïŒ
ã»ã次æ°ãå¥æ°ã§ããé ç¹ã®æ°ã2ã§ãæ®ãã®é ç¹ã®æ¬¡æ°ã¯å
šãŠå¶æ°ãâéçãèµ·ç¹ã«æ»ããªãå ŽåïŒéè·¯ã§ãªãè·¯ïŒ
ïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒåŒçšçµäºïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒïŒ
ãšãããŸãããããæºè¶³ããŠãŸããïŒ
管ç人ããã®å³ã§èŠããšãé ç¹ïŒ,11,20,10,5,6,15,16ã¯èŸºãïŒæ¬ã§å¥æ°ã§8ã§ãã
ãŸããé ç¹2,3,4,12,13,14,9,8,7,19,18,17ã§èŸºã4æ¬ã§å¶æ°ã§12ã§ãã
å¶æ°ã®å Žåãå
¥ãâåºãã®ç¹°ãè¿ãã§ãééç¹ã§ãããå¥æ°ã¯ãåºâå
¥ãâåºãããå
¥ãâåºâå
¥ããããããããªãã®ã§ãåºçºç¹ãçµç¹ã§ããã ãããå¥æ°ã¯2ã€ããããããªãã®ã§ãã
åéãã§ããããã¿ãŸããã
{A]
(1)é ç¹1ãåºçºç¹ãšããäžã€ã®çµè·¯
1->10->9->2->12->11->20->19->18->8->3->13->14->17->7->4->5->6->16->15
ã§åé ç¹ãäžåºŠãã€èšªããŠããã
ïŒå¥ã«ãã¹ãŠã®èŸºãéããšã¯èŠæ±ãããŠããªããïŒ
[B]
ã§é ç¹1ãåºçºç¹ãšããå Žåã®äžäŸ
1->2->9->19->18->8->3->4->7->17->16->6->5->15->14->13->12->11->20->10->1
ïŒå¿è«äžçã§æããŸãããéåžžã®äžçæžãã®åé¡ãšã¯è¶£æšãç°ã«ããŸããïŒ
[B]ã¯ããã¹ãŠã®èŸºã1åã ãéã£ãŠãªãã®ã§ãäžçæžããšã¯èšããŸãããã
ïŒå¿è«äžçã§æããŸãããéåžžã®äžçæžãã®åé¡ãšã¯è¶£æšãç°ã«ããŸãã
ãããªããããããŸããããç§ã®åéãã§ããããã¿ãŸããã
[B]ã®æ¹ãæ¯èŒçç°¡åãããªã®ã§ããã¡ãã ããããŸããã
ãã£ãŠãããã©ããã¯èªä¿¡ããããŸããã
nåã®ç«æ¹äœã暪ã«äžŠã¹ããã®ãèããã
巊端ã®ç«æ¹äœã®å·ŠåŽã®4åã®é ç¹ãé çªã«A,B,C,Dãšãããã®ããå³åŽã®4åã®é ç¹ãããããa,b,c,dãšããã
å·Šããiçªç®ã®ç«æ¹äœã®å³åŽã®4åã®é ç¹(=i+1çªç®ã®ç«æ¹äœã®å·ŠåŽã®4åã®é ç¹)ããŸãšããŠi段ç®ãšç§°ããã
å
šéšã®é ç¹ãéãåºçºç¹ã«æåŸã«æ»ãã³ãŒã¹ã®æ°ã¯ããã¹ãŠã®é ç¹ãéãã«ãŒãã®æ°ã®2å(ã©ã¡ãåšããã®åºå¥)ã«ãªãã®ã§ã
ã©ããåºçºç¹ã«ããŠãã³ãŒã¹ã®æ°ã¯å€ãããªãããã®æ°ã a[n] éããšããã
以äžã§ã¯Aãåºçºç¹ãšããã³ãŒã¹ãèããã
1åšããŠAã«æ»ãäžã€åã®ç¹ã¯BãDãaã®ã©ããã§ããã察称æ§ããã©ã¹ãåãBã®ã³ãŒã¹æ°ãšã©ã¹ãåãDã®ã³ãŒã¹æ°ã¯çããã
ãã®ã©ã¹ãåãBã®ã³ãŒã¹æ°(=ã©ã¹ãåãDã®ã³ãŒã¹æ°)ã b[n] éããšããã
n=0ã®å Žåãããªãã¡åãªãåè§åœ¢ABCDãèãããšãã©ã¹ãåãBã®ã³ãŒã¹ã¯
AâDâCâBâA
ã®1éããªã®ã§ã b[0]=1 ã§ããã a[0]=2 ã§ããã
nâ§1ã®å Žåã0段ç®ã®4ç¹ãéãé çªã¯ä»¥äžã®(1.1)ãã(3.4)ãŸã§ã®ããããã«ãªãã
(1.1) AâaââŠâbâBâCâDâA
(1.2) AâBâbââŠâcâCâDâA
(1.3) AâBâCâcââŠâdâDâA
(1.4) AâBâCâDâdââŠâaâA
(1.5) AâaââŠâdâDâCâBâA
(1.6) AâDâdââŠâcâCâBâA
(1.7) AâDâCâcââŠâbâBâA
(1.8) AâDâCâBâbââŠâaâA
(2.1) AâaââŠâbâBâCâcââŠâdâDâA
(2.2) AâBâbââŠâcâCâDâdââŠâaâA
(2.3) AâaââŠâdâDâCâcââŠâbâBâA
(2.4) AâDâdââŠâcâCâBâbââŠâaâA
(3.1) AâaââŠâcâCâBâbââŠâdâDâA
(3.2) AâBâbââŠâdâDâCâcââŠâaâA
(3.3) AâaââŠâcâCâDâdââŠâbâBâA
(3.4) AâDâdââŠâbâBâCâcââŠâaâA
ã(1.1)ïœ(1.8)ã®å Žå
(1.1)ãäŸã«èãããšãéšååaââŠâbã®ç®æã¯n-1åã®ç«æ¹äœã§Aãåºçºãã©ã¹ãåãBã«ãªãã³ãŒã¹æ°ã«çããã®ã§ b[n-1] éããšãªãã
(1.2)ïœ(1.8)ãåæ§ã« b[n-1] éãã§ããã
ã(2.1)ïœ(2.4)ã®å Žå
(2.1)ãäŸã«èããã
éšååaââŠâbã®æé«å°é段ãi段ç®ãéšååcââŠâdã®æé«å°é段ãj段ç®ãšããã
ã³ãŒã¹ã¯å
šäœãšããŠãã¹ãŠã®ç¹ãéãã®ã§ãi,jã®å°ãªããšãäžæ¹ã¯nãšãªãã
i=j=nã®å Žåãäºã€ã®éšååã¯ã©ã¡ãããå³ãžçŽé²ãn段ç®ã§ã²ãšã€é£ãžç§»åãå·ŠãžçŽé²ããŠæ»ãã³ãŒã¹ãããªãã®ã§ã1éãã§ããã
i<j=nã®å ŽåãéšååaââŠâbã¯å³ãžçŽé²ãi段ç®ã§ã²ãšã€é£ãžç§»åãå·ŠãžçŽé²ããŠæ»ãããšã«ãªãã
éšååcââŠâdã¯i+1段ç®ãŸã§å³ãžçŽé²ãi+1段ç®ä»¥éã®ãã¹ãŠã®ç¹ãéã£ãåŸi+1段ç®ãã1段ç®ãŸã§å·ŠãžçŽé²ããããšã«ãªãã
ãã£ãŠãã®å Žåã¯ãn-i-1åã®ç«æ¹äœã§Aãåºçºãã©ã¹ãåãBã«ãªãã³ãŒã¹æ°ã«çããã®ã§ b[n-i-1] éããšãªãã
j<i=nã®å Žåãåæ§ã« b[n-i-1] éããšãªãã
以äžã®3ã€ã®å Žåã®æ°ãåããããš(2.1)ã®ã³ãŒã¹æ°ã¯ã
1+2*Σ[i=1..n-1]b[n-i-1]
= 1+2*Σ[k=0..n-2]b[k]
éããšãªãã
(2.2)ïœ(2.4)ãåæ§ã« 1+2*Σ[k=0..n-2]b[k] éãã§ããã
ã(3.1)ïœ(3.4)ã®å Žå
çµè«ãšããŠããã®å Žåã®ã³ãŒã¹ã¯ååšããªãããã®çç±ã以äžã«ç€ºãã
(3.1)ãäŸã«èããã
éšååaââŠâcã®æé«å°é段ãi段ç®ãéšååbââŠâdã®æé«å°é段ãj段ç®ãšããã
ã³ãŒã¹ã¯å
šäœãšããŠãã¹ãŠã®ç¹ãéãã®ã§ãi,jã®å°ãªããšãäžæ¹ã¯nãšãªãã
i=j=nã®å Žåãn段ç®ãŸã§ã¯çŽé²ã§è¡ãæ¥ãããããªãããn段ç®ã§ã®äºã€ã®éšååã®ã³ãŒã¹ã®äž¡ç«ãã§ããªãããããã¯ããããªãã
i<j=nã®å ŽåãéšååaââŠâcã¯i段ç®ãŸã§ã®ã©ããã®æ®µã§ãã®æ®µå
ã®å°ãªããšã3ç¹ãéãããšã«ãªããã
ãããããšéšååbââŠâdããã®æ®µãåŸåŸ©ã§ééããããã®å°ãªããšã2ç¹ã確ä¿ã§ããªãããããããªãã
j<i=nã®å Žåãåæ§ã§ããã
以äžããã(3.1)ã®ã³ãŒã¹ã¯ååšããªãããšããããã
(3.2)ïœ(3.4)ãåæ§ã§ããã
ãããŸã§ã®ããšããnâ§1ã®ãšã次ã®äºã€ã®åŒãåŸãããã
a[n] = 8*b[n-1] + 4*(1+2*Σ[k=0..n-2]b[k]) âŠåŒâ
b[n] = 3*b[n-1] + 1*(1+2*Σ[k=0..n-2]b[k]) âŠåŒâ¡
åŒâ¡ããb[n]ã®æŒžååŒ
b[n] = 1 + 3*b[n-1] + 2*Σ[k=0..n-2]b[k] âŠåŒâ¡'
ãåŸãããa[n]ã¯åŒâ ãã
a[n] = 4 + 8*Σ[k=0..n-1]b[k] âŠåŒâ '
ã䜿ãã°æ±ãŸãã
GAIããã®åé¡[B]ã¯n=4ã®å Žåãªã®ã§ãèšç®ãããš a[4]=612 éããšãªãã
ã©ãã§ãããããGAIãããæ±ããæ°ãšåãã«ãªããŸããã§ããããïŒ
[A]
(1) 2918(éã)
(2) 2188(éã)
(3) 2116(éã)
ã§ãã£ãã®ã«å¯Ÿã
[B]
ã®å
ã«æ»ããã³ãŒã¹ã«éå®ãããšãã©ã®é ç¹ããåºçºãããã
å
ã«æ»ããã³ãŒã¹æ°ã¯äžå®ã§ãããã²ããããæ±ããããŠãã612(éã)
ãããŸããã
[A]ã®å Žåã®æ§ã«åºçºç¹ãç°ãªãã°åœç¶ç°ãªãçµæãèµ·ããã ãããšèšç®ãããããŠã¿ããšã
åæã«æ±ºãã€ããŠããããšãèŠäºã«è£åãããŸããã
ãããåŸããèããŠã¿ãããéããçµè·¯ã¯ããããžãŒçã«ã©ããåããã®ã§ããããšã«ãªãããã«æããŠçŽåŸããŸããã
é ã®äžã ãã§ãã®612ãèŠã€ããããããšã«é©ããŸããã
ã©ããããã£ãŠããããã§ããã£ãã§ãã
n=4ã§æãç«ã£ãŠããã®ãªãã°æŒžååŒã¯æ£ããå¯èœæ§ãé«ãã§ããã
ãšãããŸã§æžããåŸããµãšæãç«ã£ãŠèª¿ã¹ãŠã¿ããã
OEISã®A003699ã«ããã«ãã³éè·¯ã®æ°(=ã³ãŒã¹æ°ã®åå)ãèŒã£ãŠããŸããã
ããã®ïŒé
é挞ååŒãèŠãã«ãã£ãšã·ã³ãã«ãªèãæ¹ãããããã§ãã
æåããååã®æ°ã§æ€çŽ¢ããŠããã°ããã£ãã®ãâŠâŠã
ç§ã®æçš¿ã§äžãæééããŠããã®ã§ä¿®æ£ããŸãã
ã(2.1)ïœ(2.4)ã®å Žåãã®äž
誀ïŒãj<i=nã®å Žåãåæ§ã« b[n-i-1] éããšãªããã
â
æ£ïŒãj<i=nã®å Žåãåæ§ã«èã㊠b[n-j-1] éããšãªããã
ããã²ãããã®ãšèãæ¹ãå
±éããéšåãå€ãã§ããããããªã®ã§ã©ãã§ãããã
n åã®ç«æ¹äœãå·Šå³äžåã«äžŠã¹ãŠããå Žåã§èããŸãã
æãå³åŽã«ããç«æ¹äœã®å³åŽã®é¢ã®é ç¹ 4 ã€ã¯ã
ã»4 ã€ãé£ç¶ããŠéãïŒã³åïŒ
ã»2 ã€ããŸãéããåŸã§æ®ã 2 ã€ãéãïŒäºåïŒ
ã®ããããã§éãããšã«ãªããŸãã
ã³åã®ãã¿ãŒã³æ°ã ã³[n], äºåã®ãã¿ãŒã³æ°ã äº[n] ãšããŸãã
ã³åã«ã€ããŠãå³åŽã®é¢ã® 4 é ç¹ãåé€ããŠçµè·¯ãç絡ããããšãèããŸãã
GAI ããã®å³ã§äŸãæããã°ãâŠâŠâ4â5â6â16â15â14ââŠâŠ ã âŠâŠâ4â14ââŠâŠ ã«ç絡ãããããªã€ã¡ãŒãžã§ãã
ç«æ¹äœ n+1 åã®å Žåã®ã³åã®çµè·¯å
šãŠãç絡ãããšã
ç«æ¹äœ n åã®å Žåã®ã³åã®çµè·¯å
šçš®ã 3 ã€ãã€ããã³äºåã®çµè·¯å
šçš®ã 2 ã€ãã€ã§ããã®ã§ã
ã³[n+1] = 3*ã³[n] + 2*äº[n]
äºåã«ã€ããŠãåæ§ã«èããŸãã
GAI ããã®å³ã§äŸãæããã°ãâŠâŠâ4â5â6â7ââŠâŠâ17â16â15â14ââŠâŠ ã âŠâŠâ4â7ââŠâŠâ17â14ââŠâŠ ã«ç絡ãããããªã€ã¡ãŒãžã§ãã
ç«æ¹äœ n+1 åã®å Žåã®äºåã®çµè·¯å
šãŠãç絡ãããšã
ç«æ¹äœ n åã®å Žåã®ã³åã®çµè·¯å
šçš®ã 1 ã€ãã€ããã³äºåã®çµè·¯å
šçš®ã 1 ã€ãã€ã§ããã®ã§ã
äº[n+1] = ã³[n] + äº[n]
䞡挞ååŒãã ã³[n] ãæ¶å»ããŠ
äº[n+2] = 4*äº[n+1] - äº[n]
ãŸããã³[1] = 8, äº[1] = 4 ãªã®ã§ãäº[2] = 12, äº[3] = 44, äº[4] = 164, äº[5] = 612
ãã£ãŠãæ±ããç·æ°ã¯ ã³[4] + äº[4] = äº[5] = 612 éãã§ãã
ããã«ãã³éè·¯æ°ããa[n] = (1/2)*ã³[n] + (1/2)*äº[n] = (1/2)*äº[n+1] ãšèãããšã
a[1] = 6, a[2] = 22, a[n+2] = 4*a[n+1] - a[n]
ãšãã挞ååŒãæãç«ã€ããšã瀺ãããŸãã
ïŒããã§ã¯ n ãç«æ¹äœæ°ãšããŠèããŠããã®ã§ãA003699 ãšã¯ n ã®å€ã 1 ã€ãããŸãïŒ