مساله وزنه ها ، بحث تاريخي..

[پين]

اين تاپيك در دنباله تاپيك زير است و از دوستاني كه تازه به اين بحث
افزوده شده اند، مي خواهم كه مقدمات را دراين تاپيك بخوانند:
http://hupaa.com/forum/viewtopic.php?f=16&t=3481

من اين نوشته را در چند بخش(شبي چند سطر ) دنبال مي كنم
---------------------------------------------------------------------------

بخش اول

گاسپارد باشه (Gaspard Bachet)* ، در قرن شانزدهم پرسش مشهور خود را مطرح
كرد كه همان يافتن كمترين تعداد وزنه (و مقدارشان) براي كشيدن وزنه هاي بين
1 تا 40 كيلويي با ترازوي دو كفه اي بود .

مساله او دو حالت داشت :
الف) وزنه ها فقط بتوانند روي يك كفه قرار بگيرند .
ب) وزنه ها بتوانند روي هر دو كفه قرار بگيرند .

وي براي مساله اول ، پاسخ [1-2-4-8-16-32] و براي مساله دومش، پاسخ [1-3-9-27]
را پيشنهاد كرد كه البته تارتاگليا (Nicolo fontana Tartaglia )** قبل تر از او و در قرن پانزدهم،
مساله حالت الف را با همين پاسخ حل كرده بود .

استدلال آنان (چنانكه در تاپيك پيشين بحث شد) مبتني بر استفاده از مبناهاي 2 و 3 بود
اما مشكل آنجاست كه روش آنها تضميني بر يكتايي پاسخها نمي دهد . مساله را در حالت
ب در نظر بگيريد ، به عنوان مثال ، با استفاده از روش مبنا ها ميتوان دريافت كه براي كشيدن
وزنه هاي 1تا 10 كيلويي ، داشتن 3 وزنه به وزنه هاي [1-3-9] كفايت ميكند اما اين پاسخ
يكتا نيست و پاسخهايي نظير [1-3-6] يا [1-2-7] يا [2-3-7] نيز وجود دارند :

اين بدان معنا نيست كه همواره پاسخها غيريكتا هستند اما چرا با استفاده از روش مبناها ،
همه پاسخها معلوم نمي شوند ؟ پاسخي كه گاسپارد باشه حساب كرد ، چه تفاوتي با ديگر
پاسخها دارد؟ در واقع روش باشه و تارتاگيا مي بايست حالت خاصي از روش كلي تري باشد
كه آن روش داراي محدوديتها و شرايطي است . براي يافتن آن شرايط ، ما داستان اين مساله و
نتايجش را پله پله تا قرن نوزدهم دنبال ميكنيم .

در سال 1669 ، لايب نيتز طي نامه اي از يوهان برنولي جويا ميشود كه آيا او به اين موضوع انديشيده
كه يك عدد صحيح را به چند طريق ميتوان با اعداد صحيح كوچكتر يا مساوي (يعني تنها با استفاده از
عمل جمع) ساخت .او همچنين متذكر ميشود كه اين مساله اي دشوار اما بسيار مهم است.

Filip Naude درسال 1740 ، دو پرسش مشابه را براي اويلر فرستاد:
پرسش اول: به چند طريق ميتوان يك عدد را از طريق جمع اعدادي متمايز نوشت؟
پرسش دوم: به چند طريق ميتوان يك عدد را از طريق جمع اعداد نوشت؟
اويلر هر دو پرسش را با استفاده از توابع مولد ( Generating functions ) و بسي هوشمندانه حل كرد
كه امروزه ما روش وي را به "قضيه افراز يا partitioning" مي شناسيم .
براي پرسش اول ، اويلر از تابع زير استفاده كرد:

و استدلال كرد كه ضريب عبارت x^n در تساوي فوق، برابر با تعداد روشهايي است كه عدد n را ميتوان
به كمك اعداد متمايز و كمتر يا مساوي با خودش ساخت . مثلا با باز كردن طرف راست تساوي فوق
(تا 6 پرانتز) ، معلوم ميشود كه ضريب x^6 برابر 4 است كه اين نتيجه جمع چهار عبارت زير است:

و اين به آن معناست كه 6 را ميتوان به 4 طريق (با اعداد كوچكتر يا مساوي و نيز متمايز) نوشت

اكنون واضح است كه اويلر براي پرسش دوم از تابع زير استفاده مي كند:

كه با استفاده از تصاعد حسابي برابر ميشود با:

كه اگر طرف چپ تساوي را لااقل تا 7 باز كنيم ، به دست مي آيد:

پس با توجه به ضرايب نتيجه مي گيريم كه در حالت دوم (نداشتن شرط تمايز عاملها)، عدد 7
را ميتوان به 15 طريق و عدد 6 را به 11 طريق ساخت :

اويلر باز هم پا را فراتر نهاد و پاسخ را براي حالتهايي كه تمام عاملها "زوج" يا "فرد" يا "مربع كامل"
باشند نيز به روشي تحسين برانگيز ارائه كرد :

او با استفاده از همين توابع ساده ، قضاياي بسيار زيبا را به روشي بسيار زيبا ثابت كرد . براي مثال
نشان داد كه روش هاي ساختن عدد n بطوريكه عاملهايش فرد باشند (و نه الزاما متمايز) ، دقيقا
برابر است با حالتي كه عاملها متمايز باشند .(كه به قضيه odd-distinct مشهور است)
فرصت نيست كه بيشتر روي اين قسمت مانور دهيم . علاقه مندان ميتوانند اطلاعات كاملتري درباره
روش اويلر را در لينكهاي زير بيابند :
http://olympiad.roshd.ir/computer/content/pdf/0052.pdf
http://en.wikipedia.org/wiki/Integer_pa ... g_function

اينجا اويلر را تنها مي گذاريم و كمي آنسوتر مي رويم ، به اواسط قرن هجدهم و جايي كه دو دانشمند
آلماني ، با الهام از روش اويلر ، بار ديگر مساله وزنه هاي گاسپارد باشه را به طريقي ديگر حل
مي كنند ....
*
http://en.wikipedia.org/wiki/Claude_Gas ... 3%A9ziriac

**
http://en.wikipedia.org/wiki/Niccol%C3% ... _Tartaglia


ادامه دارد

[پين]

موريس كانتور (Moritz cantor ) در سال 1875 و در شماره بيستم نشريه
Zeitschrift für Mathematik und Physik مي نويسد كه در يك مغازه ويژه
فروش سرگرمي ها ، يك بازي به نام "سن شما چقدر است؟" به فروش
ميرسد كه توجه و حيرت او را برانگيخته . وي شرح ميدهد كه آن بازي شامل
7 دسته كارت است كه اعدادي روي آنها (بين 1 تا100 ) نوشته شده. هر
كارت شامل يك كليد (كليدها عبارتند از 1و2و4و8و16و32و64) و هركس بايد
كارتهايي را كه سنش روي آنها باشد را از ميان آن 7 كارت برگزيند و به
شعبده باز دهد و او سريعا خواهد گفت كه سن شركت كننده چقدر بوده.
اين بازي آشنا را ميتوانيد در تاپيك زير پيدا كنيد:
http://hupaa.com/forum/viewtopic.php?f=16&t=5767

كانتور آن بازي را بررسيد و به نتايجي مشابه تارتاگليا و bachet رسيد .
او استدلال مي كند كه كه اعداد بين 1 تا 100 ، در سيستم باينري حداكثر
شامل 7 رقم هستند پس حداكثر 7 كارت براي اين بازي كفايت ميكند .
پس هر عدد بين 1 تا 100 (يا هر عدد بين 1تا 127 ) را ميتوان با تركيب 7 تا از
توانهاي 2 (همان 7 كليد) توليد كرد .
در شماره بعدي (شماره 21) همان نشريه ، فليكس مولر (Felix Muller ) روش
ديگري را براي اين مساله (كه همان مساله "الف" گاسپارد باشه است ) نشان
ميدهد. او آن دو مساله را با دو اتحاد جبري اثبات مي كند .

روش او مبتني بر روشي است كه پيشتر اويلر در Introducto in ana lysin infinitorum
بكار بسته بود (استفاده از تابع مولد) . دانستيم كه ضرايب x^n نماينده تعداد روشهاي
ممكن براي ساختن n است او فرض كرد كه هر عدد را تنها به يك طريق بتوان ساخت
پس ضريب تمام اعداد را برابر واحد در نظر گرفت و n را نيز ،براي نمونه، 127 قرار داد :

سپس طرف راست كسر را بصورت حاصلضرب چندين كسر متوالي در مي آورد:

كه با اتحاد مزدوج به دست مي آيد:

چنانچه پرانتز هاي طرف راست در يكديگر ضرب شوند ، با همان استدلال اويلر
مي توان به سادگي دريافت كه هركدام از توانهاي 1 تا 127 ، به كمك مجموعه اي
"يكتا" از اعداد 1و2و4و8و16و32و64 قابل ساخته شدن است .
بنابر اين او مساله نخست bachet را نه با تغيير مبنا بلكه بوسيله يك اتحاد جبري
حل كرده بود.

مولر كار را براي حل مساله دوم (حالتي كه وزنه ها بتوانند روي هر دو كفه
قرار بگيرند ) ادامه مي دهد و اين بار نيز از تابع مولد براي حصول يك اتحاد جبري
بهره مي گيرد .
براي اين كار ، او n را برابر تواني از 3 در نظر مي گيرد تا كسرها پس از ساده شدن ،
به نتيجه دلخواه برسند :

كه با ساده كردن هركدام از كسرهاي سمت راست ، به دست مي آيد:

تا اينجاي كار ،مشابه حالت پيشين بود. حال اگر دو طرف تساوي بر x^k تقسيم
شود خواهيم داشت:

و اتحاد جبري ديگري حاصل شد و اينبار از آن نتيجه ميشود كه هر عدد بين k و –k
را ميتوان با تركيبي از توانهاي 3 (هم مثبت و هم منفي) و بطور يكتا ساخت كه
همان حل مساله دوم گاسپارد باشه است .

نقش كارهاي مولر و كانتور در اين ميان به همينجا ختم ميشود اما 10 سال بعد ،
دانشمند ديگري در شماره 21 نشريه Quarterly jurnal of mathematics آتش ديگري
در اين خرمن مي زند .وي بعدها بر پايه نظرات اويلر ، مولر، رامانوجا ،سيلوستر ، و...
كتابي دو جلدي نگاشت و راه حل مساله را توسيع داد.
او كسي نبود جز الكساندر مك ماهون (Percy Alexander MacMahon ) ....

ادامه دارد

[metra70]

با سلام
من يه سوال داشتم؟
ما مي تونيم براي اين مسئله اين الگوريتم كلي را در نظر بگيريم مثلا بگيم اگه وزنه ما دو كفه داشت و ما اجازه داشته باشيم وزنه را به دلخواه وزنه ها را روي آن قرار دهيم براي بررسي جواب داشتن مسئله از اين جملات استفاده كنيم (هرگاه بتوانيم مجموع ويا تفريق وزنه ها به عدد مورد نظر برسانيم ويا جزو مضرب هاي آنان باشد در اينصورت مسئله قابل حل شدن است)
در ترازوي سه كفه (ابولفتح خازني) با زواياي نامشخص هر گاه بتوانيم جذر مجموع مربعات به اضافه زاويه بين دو به دوي آنها با در حاصل ضرب آنها را بدست بياوريم جزو مضرب هاي عدد مورد نظر ما باشد
در يك كفه هم فقط بتوانيم از مضرب ها استفاده كنيم

[پين]

من يه سوال داشتم؟
ما مي تونيم براي اين مسئله اين الگوريتم كلي را در نظر بگيريم مثلا بگيم اگه وزنه ما دو كفه داشت و ما اجازه داشته باشيم وزنه را به دلخواه وزنه ها را روي آن قرار دهيم براي بررسي جواب داشتن مسئله از اين جملات استفاده كنيم (هرگاه بتوانيم مجموع ويا تفريق وزنه ها به عدد مورد نظر برسانيم ويا جزو مضرب هاي آنان باشد در اينصورت مسئله قابل حل شدن است)
در ترازوي سه كفه (ابولفتح خازني) با زواياي نامشخص هر گاه بتوانيم جذر مجموع مربعات به اضافه زاويه بين دو به دوي آنها با در حاصل ضرب آنها را بدست بياوريم جزو مضرب هاي عدد مورد نظر ما باشد
در يك كفه هم فقط بتوانيم از مضرب ها استفاده كنيم

درود
مسئله از ابتدا در حالت كلي بود اما بحث بر سر روش هاي حل است .
و اينكه كدام روش به چه پاسخهايي ميرسد و به چه پاسخهايي نميرسد
(و چرا).

دررياضيات گسسته البته تشخيص آنكه كدام مسئله جزيي و كدام كلي
است ، كار آساني نيست . مثلا نمونه ديگر اين پرسش(كه نميتوان گفت
كه حالت كلي تر است يا جزيي تر!) چنين است:

فرض كنيد به حالتي محدود شويم كه در هر توزين ، تنها اختيار استفاده
از يك يا دو وزنه (با اين شرط كه روي يك كفه نباشند ) را داشته باشيم .
در واقع ، هر عدد را بايد فقط با تفاضل دو وزنه يافت كه اين همان مساله
خط كش تام (perfect ruler ) است:
http://mathworld.wolfram.com/PerfectRuler.html

----------------------------------------------------------
*درباره سرنوشت خازني:
http://www.ghiasabadi.com/khazeni.html

[metra70]

ممنون از پاسختون

[پين]

چنانكه گفتيم . الكساندر مك ماهون را امروزه به عنوان كسي مي شناسند كه
مساله bachet را در حالت كلي مطرح كرد . البته اين به معناي حل كامل مسئله
نيست ولي او پنجره اي را گشود كه ديد تازه و قدرتمندي براي حل اين مساله
مي دهد . مرسوم شده است كه با روش كلاسيك (تغيير مبنا) ، پاسخ بهينه بدست
مي آيد اما بهينه بودن هنگامي معنا دارد كه قادر به يافتن پاسخهاي غير بهينه نيز
باشيم.
مك ماهون شرط اصلي مساله را در نظر گرفت (يعني بتوان هر عدد از 1 و حداكثر تا n
را ساخت ) اما روشي را پيشنهاد داد كه بتوان تمام پاسخها (حتي آنان كه بهينه
نيستند ) را يافت. در نگاه اول شايد يافتن پاسخهاي غير بهينه اتلاف وقت به نظر برسد
اما خواهيم ديد كه ديدگاه او، راه را براي يافتن پاسخهاي بهينه هم هموار مي كند.

براي مثال ، او نشان داد كه در حالت n=40 ، علاوه بر پاسخ بهينه [1,3,9,27] ، 7
دسته پاسخ غير بهينه نيز وجود دارند كه در آنها البته وزنه هاي تكراري نيز وجود دارند
(تعداد وزنه ها بيش از چهار است و لذا بهينه نيستند) اما نكته مهم آنجاست كه آن
هفت پاسخ را به روش كلاسيك( تغيير مبنا )، نميتوان يافت.
مثلا بدون محاسبه واضح است 40 وزنه يك كيلو گرمي نيز ميتواند جزو پاسخها باشد
(زيرا حداقل از 1 و حداكثر تا 40 كيلو گرمي را ميتوان با آنها توزين كرد) . اما 6 پاسخ
ديگر كدامند؟

مك ماهون درست از نقطه اي شروع كرد كه دكتر مولر پايان داده بود( دو اتحاد مولر
را به ياد آوريد) . او استدلال كرد كه تعداد پاسخها در حالت كلي ، برابراست با تعداد
حالتي كه ميتوان اتحاد مولر را تجزيه كرد. براي روشن شدن بحث ، تمام 8 پاسخ را
اينجا محاسبه ميكنيم . اما پيش از آن ، چند يادآوري:

1- مجموع تصاعد حسابي از x^-n تا x^n و با قدر نسبت x برابر است با :

2- و بطور مشابه ، مجموع تصاعد حسابي از x^-ma تا x^ma و با قدر نسبت x^a
برابر ميشود با:

*كمي جلوتر معلوم خواهد شد كه a نماينده مقدار وزنه
و m نماينگر تعداد تكرار خواهد بود .

در اتحاد دوم مولر (براي n=40 ) داشتيم كه :

اما طرف راست تساوي فوق را به 8 طريق ميتوان تجزيه كرد:

طريق اول : تجزيه به حاصلضرب چهار كسر:

با مقايسه اين چهار كسر با اتحادي كه در ابتداي اين پست آورده شد ،
معلوم ميشود كه در همه آنها m=1 و a=1,3,9,27 است كه اين نماينده
همان پاسخ كلاسيك است : [1,3,9,27]

طريق دوم: تجزيه به حاصلضرب سه كسر:

در كسر اول داريم : a=27 , m=1 كه يعني يك وزنه 27 كيلويي
در كسر دوم داريم: a=9 , m=1 كه يعني يك وزنه 9 كيلويي
در كسر سوم داريم: a=1 , m=4 كه يعني 4 وزنه يك كيوگرمي
پس يكي ديگر از پاسخها خواهد بود : [1,1,1,1,9,27]

طريق سوم : تجزيه به حاصلضرب سه كسر:

كه به طريق مشابه يعني: يك وزنه 27 كيلويي و چهار وزنه 3 كيلويي و
يك وزنه 1 كيلويي : [27,3,3,3,3,1]

طريق چهارم:تجزيه به حاصلضرب دو كسر:

كه نماينده 13 وزنه يك كيلوگرمي و يك وزنه 27 كيلويي است.

طريق پنجم: تجزيه به حاصلضرب سه كسر:

يعني چهار وزنه 9 كيلويي و يك وزنه سه كيلويي و يك وزنه يك كيلويي

طريق ششم: تجزيه به حاصلضرب دو كسر:

يعني چهار وزنه يك كيلويي و 4 وزنه 9 كيلويي

طريق هفتم:تجزيه به حاصلضرب دو كسر:

يعني 13 وزنه 3 كيلويي و يك وزنه يك كيلويي.

و در نهايت ، طريق هشتم كه بدون تجزيه است:

كه همان پاسخ بديهي است (40 وزنه يك كيلويي)

تمام اين 8 پاسخ ، خاصيت هاي زير را دارند:
-با آنها ميتوان وزنه هاي 1 تا 40 كيلويي –و نه بيشتر از آن- را توزين كرد
-هر وزنه تنها به يك طريق قابل توزين است ( با وزنه هاي غير مساوي)

مك ماهون ازاين طريق نشان داد كه راه حل مسئله bachet در حالت كلي مترادف
با تجزيه يك اتحاد جبري است و تمام ابزار كافي براي رسيدن به پاسخ را در اختيار
مي گذارد .از اين رو مشهور است كه او روش كلاسيك را كليت داده.

مثلا (و به عنوان آخرين مثال) ، فرض كنيد به دنبال يافتن وزنه هايي هستيم كه
بتوان با آنها مقادير از 1 تا 10 كيلو گرم را توزين نمود بطوريكه هر مقدار را تنها بتوان
به يك طريق اما وزنه هاي 1 و 6 و 8 كيلويي را بتوان از 2طريق توزين نمود .

براي حل چنين مساله اي ، روش تغيير مبنا راهگشا نيست . اما از روش كلي داريم:

كه مي توان آن را به فرم زير تجزيه نمود:

و با ساده كردن به دست مي آيد:

يعني به سه وزنه 1و 2 و 7 كيلويي نياز است و اين همان پاسخي است كه در
ابتداي اين تاپيك آورده شد .

[1] P.A MacMahon/Combinatory ana.lysis / Volume1
[2] P.A MacMahon/Combinatory ana.lysis / Volume2
[3] Anton Glaser / History of Binary
[4] James J. Tattersal / Elementary number theory in nine chapter
[5] Rauss Ball / Mathematical recreations and essays
[6] H.L Alder / Partition identities from euler to the present

----------------------------------------------------------------------------------------------------
پي نوشت:
1-در ارتباط با همين پرسش ، مسئله "سه پيمانه و مختصات مثلثي" نيز قابل بررسي است
2-با نگاه به اوضاع فعلي ، چندان دور نيست كه اسپم ها اين تاپيك را نيز في الفور به قعر هوپا
بفرستند اما پيش از آن اميد دارم كه تعدادي از دوستان آن را بخوانند .


-پين-

[PETERAXON]

سپاس از پین عزیز
شاید به ظاهر علائمی از حیات در هوپا نباشد ولی بدانید کسانی هستند که از مطالب شما استفاده کنند هرچند کم رنگند

-------------------------------
اینم از طرف خودم :

[پين]

پيتر عزيز،
من اين مطلب را با چند مقصود شروع كردم . اول آنكه مي دانم
ياراني(همانند شما) در هوپا هستند كه به علاقه و پيگيري شان
نسبت به اينگونه بحث ها ترديد ندارم و اگر هم اين روزها در سايه
باشند، آفتاب در سايه اند.
دوما پيرامون اين موضوع صحبتهايي با استاد خروش داشتيم و مي
خواستم به نوعي بحث را به جايي رسانده باشم .اميدوارم بحثي
درخور تالار رياضي هوپا بوده باشد.
در آخر، اگر اين شيوه مورد توجه دوستداران تالار رياضي قرار بگيرد،
ميتوانند به همين شيوه كارهاي خود را در هوپا بنويسند . از آينده
خبر نداريم، شايد روزي به كار هوپا بيايد (به هر صورت ما خواهيم
رفت اما به قول فردوسي، "سخن ماند از ما همي يادگار" )

اگر دري به تخته خورد و فرصتي گيرم آمد، اين روند را ادامه داده و
بحث تاريخي ديگري را شروع خواهم كرد.

سپاسگزارم

[پين]

تصاویر و روابط ریاضی این بحث، اکنون دیگر در دسترس نیست
و جایگزین کردن مجدد آنان نیز برایم شدنی نیست. بنابراین
فایل اصلی آن را (به درخواست یکی از دوستان) اینجا
می گذارم: