Map folding
કાગળના ફોલ્ડિંગના ગણિતમાં, નકશાના ફોલ્ડિંગ અને સ્ટેમ્પ ફોલ્ડિંગ એ કાગળના ટુકડાને ફોલ્ડ કરી શકાય તેવી રીતોની સંખ્યાની ગણતરીની બે સમસ્યાઓ છે. સ્ટેમ્પ ફોલ્ડિંગ સમસ્યામાં, કાગળ એ સ્ટેમ્પની એક પટ્ટી છે જેની વચ્ચે ક્રીઝ હોય છે, અને ફોલ્ડ્સ ક્રીઝ પર હોવા જોઈએ. નકશાની ફોલ્ડિંગ સમસ્યામાં, કાગળ એક નકશો છે, જે ક્રીઝ દ્વારા લંબચોરસમાં વહેંચાયેલો છે, અને ફોલ્ડ્સ ફરીથી ફક્ત આ ક્રીઝ સાથે જ હોવા જોઈએ. સ્ટેમ્પ ફોલ્ડિંગ સમસ્યાની શોધનો શ્રેય એમિલ લેમોઇનને આપે છે. કેટલાક અન્ય પ્રારંભિક સંદર્ભો પૂરા પાડે છે. લેબલવાળી સ્ટેમ્પ્સ સ્ટેમ્પ ફોલ્ડિંગ સમસ્યામાં, ફોલ્ડ કરવા માટેનું કાગળ ચોરસ અથવા લંબચોરસ સ્ટેમ્પ્સની પટ્ટી છે, જે ક્રીઝ દ્વારા અલગ પડે છે, અને સ્ટેમ્પ્સને ફક્ત તે ક્રીઝ સાથે ફોલ્ડ કરી શકાય છે. સમસ્યાના એક સામાન્ય રીતે માનવામાં આવતા સંસ્કરણમાં, દરેક ટપાલ ટિકિટને એકબીજાથી અલગ પાડી શકાય તેવું માનવામાં આવે છે, તેથી ટપાલ ટિકિટની પટ્ટીના બે ફોલ્ડિંગને ત્યારે જ સમકક્ષ ગણવામાં આવે છે જ્યારે તેમની પાસે ટપાલ ટિકિટનો સમાન ઊભી ક્રમ હોય. ઉદાહરણ તરીકે, ત્રણ જુદી જુદી ટપાલ ટિકિટોની પટ્ટીને ફોલ્ડ કરવાની છ રીતો છેઃ તેમાં ટપાલ ટિકિટના તમામ છ ક્રમચયો શામેલ છે, પરંતુ ત્રણથી વધુ ટપાલ ટિકિટો માટે તમામ ક્રમચયો શક્ય નથી. જો, ક્રમચય માટે, બે સંખ્યાઓ હોય અને સમાન સમાનતા સાથે ચાર સંખ્યાઓ,, અને તે ચક્રીય ક્રમમાં દેખાય, તો તેને ફોલ્ડ કરી શકાતી નથી. સમાનતા શરત સૂચવે છે કે સ્ટેમ્પ્સ અને, અને સ્ટેમ્પ્સ અને વચ્ચેની ક્રીઝ ફોલ્ડેડ સ્ટેમ્પ્સના સ્ટેકની એક જ બાજુ દેખાય છે, પરંતુ ચક્રીય ક્રમની સ્થિતિ સૂચવે છે કે આ બે ક્રીઝ એકબીજાને પાર કરે છે, જે એક ભૌતિક અશક્યતા છે. દાખલા તરીકે, ચાર-તત્વ ક્રમચય 1324 ને ફોલ્ડ કરી શકાતો નથી, કારણ કે તેમાં અને સાથે આ પ્રતિબંધિત પેટર્ન છે. આ પેટર્ન વિના બાકી રહેલા તમામ ક્રમચયોને ફોલ્ડ કરી શકાય છે. ટપાલ ટિકિટની પટ્ટીને ફોલ્ડ કરવાની વિવિધ રીતોની સંખ્યા ક્રમ 1,2,6,16,50,144,462,1392,4536,14060,46310,146376,485914,1557892,5202690, દ્વારા આપવામાં આવી છે. આ સંખ્યાઓ હંમેશા આ રીતે વિભાજીત થાય છે (કારણ કે ફોલ્ડેબલ સ્ટેમ્પ સિક્વન્સનું ચક્રીય ક્રમચય હંમેશા ફોલ્ડેબલ હોય છે), અને આ ડિવિઝનના ભાગાકાર 1,1,2,4,10,24,66,174,504,1406,4210,12198,37378,111278,346846,1053874 છે, જે ટોપોલોજીકલ રીતે અલગ અલગ રીતોની સંખ્યા છે જે અર્ધ-અનંત વળાંક રેખા સાથે ક્રોસિંગ કરી શકે છે, જેને "સેમીમેન્ડર્સ" કહેવાય છે. આ મીન્ડર્સ સાથે નજીકથી સંબંધિત છે, જે બંધ વળાંક માટે એક રેખા સાથે સમાન સંખ્યામાં ક્રોસિંગ કરવાની રીતો છે. મીન્ડર્સ સ્ટેમ્પ-ફોલ્ડિંગ સમસ્યાના ઉકેલોને અનુરૂપ છે જેમાં પ્રથમ અને છેલ્લી સ્ટેમ્પને એકબીજા સાથે જોડી શકાય છે જેથી સ્ટેમ્પની સતત લૂપ બનાવી શકાય. 1960ના દાયકામાં, જ્હોન ઇ. કોહલર અને ડબલ્યુ. એફ. લુનને એલ્ગોરિધમ્સ અમલમાં મૂક્યા હતા, જે તે સમયે 28 ટપાલ ટિકિટો માટે આ સંખ્યાઓની ગણતરી કરી શકતા હતા. વધારાના સંશોધન છતાં, આ સંખ્યાઓની ગણતરી માટેની જાણીતી પદ્ધતિઓ ના કાર્ય તરીકે ઘાતાંકીય સમય લે છે. આમ, કોઈ સૂત્ર અથવા કાર્યક્ષમ અલ્ગોરિધમ જાણીતું નથી કે જે આ ક્રમને ખૂબ મોટા મૂલ્યો સુધી વિસ્તૃત કરી શકે. તેમ છતાં, આ ક્રમની ઘાતાંકીય વૃદ્ધિના દરની આગાહી કરવા માટે ભૌતિકશાસ્ત્રની સંશોધનાત્મક પદ્ધતિઓનો ઉપયોગ કરી શકાય છે. સ્ટેમ્પ ફોલ્ડિંગ સમસ્યા સામાન્ય રીતે સ્ટેમ્પની પટ્ટીની સંભવિત ફોલ્ડિંગ સ્થિતિઓની સંખ્યાને ધ્યાનમાં લે છે, તે ધ્યાનમાં લીધા વિના કે શું સ્ટેમ્પની ખુલ્લી પટ્ટીથી શરૂ થતી ચાલના ક્રમ દ્વારા ભૌતિક રીતે ફોલ્ડનું નિર્માણ કરવું શક્ય છે કે કેમ. જો કે, સુથારની નિયમ સમસ્યાના ઉકેલ અનુસાર, દરેક ફોલ્ડેડ સ્થિતિનું નિર્માણ કરી શકાય છે (અથવા સમકક્ષ રીતે, અનફોલ્ડ કરી શકાય છે). અનલેબલ્ડ સ્ટેમ્પ્સ સ્ટેમ્પ ફોલ્ડિંગ સમસ્યાના અન્ય પ્રકારમાં, સ્ટેમ્પની પટ્ટી ખાલી માનવામાં આવે છે, જેથી તેનો એક છેડો બીજાથી અલગ કરી શકાય નહીં, અને બે ફોલ્ડિંગ્સ ત્યારે જ અલગ ગણવામાં આવે છે જ્યારે તેમના આકાર અલગ હોય. ફોલ્ડ કરેલી પટ્ટીને ઊંધી-નીચે અથવા પાછળ-થી-સામે ફેરવવાથી તેનો આકાર બદલાતો હોવાનું માનવામાં આવતું નથી, તેથી ત્રણ સ્ટેમ્પમાં માત્ર બે ફોલ્ડિંગ હોય છે, એક એસ-કર્વ અને એક સર્પાકાર. વધુ સામાન્ય રીતે, આ વ્યાખ્યા સાથે ફોલ્ડિંગની સંખ્યા 1,1,2,5,14,38,120,353,1148,3527,11622,36622,389560,1301140,4215748, છે. નકશાના નકશાના ફોલ્ડિંગ એ પ્રશ્ન છે કે લંબચોરસ નકશાને તેની ક્રીઝ સાથે કેટલી રીતે ફોલ્ડ કરવો, દરેક ક્રીઝને પર્વત અથવા ખીણની ગડી બનાવવાની મંજૂરી આપે છે. તે સ્ટેમ્પ ફોલ્ડિંગથી અલગ છે કારણ કે તેમાં માત્ર એક જ દિશામાં ક્રીઝને બદલે ઊભી અને આડી બંને ક્રીઝનો સમાવેશ થાય છે. નકશાને ફોલ્ડ કરવાની એક અલગ રીત તરીકે ફોલ્ડ કરેલા ચોરસના દરેક જુદા જુદા ઊભી ક્રમની ગણતરી કરીને, તેની ક્રીઝ સાથે 2×2 નકશાને ફોલ્ડ કરવાની આઠ રીતો છેઃ જો કે, નકશાને ફોલ્ડ કરવાની રીતોની સંખ્યાની ગણતરીની સામાન્ય સમસ્યા ઉકેલાઈ નથી. નકશાને ફોલ્ડ કરવાની રીતોની સંખ્યા માત્ર આના માટે જાણીતી છે. તેઓ છેઃ 1,8,1368,300608,186086600,123912532224,129950723279272. જટિલતા નકશાના ફોલ્ડિંગ અને સ્ટેમ્પ ફોલ્ડિંગની સમસ્યાઓ ઓરિગામિના ગણિતમાં એક સમસ્યા સાથે સંબંધિત છે કે શું ક્રીઝ પેટર્નવાળા ચોરસને સપાટ આકૃતિમાં ફોલ્ડ કરી શકાય છે કે કેમ. જો સ્ટેમ્પની પટ્ટીની દરેક ક્રીઝને ફોલ્ડિંગ દિશા (કાં તો પર્વતની ગડી અથવા ખીણની ગડી) સોંપવામાં આવે, તો તે ચકાસવું શક્ય છે કે પરિણામ બહુપદી સમયમાં સપાટ ફોલ્ડ કરી શકાય છે કે કેમ. નકશા પર સમાન સમસ્યા માટે (નિયુક્ત દિશાઓ સાથે ક્રીઝ દ્વારા લંબચોરસમાં વિભાજિત) તે અજ્ઞાત છે કે બહુપદી સમય ફોલ્ડિંગ અલ્ગોરિધમ સામાન્ય રીતે અસ્તિત્વમાં છે કે કેમ, જો કે બહુપદી અલ્ગોરિધમ નકશા માટે જાણીતું છે. પ્રતિબંધિત કિસ્સામાં જ્યાં નકશાને "સરળ" ફોલ્ડ્સના ક્રમ દ્વારા ફોલ્ડ કરવામાં આવે છે, જે કાગળને એક જ લીટી સાથે ફોલ્ડ કરે છે, ત્યાં સમસ્યા બહુપદી છે. સમસ્યાના કેટલાક વિસ્તરણ, ઉદાહરણ તરીકે કાગળની બિન-લંબચોરસ શીટ્સ, એન. પી.-પૂર્ણ છે. એક-પરિમાણીય ટપાલ ટિકિટની પટ્ટી માટે પણ, તેની ક્રીઝને પહેલેથી જ પર્વત અથવા ખીણની ફોલ્ડ્સ તરીકે લેબલ કરવામાં આવી છે, તેને ફોલ્ડ કરવાનો રસ્તો શોધવો એન. પી.-મુશ્કેલ છે જે કોઈપણ ક્રીઝની બે ટપાલ ટિકિટ વચ્ચેની મહત્તમ સંખ્યાને ઘટાડે છે. નિયમિત પેપરફોલ્ડિંગ ક્રમ પણ જુઓ, 0s અને 1s નો અનંત ક્રમ જે સ્ટેમ્પ્સની ફોલ્ડિંગ સ્ટ્રીપ્સની એક રીતનું વર્ણન કરે છે સંદર્ભો વોલ્ફ્રમ ડેમોન્સ્ટ્રેશન પ્રોજેક્ટઃ http://demonstrations.wolfram.com/FoldingAStripOfLabeledStamps પેપર ફોલ્ડિંગ ગણિતમાં વણઉકેલાયેલી સમસ્યાઓમાંથી બાહ્ય લિંક્સ "ફોલ્ડિંગ એ સ્ટ્રીપ ઓફ લેબલ્ડ સ્ટેમ્પ્સ"