ប៉មហាណូយ
ផ្លាស់ទីប៉មទាំងមូលទៅបង្គោលខាងស្ដាំ ម្ដងមួយថាស ហើយហាមដាក់ថាសធំលើថាសតូច។ សាកល្បងចំនួន 2^n − 1 ជំហានដ៏ឥតខ្ចោះ!
របៀបលេងប៉មហាណូយ
ប៉មហាណូយគឺជាល្បែងផ្គុំតក្កវិជ្ជាដ៏ល្បីល្បាញបំផុតក្នុងគណិតវិទ្យា៖ បង្គោលបី ប៉មនៃថាសដែលរៀបពីធំទៅតូច និងភារកិច្ចមួយដែលមើលទៅសាមញ្ញ — សង់ប៉មទាំងមូលឡើងវិញនៅបង្គោលចុងម្ខាង។ បង្កើតឡើងដោយគណិតវិទូបារាំង Édouard Lucas ក្នុងឆ្នាំ 1883 វាលាក់រចនាសម្ព័ន្ធហៅខ្លួនឯង (recursive) ដ៏ស្រស់ស្អាតនៅពីក្រោយច្បាប់តូចៗបី។ អ្នកណាក៏អាចដោះស្រាយប៉មបួនថាសបានដោយអត់ធ្មត់បន្តិច ប៉ុន្តែប៉មប្រាំបីថាសទាមទារវិន័យពិតប្រាកដ ព្រោះថាសនីមួយៗដែលបន្ថែម ធ្វើឱ្យប្រវែងដំណោះស្រាយឥតខ្ចោះកើនទ្វេដង។ កំណែនេះតាមដានជំហានរបស់អ្នកធៀបនឹងតម្លៃល្អបំផុតតាមគណិតវិទ្យា និងពេលវេលា ហើយដំណើរការទាំងស្រុងក្នុងកម្មវិធីរុករក ទាំងអនឡាញនិងក្រៅបណ្ដាញ។
គោលដៅ
ផ្លាស់ទីប៉មថាសទាំងមូលពីបង្គោលឆ្វេងទៅបង្គោលស្ដាំ (សម្គាល់ដោយផ្កាយ)។ ប៉មត្រូវបញ្ចប់ដូចពេលចាប់ផ្ដើមទាំងស្រុង — ថាសធំបំផុតនៅបាត ថាសតូចបំផុតនៅកំពូល — គ្រាន់តែនៅបង្គោលផ្សេង។ អ្នកឈ្នះភ្លាមៗ ពេលថាសចុងក្រោយចុះចតលើបង្គោលស្ដាំ ជំហានតិចនិងពេលខ្លីប៉ុនណា ពិន្ទុខ្ពស់ប៉ុណ្ណោះ។ ភាពឥតខ្ចោះមានន័យថា 2^n − 1 ជំហាន៖ 15 សម្រាប់បួនថាស 63 សម្រាប់ប្រាំមួយ 255 សម្រាប់ប្រាំបី។
ការរៀបចំ
បង្គោលបីឈរជាប់គ្នា៖ ឆ្វេង កណ្ដាល និងស្ដាំ។ ថាសទាំងអស់ចាប់ផ្ដើមនៅបង្គោលឆ្វេងជារាងពីរ៉ាមីតឥតខ្ចោះ។ កម្រិតលំបាកកំណត់កម្ពស់ប៉ម — ងាយ 4 ថាស មធ្យម 6 ពិបាក 8។ បង្គោលកណ្ដាលគឺជាកន្លែងធ្វើការរបស់អ្នក៖ ល្បែងផ្គុំនេះមិនអាចដោះស្រាយបានបើគ្មានវា ហើយការរៀនប្រើវាគឺជាសិល្បៈទាំងមូលនៃល្បែងនេះ។ ឧបករណ៍រាប់ជំហានធៀបអ្នកផ្ទាល់ជាមួយដំណោះស្រាយល្អបំផុត ហើយនាឡិកាធ្វើឱ្យអ្នកស្មោះត្រង់នឹងខ្លួនឯង។
ច្បាប់
- ផ្លាស់ទីមួយថាសក្នុងមួយវេន។ គ្មានវិធីរំកិលពីរថាសព្រមគ្នាទេ — ប៉មផ្លាស់ទីបានតែម្ដងមួយស្រទាប់ប៉ុណ្ណោះ។
- មានតែថាសនៅកំពូលបង្គោលប៉ុណ្ណោះដែលអាចផ្លាស់ទីបាន។ ថាសដែលកប់នៅក្រោមត្រូវជាប់គាំង រហូតដល់អ្វីៗនៅពីលើវាត្រូវបានផ្លាស់ទីចេញអស់។
- ថាសមិនអាចដាក់លើថាសតូចជាងវាបានឡើយ។ ថាសណាក៏អាចដាក់លើបង្គោលទទេ ឬលើថាសធំជាងបាន — កម្រិតតែមួយនេះហើយដែលធ្វើឱ្យល្បែងផ្គុំក្លាយជាល្បែងផ្គុំ។
- របៀបផ្លាស់ទី៖ ចុចបង្គោលប្រភពដើម្បីលើកថាសកំពូល បន្ទាប់មកចុចបង្គោលគោលដៅដើម្បីដាក់ចុះ។ ចុចបង្គោលដដែលម្ដងទៀត ដើម្បីដាក់ថាសចុះវិញ។ អ្នកលេងក្ដារចុចអាចប្រើគ្រាប់ចុច 1, 2 និង 3 សម្រាប់បង្គោលឆ្វេង កណ្ដាល និងស្ដាំ ហើយ U ដើម្បីត្រឡប់ក្រោយ។
- ប៊ូតុង «ត្រឡប់ក្រោយ» ដកជំហានចុងក្រោយវិញ អាចត្រឡប់រហូតដល់ដើមល្បែងបើចាំបាច់។ ជំហានដែលបានដកនៅតែរាប់ចូលក្នុងចំនួនជំហានសរុប ដូច្នេះផែនការស្អាតឈ្នះការសាកល្បងខុសៗ ខាងពិន្ទុ។
ការឈ្នះ
អ្នកឈ្នះពេលថាសទាំងអស់បង្កើតជាប៉មពេញលេញនៅបង្គោលស្ដាំ។ បដាបង្ហាញចំនួនជំហានរបស់អ្នកក្បែរចំនួនល្អបំផុត ដូច្នេះអ្នកដឹងច្បាស់ថាខ្លួនខិតជិតភាពឥតខ្ចោះប៉ុនណា ហើយពិន្ទុត្រូវបានបញ្ជូនទៅក្ដារពិន្ទុ។ ប៉មដែលបញ្ចប់នៅបង្គោលកណ្ដាលមិនរាប់ទេ — គោលដៅគឺបង្គោលខាងស្ដាំ ដូច្នេះរៀបផែនការជំហានដំបូងដោយគិតដល់ទីបញ្ចប់។
រឿងព្រេងថាសមាស 64
Lucas លក់ល្បែងផ្គុំនេះជាមួយរឿងដ៏អស្ចារ្យមួយ៖ នៅប្រាសាទធំមួយក្នុងក្រុង Benares ព្រះសង្ឃខិតខំផ្លាស់ទីប៉មថាសមាស 64 ដែលដោតលើម្ជុលពេជ្របី ដោយផ្លាស់ទីមួយថាសក្នុងមួយវិនាទីតាមច្បាប់ដដែលនេះ ទាំងយប់ទាំងថ្ងៃ។ រឿងថា ពេលថាសចុងក្រោយចូលកន្លែង ពិភពលោកនឹងដល់ទីបញ្ចប់។ មិនចាំបាច់ប្រញាប់រកកន្លែងពួនទេ៖ 2^64 − 1 ជំហានស្មើនឹង 18,446,744,073,709,551,615 — ក្នុងល្បឿនមួយជំហានក្នុងមួយវិនាទី ព្រះសង្ឃត្រូវការប្រហែល 585 ពាន់លានឆ្នាំ ស្មើនឹងសែសិបដងនៃអាយុបច្ចុប្បន្នរបស់សកលលោក។ រឿងព្រេងនេះនៅរស់រានមកដល់សព្វថ្ងៃ ព្រោះវាចាប់យកមេរៀនជ្រៅបំផុតរបស់ល្បែងផ្គុំបានយ៉ាងរស់រវើក៖ កំណើនអិចស្ប៉ូណង់ស្យែលលឿនហួសការស្រមៃ ហើយថាសបន្ថែមនីមួយៗធ្វើឱ្យការងារកើនទ្វេដង។
គន្លឹះយុទ្ធសាស្ត្រ
- គិតបែបហៅខ្លួនឯង។ ដើម្បីផ្លាស់ទីប៉ម n ថាសទៅស្ដាំ៖ ផ្លាស់ទី n−1 ថាសខាងលើទៅកណ្ដាល យកថាសធំបំផុតទៅស្ដាំ រួចផ្លាស់ទីប៉ម n−1 នោះមកលើវាវិញ។ ប៉មហាណូយខ្ពស់ប៉ុនណាក៏ដោយ គឺគ្រាន់តែជាគំនិតតែមួយនេះដដែលៗ។
- តាមដានថាថាសតូចបំផុតទៅណា។ ក្នុងដំណោះស្រាយឥតខ្ចោះ ថាសតូចបំផុតផ្លាស់ទីរៀងរាល់វេនម្ដង ហើយវិលទៅទិសដដែលជានិច្ច — ពេលចំនួនថាសជាលេខគូ (ដូចទាំងបីកម្រិតនៅទីនេះ) វាធ្វើដំណើរ ឆ្វេង → កណ្ដាល → ស្ដាំ → ត្រឡប់មកឆ្វេងវិញ។
- ដើរឆ្លាស់គ្នា។ ដំណោះស្រាយល្អបំផុតឆ្លាស់គ្នាយ៉ាងតឹងរ៉ឹង៖ ថាសតូចបំផុត បន្ទាប់មកជំហានស្របច្បាប់តែមួយគត់ផ្សេងទៀត រួចថាសតូចបំផុតម្ដងទៀត។ បើអ្នកផ្លាស់ទីថាសដដែលពីរដងជាប់គ្នា អ្នកបានខ្ជះខ្ជាយមួយជំហានហើយ។
- កុំឱ្យថាសធំដើរថយក្រោយ។ ក្នុងល្បែងឥតខ្ចោះ ថាសធំបំផុតផ្លាស់ទីតែម្ដងគត់ ថាសធំទីពីរពីរដងគត់។ បើថាសធំណាមួយទៅៗមកៗ ផែនការរបស់អ្នកខុសហើយ — ត្រឡប់ក្រោយ ហើយរៀបចំឡើងវិញ។
- រៀននៅកម្រិតងាយ យកមេដាយនៅកម្រិតពិបាក។ បួនថាស (15 ជំហាន) បង្រៀនលំនាំពេញលេញក្នុងមួយនាទី។ ចង្វាក់ដដែល — គ្មានល្បិចថ្មី — ដោះស្រាយប្រាំមួយថាសក្នុង 63 ជំហាន និងប្រាំបីក្នុង 255។ ល្បឿនមកពីចង្វាក់ មិនមែនការប្រញាប់ទេ។
សំណួរញឹកញាប់
តើពិន្ទុត្រូវបានគណនាយ៉ាងដូចម្ដេច?
ពិន្ទុ = 10,000 − វិនាទីដែលកន្លងផុត − (ជំហានរបស់អ្នក − ជំហានល្អបំផុត) × 10 ដោយអប្បបរមា 1 និងកំពូល 99,999។ ជំហានខ្ជះខ្ជាយនីមួយៗកាត់ 10 ពិន្ទុ ហើយមួយវិនាទីកាត់ 1 ដូច្នេះភាពត្រឹមត្រូវសំខាន់ជាងល្បឿនសុទ្ធប្រហែលដប់ដង។ ការដោះស្រាយឥតខ្ចោះភ្លាមៗនឹងបានពិន្ទុ 10,000។ ពិន្ទុត្រូវបានបញ្ជូនពេលអ្នកបញ្ចប់ប៉ម ហើយពិន្ទុល្អបំផុតតាមកម្រិតនីមួយៗបង្ហាញលើក្ដារពិន្ទុ ពេលអ្នកចូលគណនី។
តើចំនួនជំហានអប្បបរមាប៉ុន្មាន?
2^n − 1 គត់សម្រាប់ n ថាស — 15 ជំហាននៅកម្រិតងាយ (4 ថាស) 63 នៅមធ្យម (6 ថាស) និង 255 នៅពិបាក (8 ថាស)។ នេះជាអប្បបរមាគណិតវិទ្យាដែលបានបញ្ជាក់៖ ថាសធំបំផុតអាចផ្លាស់ទីបានតែពេលថាសតូចជាង n−1 ត្រូវបានចតនៅបង្គោលបម្រុងតែមួយ ដែលការធ្វើដូច្នេះខ្លួនឯងត្រូវការយ៉ាងហោច 2^(n−1) − 1 ជំហានទាំងមុននិងក្រោយ។ ឧបករណ៍រាប់ជំហានបង្ហាញតម្លៃល្អបំផុតនេះក្បែរចំនួនរបស់អ្នកពេញមួយល្បែង។
តើកម្រិតលំបាកផ្លាស់ប្ដូរអ្វីខ្លះ?
ផ្លាស់ប្ដូរតែចំនួនថាសប៉ុណ្ណោះ៖ ងាយ 4 មធ្យម 6 ពិបាក 8។ ច្បាប់មិនដែលផ្លាស់ប្ដូរទេ។ អ្វីដែលផ្លាស់ប្ដូរយ៉ាងខ្លាំងគឺប្រវែងដំណោះស្រាយឥតខ្ចោះ — ថាសបន្ថែមនីមួយៗធ្វើឱ្យវាកើនទ្វេដងបូកមួយ — និងការផ្ចង់អារម្មណ៍ដែលត្រូវការ ដើម្បីចាំកន្លែងខ្លួនក្នុងលំនាំដោយមិនខ្ជះខ្ជាយជំហាន។
តើរឿងប្រាសាទជាមួយថាស 64 ពិតឬទេ?
វាជារឿងព្រេងផ្សព្វផ្សាយដែល Édouard Lucas អ្នកបង្កើតល្បែងផ្គុំ សរសេរដោយខ្លួនឯង ពេលវាចាប់ផ្ដើមលក់ក្នុងឆ្នាំ 1883 — គ្មានប្រាសាទបែបនោះទេ។ ប៉ុន្តែលេខនព្វន្ធក្នុងរឿងគឺពិត៖ ការផ្លាស់ទីថាស 64 ត្រូវការ 2^64 − 1 ជំហាន ហើយក្នុងល្បឿនមួយជំហានក្នុងមួយវិនាទី នោះគឺប្រហែល 585 ពាន់លានឆ្នាំ។ រឿងនេះនៅគង់វង្ស ព្រោះវាជាការបង្ហាញកំណើនអិចស្ប៉ូណង់ស្យែលដ៏រស់រវើកបំផុតដែលធ្លាប់ភ្ជាប់នឹងប្រដាប់ក្មេងលេងមួយ។
តើលេងក្រៅបណ្ដាញបានទេ?
បាន។ ពេលទំព័របានផ្ទុករួច អ្វីៗទាំងអស់ — បង្គោល ការផ្ទៀងផ្ទាត់ជំហាន ឧបករណ៍រាប់ និងនាឡិកា — ដំណើរការទាំងស្រុងក្នុងកម្មវិធីរុករករបស់អ្នកដោយគ្មានអ៊ីនធឺណិត។ ពិន្ទុដែលទទួលបានពេលក្រៅបណ្ដាញត្រូវរក្សាទុកលើឧបករណ៍ ហើយផ្ទុកឡើងដោយស្វ័យប្រវត្តិពេលអ្នកតភ្ជាប់ម្ដងទៀត បើអ្នកបានចូលគណនី។