কম্বিনেটরিক্স গণিত

একেলা দৌড়বিদের কনজেকচার (The Lonely Runner Conjecture)

The Lonely Runner

১.

ধরা যাক, একটা গোল ট্র্যাকে কয়েকজন দৌড়বিদ দৌড়চ্ছে। তারা কে বা কোথা থেকে এসেছেন এটা আপাতত আমাদের কাছে গুরুত্বপূর্ণ নয়, কিন্তু গুরুত্বপূর্ণ বিষয় হচ্ছে যে তাদের সবার বেগ আলাদা। সুতরাং কোন দুইজনের বেগ এক হয়ে গেলেই পুরো আয়োজন ব্যর্থ হয়ে যাবে।

আরও ধরা যাক যতজন দৌড়চ্ছে তাদের সংখ্যা k। আমি আগেই বলেছি কারা কারা দৌড়চ্ছে সেটা কখনও আমাদের কাছে গুরুত্বপূর্ণ নয়। কিন্তু কেউ বাড়তি বিনোদনের জন্য দৌড়বিদদের একটা লিস্ট করে ফেলতে পারে(যেমন: কচ্ছপ, শ্লথ, উসাইন বোল্ট ইত্যাদি)।

ট্র্যাকের দৈর্ঘ্য আমাদের সুবিধের জন্য নেওয়া যেতে পারে এক কিলোমিটার(মানে এক একক)। একেবারে শুরুতে মানে যখন অতিক্রান্ত সময় t=0 তখন সবাই এক জায়গাতে থাকে এবং সংকেত পাওয়ার সাথে সাথে একসাথে দৌড়ানো শুরু করে।

এবার আমাদের কিছু অবাস্তব শর্ত কল্পনা করে নিতে হবে। প্রথমটি হচ্ছে, দৌড়বিদদের বেগ সবসময় একই থাকে, কখনও এক বিন্দু পরিবর্তিত হয় না। দ্বিতীয়ত, দৌড় কখনও শেষ হয় না। অর্থাৎ গোল ট্র্যাকে তারা সবাই সারা জীবনের জন্য দৌড়াতে থাকবে, পুরো এক কিলোমিটার ঘুরে আসার পর আবার দৌড়াতে থাকবে।

যাই হোক, দৌড়াতে দৌড়াতে কোন দৌড়বিদ কখনো কখনো একা হয়ে যেতে পারে। একজন দৌড়বিদ তখনই একা হয়ে যায় যখন তার সবচেয়ে কাছের প্রতিদ্বন্দ্বীর থেকে তার দূরত্ব অন্তত \frac{1}{{\rm{k}}} কিলোমিটার হবে। অর্থাৎ একজন একলা দৌড়বিদের  \frac{1}{{\rm{k}}} দূরত্বের মধ্যে অন্য কেউ থাকবে না।

একলা দৌড়বিদের অনুমান বা Lonely Runner Conjecture (বলে রাখা উচিৎ গণিতে কনজেকচারকেই অনুমান বলে। কনজেকচার হচ্ছে এমন কিছু থিওরি যাদের সন্তোষজনক কোন প্রমাণ পাওয়া যায় নি) বলে যে এমন একটা সময় পাওয়া যাবে যখন ট্র্যাকের সব দৌড়বিদ কমপক্ষে একবারের জন্য হলেও একা হয়ে আসবে।

 

২.

নাম্বার থিওরির একটা সমস্যা নিয়ে আলোচনা করা যাক। তবে তার আগে কিছু জিনিস ব্যাখ্যা করা প্রয়োজন।

ধরা যাক আমাদের কাছে একটা বাস্তব সংখ্যা r দেওয়া হল। তাহলে \left\| r \right\| দিয়ে বুঝাবে r এবং এর সবচেয়ে কাছের পূর্ণ সংখ্যার পার্থক্য। যেমন ধরা যাক 3.14 এর সবচেয়ে কাছের পূর্ণসংখ্যা 3। তাহলে \left\| {3.14} \right\| = 3.14 \sim 3 = 0.14

মনে করি D একটি পূর্ণ সংখ্যার সেট এবং এর সদস্য k সংখ্যক। এই সেটের সদস্যদের একটি বৈশিষ্ট্য হচ্ছে এরা সবাই সহমৌলিক। অর্থাৎ এই সেটের সদস্যদের মাঝে এক ছাড়া অন্য কোন সাধারণ উৎপাদক নেই।

তাহলে প্রমাণ করতে হবে যে এমন একটি বাস্তব সংখ্যা t পাওয়া যাবে যার জন্য D এর যে কোন  সদস্য(ধরা যাক v) এর জন্য সবসময় \left\| {vt} \right\| \ge \frac{1}{k}

 

৩.

কনজেকচারটি দিয়েছিলেন জে. এম. উইলস ১৯৬৭ সালে, আর এর নাম Lonely Runner Conjecture রাখেন এল. গডউইন ১৯৯৮ সালে। যদিও সমস্যাটি আসলে কম্বিনেটরিক্সের একটি অনুমান, কিন্তু নাম্বার থিওরির ক্ষেত্রেও এটি অনেক গুরুত্বপূর্ণ, বিশেষ করে Diophantine Approximation নিয়ে যখন কাজ করা হয় তখন।

k=1 এর জন্য আমরা জানি একলা দৌড়বিদের কনজেকচারটি সত্য, কারণ তখন ট্র্যাকে খেলোয়াড়ই মাত্র একজন। k=2 এর জন্যও খুব সহজে কনজেকচারটি প্রমাণ করা যেতে পারে। k=3 এর জন্য প্রমাণটি এক পৃষ্ঠার খুব একটা বেশি হবে না।

কিন্ত k এর মান যত বাড়তে থাকে, সমস্যাটির সমাধান ততই জটিল হতে থাকে। যেমন ধরা যাক এম.আই.টি. এর একদল গণিতবিদ k=6 এর জন্য কনজেকচারটির যে প্রমাণটি দিয়েছিলেন সেটি পাঁচ নয় দশ নয়, একেবারে ৫০ পৃষ্ঠা লম্বা ছিল! কিন্তু আরও আনন্দের ব্যাপার হচ্ছে ফরাসি গণিতবিদ জেরোম রেনাল্ট আরও সুন্দর একটি পদ্ধতি ব্যবহার করে k=6 এর জন্য সমস্যাটি প্রমাণ করতে জায়গা নিয়েছিলেন মাত্র ৯ পৃষ্ঠা।

গণিতের হাজার হাজার সমাধানহীন সমস্যার মাঝে তাই একলা দৌড়বিদের অনুমান বা Lonely Runner Conjecture এখনও একটি। এই ক্ষেত্রে বিখ্যাত ফার্মার লাস্ট থিওরেমের সাথে কনজেকচারটির একটা মিল খুঁজে পাওয়া যায়। দুটি সমস্যাই খুব সহজে বুঝা যায়, কিন্তু সমাধান করা মোটেও সহজ নয়।

এখন পর্যন্ত k=7 এর জন্য কনজেকচারটি সত্য প্রমাণিত হয়েছে আর k=7 এর জন্য প্রমাণটি করেছেন স্পেনের দুইজন গণিতবিদ। কিন্তু এর থেকে বড় কোন মানের জন্য অনুমানটি এখনও একটি অনুমান।

৪.

নাম্বার থিওরির যে সমস্যাটি দিয়েছিলাম সেটির কথা মনে আছে। যারা এখনও বুঝতে পারেনি তাদের একটা চমক দেওয়া যাক। ওই সমস্যাটিও কিন্তু লোনলি রানার কনজেকচার, চেহারাটা একটু পাল্টেছে কেবল।

কনজেকচারে আমাদের কাছে k জন দৌড়বিদ ছিল যাদের সবার বেগ আলাদা। তাদের বেগকে আমরা পূর্ণসংখ্যায় পরিণত করে ফেলতে পারি। যেমন ধরা যাক দৌড়বিদ তিনজন এবং তাদের বেগ প্রতি সেকেন্ডে যথাক্রমে 0.5, 0.27 এবং 0.13। তাহলে তাদের বেগ যদি 50, 27, 13 ধরা হয় তবে আপেক্ষিকভাবে ওদের অবস্থানের কিন্তু কোন পরিবর্তন ঘটে না। সুতরাং k জন দৌড়বিদের সবার বেগ পূর্ণসংখ্যা করে তাদের গ.সা.গু. দ্বারা ভাগ করে এদেরকে সহমৌলিক বানানোর পড় ধরে নেওয়া যায় বেগগুলো D সেটের সদস্য।

আমরা এতক্ষণ দৌড়বিদদের অবস্থান মাপছিলাম ট্র্যাকের সাপেক্ষে। এবার একটু মজা করা যাক, আমরা দৌড়বিদদের অবস্থান মাপি একজন নির্দিষ্ট দৌড়বিদের সাপেক্ষে। আমরা যদি k জনের কোন একজনকে স্থির ধরে নেই (তাহলে অবশ্য এটাও ধরে নিতে হবে যে ট্র্যাকটিও দৌড়বিদদের বিপরীত দিকে চলছে, অর্থাৎ ট্র্যাকেরও বেগ আছে) তখন কি হবে?

এবার দ্বিতীয় আরেকজন দৌড়বিদকে বিবেচনা করা যায় যার বেগ হচ্ছে v। তাহলে t সময় দৌড়বিদের অতিক্রান্ত দূরত্ব হবে vt কিলোমিটার। vt যদি পূর্ণসংখ্যা হয় তবে একটু চিন্তা করলেই বুঝা যাবে যে স্থির ধরে নেওয়া দৌড়বিদ আর দ্বিতীয় দৌড়বিদ এখন একই অবস্থানে। যদি দ্বিতীয় দৌড়বিদের অতিক্রান্ত দূরত্ব পূর্ণসংখ্যা না হয় তবে ||vt|| দিয়ে স্থির দৌড়বিদের থেকে তার দূরত্ব প্রকাশ পাবে।

এখন যদি কোন নির্দিষ্ট সময় t তে ট্র্যাকের প্রতিটি দৌড়বিদের থেকে স্থির দৌড়বিদের দূরত্ব \frac{1}{k} এর থেকে বেশি হয় তবেই বুঝা যাবে স্থির ধরে নেওয়া দৌড়বিদ একলা হয়ে যাবে। সুতরাং D সেটের যে কোন উপাদান v নেওয়া হলে যদি সবক্ষেত্রেই ||vt|| ≥ \frac{1}{k} হয় তবেই স্থির দৌড়বিদ একা হয়ে যাবে।

এভাবে প্রতিজনকেই একবার করে স্থির ধরে নিয়ে যদি প্রতিবার ||vt|| ≥ \frac{1}{k} প্রমাণ করা যায় তবে সকল দৌড়বিদকেই কমপক্ষে একবার একা প্রমাণ করা যাবে। সুতরাং ওই দৌড়বিদদের জন্য Lonely Runner Conjecture প্রমাণিত হবে।

 

আরও পড়ার জন্য দেখতে পারেন এখানে https://terrytao.wordpress.com/2015/05/13/a-remark-on-the-lonely-runner-conjecture/

About the author

মৃন্ময় আকাশ

আপাতদৃষ্টিতে অযৌক্তিক পৃথিবীর যুক্তি অন্বেষনে।

Leave a Comment