Conways сарбаздары - Conways Soldiers - Wikipedia

Конвейдің сарбаздары немесе секіргіштен секіру проблемасы бір адам математикалық ойын немесе математик ойлап тапқан жұмбақ Джон Хортон Конвей 1961 жылы. нұсқасы қазық пасьері, ол орын алады шексіз шахмат тақтасы. Тақта шексіз созылатын көлденең сызықпен бөлінген. Жолдың үстінде бос ұяшықтар, ал жолдың астында ойын бөліктерінің ерікті саны немесе «сарбаздар» орналасқан. Қазық пасьянсындағыдай, қозғалыс бір сарбаздың жанындағы сарбаздан бос камераға тік немесе көлденеңінен (бірақ диагональ бойынша емес) бос камераға секіріп түсіп, секірген солдатты алып тастаудан тұрады. Сөзжұмбақтың мақсаты - сарбазды көлденең сызықтан мүмкіндігінше жоғары орналастыру.

Конвей сарбаздарының 1, 2, 3 және 4-қатарларға жету шаралары. «В» таңбасы бар адамдар «А» белгілеріне балама болып табылады.

Конвей, қолданылған стратегияға қарамастан, сарбазға көлденең сызықтан төрт қатардан жоғары ілгерілеуге мүмкіндік беретін соңғы жүрістер тізбегі жоқ екенін дәлелдеді. Оның дәлелі жасушалардың мұқият таңдалған салмағын қолданады ( алтын коэффициент ) және ол жалпы салмақтың тек төмендеуі немесе тұрақты болып қалуы мүмкін екенін дәлелдеді. Бұл дәлел бірқатар танымал математикалық кітаптарда келтірілген.^{[дәйексөз қажет ]}

Саймон Тэтэм және Гарет Тейлор көрсетті^[1][2] бесінші қатарға an арқылы жетуге болады шексіз қадамдар сериясы. Егер қиғаш секірулерге рұқсат етілсе, 8-ші қатарға жетуге болады, бірақ 9-шы қатарға емес.^{[дәйексөз қажет ]} Ол сондай-ақ көрсетілді^{[дәйексөз қажет ]} бұл, n-өлшемді ойын нұсқасы, оған жетуге болатын ең жоғарғы қатар ${ displaystyle 3n-2}$. Конвейдің салмақ өлшеуі дәлелдейді^{[дәйексөз қажет ]} бұл қатар ${ displaystyle 3n-1}$ қол жеткізу мүмкін емес. Бұл қатарды көрсету айтарлықтай қиын ${ displaystyle 3n-2}$ мүмкін қол жеткізілді.^[3]

Конвейдің бесінші қатарға қол жетімді емес екендігінің дәлелі

Белгілеулер және анықтамалар

Анықтаңыз ${ displaystyle varphi = { frac {{ sqrt {5}} - 1} {2}} шамамен 0.61803 , 39887 ldots}$. (Басқа сөздермен айтқанда, ${ displaystyle varphi}$ мұнда өзара туралы алтын коэффициент.) Мұны ескеріңіз ${ displaystyle varphi ^ {2} = 1- varphi}$.

Мақсатты квадрат мәнімен белгіленсін ${ displaystyle varphi ^ {0} = 1}$және барлық басқа квадраттар мәнімен белгіленеді ${ displaystyle varphi ^ {n}}$, қайда ${ displaystyle n}$ болып табылады Манхэттен қашықтығы мақсатты алаңға. Содан кейін біз сарбаздар алаңдарының мәндерін қосу арқылы сарбаздар конфигурациясының «балын» есептей аламыз. Мысалы, келесі секірістегі мақсатты алаңға жету үшін орналастырылған тек екі сарбаздан тұратын конфигурацияда ұпай болады ${ displaystyle varphi ^ {1} + varphi ^ {2}}$.

Сарбаз басқа сарбаздың үстінен секіргенде, үш жағдайды ескеру керек:

1. Сарбаз секіргенде қарай мақсатты квадрат: сарбаз алаңының мәні болсын ${ displaystyle varphi ^ {n}}$ кейбіреулер үшін ${ displaystyle n}$, және ол секірген квадраттың мәні болады ${ displaystyle varphi ^ {n-1}}$; онда секіруден кейінгі ұпайдың жалпы өзгерісі ${ displaystyle varphi ^ {n-2} - varphi ^ {n-1} - varphi ^ {n} = varphi ^ {n-2} (1- varphi - varphi ^ {2}) = 0}$.
2. Сарбаз сол кезде қалады бірдей оның секіруден кейінгі мақсаттық квадраттан қашықтығы: бұл жағдайда ұпайдың өзгеруі ${ displaystyle varphi ^ {n} - varphi ^ {n-1} - varphi ^ {n} = - varphi ^ {n-1}}$.
3. Сарбаз секіргенде алыс мақсатты квадраттан: Мұндағы ұпайдың өзгерісі ${ displaystyle varphi ^ {n + 2} - varphi ^ {n + 1} - varphi ^ {n} = varphi ^ {n} ( varphi ^ {2} - varphi -1) = - 2 varphi ^ {n + 1}}$.

Сонымен, ешқандай секіру конфигурацияның жалпы ұпайын ешқашан арттырмайды.

Бастапқы конфигурацияның балын есептеу

Енді тек бір шексіз көлденең сызық толығымен сарбаздармен толтырылатын бастапқы конфигурацияны қарастырайық.

Егер бұл көлденең сарбаздар мақсатты квадраттан бірден төмен болса, онда конфигурацияның ұпайы болады ${ displaystyle varphi +2 varphi ^ {2} +2 varphi ^ {3} + ldots}$. Сызық ұпайы екі мақсатты квадраттың астындағы бос орындар ${ displaystyle varphi ^ {2} +2 varphi ^ {3} +2 varphi ^ {4} + ldots = varphi ( varphi +2 varphi ^ {2} +2 varphi ^ {3} + ldots)}$. Сызық ұпайы үш төмендегі кеңістіктер ${ displaystyle varphi ^ {2} ( varphi +2 varphi ^ {2} +2 varphi ^ {3} + ldots)}$. Және тағы басқа.

Толық бастапқы конфигурацияны қарастырыңыз, мұнда сарбаздар қызыл сызықтың астына бүкіл жарты жазықтықты толтырады. Бұл конфигурацияның бағасы - жеке жолдар ұпайларының қосындысы. Сондықтан, егер мақсатты квадрат қызыл сызықтан жоғары болса, онда ұпай болады

${ displaystyle S_ {1} = ( varphi +2 ( varphi ^ {2} + varphi ^ {3} + varphi ^ {4} ldots)) (1+ varphi + varphi ^ {2} + varphi ^ {3} + ldots)}$.

Осы кезде тағы бір қызықты қасиетін байқаңыз ${ displaystyle varphi}$, атап айтқанда ${ displaystyle sum _ {n = 2} ^ { infty} varphi ^ {n} = 1}$. Осы сәйкестікті қолдану пайда болады

${ displaystyle S_ {1} = ( varphi +2) (1+ varphi +1) = ( varphi +2) ^ {2} = 5 + 3 varphi шамамен 6.85410 ldots}$.

Егер мақсатты квадрат қызыл сызықтан жоғары екінші қатарда болса, онда кез-келген сарбаз мақсатты алаңнан бір қашықтықта орналасқан, сондықтан ұпай

${ displaystyle S_ {2} = varphi S_ {1} = 2 + 2 varphi}$.

Сол сияқты:

${ displaystyle S_ {3} = varphi S_ {2} = 2 + varphi}$,

${ displaystyle S_ {4} = varphi S_ {3} = 1 + varphi}$,

${ displaystyle S_ {5} = varphi S_ {4} = 1}$.

Сарбаз мақсатты квадратқа бірнеше шектеулі жүрістерден кейін жеткенде, аяқталатын конфигурацияда ұпай болады ${ displaystyle E = varphi ^ {0} + epsilon}$, қайда ${ displaystyle varphi ^ {0}}$ мақсатты алаңдағы сарбаздың үлесін білдіреді және ${ displaystyle epsilon}$ ұшақтың басқа жерлерінде қалған шексіз сарбаздардың (аз, бірақ оң) үлестерін білдіреді.

Осылайша, біз мақсатты квадрат сарбаздардың шексіз жарты жазықтығынан бесінші қатарда болғанда, бастапқы конфигурацияның ұпайы дәл болатынын көрсеттік ${ displaystyle S_ {5} = 1}$; аяқталатын конфигурацияның ұпайы ${ displaystyle E = 1 + epsilon}$; және секірудің ешқайсысы есепті көбейтпейтіндіктен, бізде болмауы керек ${ displaystyle S_ {5} geq E}$. Бұл қайшылық; Q.E.D., кез-келген сарбазға соңғы секіруден кейін бесінші қатардағы шаршы алаңға жету мүмкін емес.

Әдебиеттер тізімі

• Э.Берлекамп, Дж.Конвей және Р.Гай, сіздің математикалық пьесаларыңыз үшін жеңіске жету жолдары, 2-ші басылым, т. 4, тарау. 23: 803—841, A K Peters, Wellesley, MA, 2004.
• Р.Хонсбергер, дойбыдан секіруге қатысты проблема, математикалық асыл тастар II, тарау. 3: 23—28, MAA, 1976.
• Г.Белл, Д.Хиршберг және П.Герреро, сольтер армиясына қажетті минималды мөлшер, INTEGERS Комбинаторлық сан теориясының электронды журналы, 7-том, G7, 2007 ж.

Сыртқы сілтемелер

• cut-the-knot.org ойын түсіндіреді
• Ойынның бірнеше нұсқаларын сипаттайтын бет, жақында қолданылған сілтемелер
• Вайсштейн, Эрик В. «Конвейдің сарбаздары». MathWorld.
• Ойынның интерактивті нұсқасы (1)
• Ойынның интерактивті нұсқасы (2)
• Plus онлайн журналы ойын сипаттайды