Zeckendorf's theorem
ریاضی میں، زیکنڈورف تھیوریم، جس کا نام بیلجیئم کے شوقیہ ریاضی دان ایڈورڈ زیکنڈورف کے نام پر رکھا گیا ہے، فبونیکی نمبروں کے مجموعے کے طور پر انٹیجرز کی نمائندگی کے بارے میں ایک تھیوریم ہے۔ زیکنڈورف کے نظریہ میں کہا گیا ہے کہ ہر مثبت عدد کو ایک یا زیادہ الگ فبونیکی نمبروں کے مجموعے کے طور پر اس طرح سے منفرد طور پر پیش کیا جا سکتا ہے کہ اس رقم میں کوئی بھی دو مسلسل فبونیکی نمبر شامل نہ ہوں۔ مزید واضح طور پر، اگر کوئی مثبت عدد ہے، تو اس کے ساتھ مثبت عدد موجود ہیں، جیسے کہ فبونیکی نمبر کہاں ہے۔ اس طرح کی رقم کو زیکینڈورف کی نمائندگی کہا جاتا ہے۔ کی فبونیکی کوڈنگ اس کی زیکنڈورف نمائندگی سے حاصل کی جا سکتی ہے۔ مثال کے طور پر، زیکنڈورف کی نمائندگی 64 ہے۔ فبونیکی نمبروں کے مجموعے کے طور پر 64 کی نمائندگی کرنے کے دوسرے طریقے بھی ہیں لیکن یہ زیکنڈورف کی نمائندگی نہیں ہیں کیونکہ 34 اور 21 مسلسل فبونیکی نمبر ہیں، جیسا کہ 5 اور 3 ہیں۔ کسی بھی مثبت عدد کے لیے، اس کی زیکینڈورف کی نمائندگی لالچی الگورتھم کا استعمال کرتے ہوئے، ہر مرحلے پر سب سے بڑے ممکنہ فبونیکی نمبر کا انتخاب کرکے پائی جا سکتی ہے۔ اگرچہ اس تھیوریم کا نام اسی نام کے مصنف کے نام پر رکھا گیا ہے جس نے 1972 میں اپنا مقالہ شائع کیا تھا، یہی نتیجہ 20 سال قبل گیرٹ لیککرکر نے شائع کیا تھا۔ اس طرح، تھیوریم اسٹگلر کے لا آف ایپونیمی کی ایک مثال ہے۔ ثبوت زیکنڈورف کے نظریہ کے دو حصے ہیں: وجود: ہر مثبت عدد میں زیکنڈورف کی نمائندگی ہوتی ہے۔ انفرادیت: کسی بھی مثبت عدد کی دو مختلف زیکنڈورف نمائندگی نہیں ہوتی ہے۔ زیکنڈورف کے نظریہ (وجود) کا پہلا حصہ انڈکشن کے ذریعے ثابت کیا جا سکتا ہے۔ کیونکہ یہ واضح طور پر درست ہے (کیونکہ یہ فبونیکی نمبر ہیں)، کیونکہ ہمارے پاس ہے۔ اگر فبونیکی نمبر ہے تو ثابت کرنے کے لیے کچھ نہیں ہے۔ ورنہ اس طرح موجود ہے. اب فرض کریں کہ ہر مثبت عدد میں زیکنڈورف کی نمائندگی (انڈکشن مفروضہ) ہوتی ہے اور اس پر غور کریں۔ چونکہ، انڈکشن مفروضے کے ذریعہ زیکنڈورف کی نمائندگی ہے۔ ایک ہی وقت میں، (ہم آخری مساوات میں فبونیکی نمبر کی تعریف کا اطلاق کرتے ہیں)، لہذا زیکینڈورف کی نمائندگی پر مشتمل نہیں ہے، اور اس وجہ سے بھی شامل نہیں ہے۔ نتیجے کے طور پر، کی رقم اور زیکنڈورف کی نمائندگی کے طور پر پیش کیا جا سکتا ہے، اس طرح کہ رقم میں شامل فبونیکی نمبر الگ ہیں۔ زیکنڈورف تھیوریم (انفرادیت) کے دوسرے حصے میں مندرجہ ذیل لیما کی ضرورت ہوتی ہے: لیما: مختلف، غیر مسلسل فبونیکی نمبروں کے کسی بھی غیر خالی سیٹ کا مجموعہ جس کا سب سے بڑا ممبر اگلے بڑے فبونیکی نمبر سے سختی سے کم ہے۔ لیما کو انڈکشن آن کرکے ثابت کیا جا سکتا ہے۔ اب دو غیر خالی سیٹ اور الگ الگ غیر مسلسل فبونیکی نمبروں کے سیٹ لیں جن کی رقم ایک جیسی ہو۔ سیٹوں پر غور کریں اور جو برابر ہیں اور جن سے عام عناصر کو ہٹا دیا گیا ہے (یعنی اور)۔ چونکہ اور اس کا مجموعہ برابر تھا، اور ہم نے دونوں سیٹوں سے بالکل عناصر کو ہٹا دیا ہے، اور اس کا مجموعہ بھی ایک ہی ہونا چاہیے۔ اب ہم تضاد کے ساتھ دکھائیں گے کہ کم از کم ایک اور خالی ہے۔ اس کے برعکس فرض کریں، یعنی کہ اور دونوں خالی ہیں اور سب سے بڑا رکن اور سب سے بڑا رکن ہونے دیں۔ کیونکہ اور کوئی مشترکہ عناصر پر مشتمل نہیں ہے۔ عامیت کے نقصان کے بغیر، فرض کریں۔ پھر لیما کے ذریعے، اور، اس حقیقت کے ذریعے کہ، جبکہ واضح طور پر۔ یہ اس حقیقت سے متصادم ہے کہ اور ایک ہی رقم ہے، اور ہم یہ نتیجہ اخذ کر سکتے ہیں کہ یا تو خالی ہونا چاہیے۔ اب فرض کریں (پھر سے عام ہونے کے نقصان کے بغیر) کہ خالی ہے۔ پھر اس کا مجموعہ 0 ہے، اور اسی طرح ہونا چاہیے۔ لیکن چونکہ اس میں صرف مثبت عدد ہو سکتے ہیں، اس لیے اسے خالی بھی ہونا چاہیے۔ نتیجہ اخذ کرنے کے لیے: جس کا مطلب ہے، یہ ثابت کرنا کہ ہر زیکنڈورف کی نمائندگی منفرد ہے۔ فبونیکی ضرب قدرتی اعداد پر مندرجہ ذیل عمل کی وضاحت کی جا سکتی ہے،: زیکنڈورف کی نمائندگی کو دیکھتے ہوئے اور ہم فبونیکی پروڈکٹ کی وضاحت کرتے ہیں۔ مثال کے طور پر، 2 کی زیکنڈورف کی نمائندگی ہے، اور 4 کی زیکنڈورف کی نمائندگی ہے (نمائندگی سے منع ہے)، لہذا (پروڈکٹ ہمیشہ زیکنڈورف کی شکل میں نہیں ہوتا ہے۔ مثال کے طور پر،) رقم کی ایک سادہ ترتیب سے پتہ چلتا ہے کہ یہ ایک تبادلہ عمل ہے ؛ تاہم، ڈونلڈ نوتھ نے حیرت انگیز حقیقت کو ثابت کیا کہ یہ عمل بھی معاون ہے۔ نیگا فبونیکی نمبروں کے ساتھ نمائندگی فبونیکی ترتیب کو دوبارہ ترتیب شدہ تکرار کے تعلق کا استعمال کرتے ہوئے منفی اشاریہ تک بڑھایا جا سکتا ہے جو "نیگا فبونیکی" نمبروں کی ترتیب کو مطمئن کرتا ہے۔ کسی بھی عدد کو منفرد طور پر نیگا فبونیکی نمبروں کے مجموعے کے طور پر پیش کیا جا سکتا ہے جس میں کوئی دو مسلسل نیگا فبونیکی نمبر استعمال نہیں کیے جاتے ہیں۔ مثال کے طور پر: 0 کو خالی رقم سے ظاہر کیا جاتا ہے۔ مثال کے طور پر، تو نمائندگی کی انفرادیت اس شرط پر منحصر ہے کہ کوئی دو مسلسل نیگا فبونیکی نمبر استعمال نہیں کیے جاتے ہیں۔ یہ کوڈنگ انٹیجرز کا ایک نظام فراہم کرتا ہے، جو زیکنڈورف کے نظریہ کی نمائندگی سے ملتا جلتا ہے۔ انٹیجر کی نمائندگی کرنے والے سٹرنگ میں، واں ہندسہ 1 ہے اگر اس رقم میں ظاہر ہوتا ہے جو نمائندگی کرتا ہے ؛ وہ ہندسہ بصورت دیگر 0 ہے۔ مثال کے طور پر، 24 کی نمائندگی سٹرنگ 100101001 سے کی جا سکتی ہے، جس میں 9، 6، 4، اور 1 جگہوں پر 1 ہندسہ ہے، کیونکہ۔ عدد کی نمائندگی عجیب لمبائی کی تار سے کی جاتی ہے اگر اور صرف اگر۔ یہ بھی دیکھیں کہ مکمل ترتیب فبونیکی کوڈنگ فبونیکی نیم آسٹرووسکی عدد حوالہ جات بیرونی روابط زیکنڈورف تھیوریم کٹ-دی-گانٹھ فبونیکی نمبرز تھیوریمز ان نمبر تھیوری ثبوت پر مشتمل مضامین