09-05-2025 01:38:07 am

print

 
বিজ্ঞান - Bigyan-logo

বিজ্ঞান - Bigyan

বাংলা ভাষায় বিজ্ঞান জনপ্রিয়করণের এক বৈদ্যুতিন মাধ্যম
An online Bengali Popular Science magazine

https://bigyan.org.in

 

কেক কাটার সমস্যা!


%e0%a6%86%e0%a6%b7%e0%a6%bf%e0%a6%95%c2%a0-%e0%a6%96%e0%a7%81%e0%a6%a6%e0%a6%be%e0%a6%ac%e0%a6%95%e0%a7%8d%e0%a6%b6
আষিক  খুদাবক্শ

(Carnegie Mellon University)

 
15 Feb 2016
 

Link: https://bigyan.org.in/cake

%e0%a6%95%e0%a7%87%e0%a6%95-%e0%a6%95%e0%a6%be%e0%a6%9f%e0%a6%be%e0%a6%b0-%e0%a6%b8%e0%a6%ae%e0%a6%b8%e0%a7%8d%e0%a6%af%e0%a6%be

একটা কেক - যার উপর কাজু, কিসমিস, চকোলেট ছড়ানো- তাকে কী করে অনেকের মধ্যে ভাগ করে দেওয়া যায়, যাতে সবাই সন্তুষ্ট হয়?

prof

ডঃ সত্যব্রত দাস ছিলেন নদীয়ার কল্যাণী ইউনিভার্সিটি এক্সপেরিমেন্টাল হাইস্কুলের গণিত শিক্ষক। দীর্ঘ কর্মজীবনে অসংখ্য কৃতি ছাত্রছাত্রী তিনি তৈরী করেছেন, যারা দেশে-বিদেশে বিজ্ঞান ও প্রযুক্তির বিভিন্ন ধারাকে পুষ্ট করে চলেছে নিরন্তর। মানুষটির জীবনের অনেকটা সময় কেটেছে রোগে ভুগে। কিন্তু, মনের জোরকে সম্বল করে ‘সত্য স্যার’ অব্যাহত রেখেছিলেন গণিতের শিক্ষাদান। গত ২০১৩ র ১৪-ই ফেব্রুয়ারী এই কর্মবীর মানুষটির জীবনাবসান হয়। 

তাঁর স্মৃতিতে ছাত্রছাত্রীরা কল্যাণীতে শুরু করেছেন বার্ষিক “ডঃ সত্যব্রত দাস স্মৃতি বক্তৃতা”। এই বক্তৃতার প্রধান উদ্দেশ্য হল, তারই দেখানো পথে পরবর্তী প্রজন্মকে বিজ্ঞানে উৎসাহিত করা। আর এই কাজটি করার জন্য উদ্যোক্তারা বেছে নিয়েছেন সত্য স্যরের হাতে গড়া ছাত্রছাত্রীদেরই। ২০১৬ এর ১০ জানুয়ারী বক্তৃতার দ্বিতীয় বর্ষে বক্তা ছিলেন আষিক খুদাবক্শ, যে বর্তমানে আমেরিকার কার্নেগী মেলন বিশ্ববিদ্যালয়ে কম্পিউটার সায়েন্স-এর গবেষক। তার বক্তৃতার বিষয় কম্পিউটার সায়েন্সের একটি মজার, এবং ব্যবহারিক জগতে অত্যন্ত গুরুত্বপূর্ণ সমস্যা – কিভাবে একটা কেক-কে অনেকের মধ্যে সন্তোষজনক ভাবে ভাগ করে দেওয়া যায়! সেই বক্তৃতাটির উপর ভিত্তি করে আষিক লিখছে ‘বিজ্ঞান’-এর পাতায়। আজ প্রথম পর্ব।

“একদিকে “নারায়ণী সৈন্য” নামক আমার অতি ভয়ঙ্কর এক অর্বুদ সৈন্য থাকিবে, অপরদিকে আমি নিজে শুধু হাতে থাকিব, কিন্তু যুদ্ধ করিব না। এই দুয়ের মধ্যে যাহার যাহা ইচ্ছা নিতে পার। অর্জুন বয়সে ছোট, সুতরাং তাহাকেই আগে জিজ্ঞেস করি। বল তো অর্জুন, ইহার কোনটা তোমার পছন্দ হয়?”

অর্জুন বলিলেন, “আমি সৈন্য চাহি না, আপনাকেই চাহি।”

কাজেই অর্জুন পাইলেন কৃষ্ণকে, আর দুর্যোধন পাইলেন এক অর্বুদ সৈন্য। দুজনেই মনে করিলেন, ‘আমি খুব জিতিয়াছি।’

[ছেলেদের মহাভারত, উপেন্দ্রকিশোর রায়চৌধুরী]

পর্ব-১

মহাভারতে দুর্যোধন ও অর্জুনের মধ্যে সেই এক অর্বুদ সৈন্য অথবা স্বয়ং কৃষ্ণকে ভাগ করে দেওয়া হচ্ছে গেম থিয়োরীর “ফেয়ার অ্যালোকেশন অফ ইনডিভিজিবল গুড্স”-এর একটি উদাহরণ। কিন্তু আজকের গল্প “ফেয়ার অ্যালোকেশন”-এর অন্য শাখাটিকে নিয়ে – যেখানে ভাগের বস্তুটি ডিভিজিবল বা বিভাজ্য – গেম থিয়োরী, রাষ্ট্রবিজ্ঞান, কম্পিউটার সায়েন্স, ইকনমিক্স-এর বহুচর্চিত বিষয় “কেক-কাটিং”।

তা কী এই “কেক-কাটিং” সমস্যা? ধরা যাক একটি কেক রয়েছে যা n সংখ্যক লোকের মধ্যে ভাগ করে দিতে হবে। কেকটির ওপরে কাজু, কিশমিশ, মোরব্বা, চকলেট সাজানো রয়েছে। এখন কারোর হয়তো চকলেট আর কাজু ভারি পছন্দ – কারোর হয়তো বাদামে অ্যালার্জি। কীভাবে সেই কেক ভাগ করা যায়, যাতে সব্বাই নিজের নিজের ভাগে সন্তুষ্ট থাকে সেই নিয়ে গবেষণা। ভাইবোনের নিরন্তর ঝগড়াঝাটির এই আপাতসাধারণ ছেলেমানুষি সমস্যা নিয়ে বিশ্বের তাবড় তাবড় বিজ্ঞানীরা সেই দ্বিতীয় বিশ্বযুদ্ধের সময় থেকে মাথা ঘামাচ্ছে। কিন্তু কেন? কেন কেক-কাটিং নিয়ে গবেষণা এত গুরুত্বপূর্ণ?

বস্তুত কেক হচ্ছে একটা অসমসত্ত্ব (হেটেরোজিনিয়াস), বিভাজ্য (ডিভিজিবল) জিনিসের প্রতীক। সেই কেক জমি হতে পারে, হতে পারে টেলিভিশনের এয়ারটাইম, আবার একটা আস্ত দেশও হতে পারে। তেমনই হতে পারে প্রাকৃতিক দূষণরোধের খরচ। তাই এত গবেষণা। আর হবে নাই বা কেন – গবেষণায় জানা গিয়েছে যত বেশী লোকের মধ্যে ভাগ করতে হবে এই কেক – সমস্যা হয়ে উঠবে ততটাই জটিলতর।

এই কেক হতে পারে জমি, টেলিভিশনের এয়ারটাইম, একটা আস্ত দেশ, বা প্রাকৃতিক দূষণরোধের খরচ।

শুরু করা যাক – দুজন দিয়ে। ধরা যাক দুজনের মধ্যে একটা কেক এমনভাবে ভাগ করে দিতে হবে যাতে দুজনেই নিজের নিজের ভাগ নিয়ে সন্তুষ্ট থাকে। এই বন্টন (অ্যালোকেশন) আমরা ন্যায়সঙ্গত (ফেয়ার) বলব যদি প্রতিটি ভাগীদারের জন্য নিচের দুটো শর্ত প্রযোজ্য হয় –

১: সমানুপাতিক ভাগ (প্রোপোরশনলাটি)  – কোনও ভাগীদারের কাছে কেকের দাম যদি ১ টাকা হয়ে থাকে, তার যেন মনে হয় অন্তত ১/২ টাকা দামের কেকের টুকরো সে পেয়েছে।

২: ঈর্ষামুক্তভাবে ভাগ (এনভি-ফ্রিনেস) – কোনও ভাগীদারই অপরকে ঈর্ষা (এনভি) করছে না। কারোরই মনে হচ্ছে না তার বরাদ্দ টুকরোটার থেকে অন্যর কেকের টুকরোটা বেশী ভালো।

এখন দুজনের মধ্যে  প্রোপোরশনলাটি ও এনভি-ফ্রিনেস মেনে খুব সহজে ভাগ করে ফেলা যায় কেক। প্রথম লোকটাকে বলব “তুমি কেকটা সমান দুইভাগে কাটো”। দ্বিতীয় লোকটাকে বলব – “তুমি আগে বাছো” (প্রথম লোকটা কিন্তু কেকটা কাটবার আগেই জানে যে দ্বিতীয় লোকটা আগে বাছবার সুযোগ পাবে)। যেহেতু দ্বিতীয় ব্যক্তি আগে বাছার সুযোগ পাচ্ছে – সে নিশ্চয়ই প্রথম ব্যক্তিকে ঈর্ষা করবে না। আর প্রথম ব্যক্তি যেহেতু নিজেই কেকটা কেটেছে, তার কাছে দুটো টুকরো নিশ্চয়ই সমানই মনে হয়েছে। তাই যে টুকরোটাই সে পাক না কেন, সেও দ্বিতীয় ব্যক্তিকে ঈর্ষা করবে না।

তা হলে কি এই অ্যালোকেশন এনভি-ফ্রি? এবং প্রোপোরশনালও? একটু তলিয়ে ভাবলেই দেখা যায় দুজনের মধ্যে কেক ভাগ হলে এনভি-ফ্রিনেস এবং প্রোপোরশনলাটি একই জিনিস। যদি গোটা কেকের দাম আমার কাছে এক টাকা হয়, অন্তত ১/২ টাকা দামের কেকের টুকরো পেলে নিশ্চিতভাবে অন্য টুকরোটার দাম আমার কাছে বড় জোর ১/২ টাকা। তাই অ্যালোকেশন প্রোপোরশনাল হলে এনভি-ফ্রিও হবে। আবার উলটোদিকে যদি অ্যালোকেশন এনভি-ফ্রি হয়, আমি অন্যকে ঈর্ষা করছি না মানে আমার টুকরোটার দাম আমার কাছে অন্তত ১/২ টাকা (যদি গোটা কেকের দাম আগের মতো আমার কাছে এক টাকা হয়)।

এ তো গেল দুজনের মধ্যে কেক কাটার সমস্যা। তিন জনের জন্য কেক-কাটিং-এও কি এনভি-ফ্রিনেস এবং প্রোপোরশনলাটি একই জিনিস? দুজনের মধ্যে কেক-ভাগের সময়ে প্রথম ব্যক্তিটি অসৎ হলে কী কোনওভাবে লাভবান হতে পারে? এইসব আপাতনিরীহ কিন্তু জটিল প্রশ্নের আলোচনা চালু থাকবে পরের পর্বে।

-চলবে

আরও পড়তে হলে – 

১। Cake Cutting: Not Just Child’s Play by Ariel D. Procaccia 

(লেখকের ছবি তুলেছে – অর্কপ্রভ পাত্র, ডঃ সত্যব্রত দাস এবং তাঁর নামে বক্তৃতা সম্বন্ধে লিখেছে – দেবাদিত্য বিশ্বাস)

ডঃ সত্যব্রত দাস সম্বন্ধে দু-চার কথা – ১৯৬২ সালে হিলি আর. এন. হাই স্কুল থেকে বিজ্ঞান বিভাগে পাশ করার পর তিনি ১৯৬৫ সালে কে. এন. কলেজ থেকে অঙ্কে বি. এস. সি. পাশ করেন। ১৯৬৯ সালে কলকাতা বিশ্ববিদ্যালয় থেকে অঙ্কে প্রথম শ্রেণীতে এম. এস. সি। ১৯৮৬ সালে পি. এইচ. ডি. ডিগ্রী লাভ করেন কল্যাণী বিশ্ববিদ্যালয় থেকে। তাঁর কর্মজীবন শুরু অঙ্কের শিক্ষক হিসেবে বড় আন্দুলিয়া হাইস্কুলে। সেখানে কিছুদিন শিক্ষকতা করার পর তিনি যোগ দেন কল্যাণী ইউনিভার্সিটি এক্সপেরিমেন্টাল হাইস্কুলে।

লেখক পরিচিতিঃ আষিক খুদাবক্শ কার্নেগী মেলন বিশ্ববিদ্যালয়ের কম্পিউটার সায়েন্স বিভাগে পি এইচ ডি করছেন। গবেষণার বিষয় মেশিন লার্নিং ও আর্টিফিশিয়াল ইন্টেলিজেন্স। গবেষণার বাইরে আষিক সাংবাদিকতা, কাব্য ও সঙ্গীতচর্চা করেন। সুরকার ও গীতিকার হিসেবে কাজ করেছেন ভারতীয় মার্গসঙ্গীতের উল্লেখযোগ্য কিছু তরুণ শিল্পীর সঙ্গে। প্রকাশিত কবিতার বই দুটিঃ ঘুম নামের পাহাড় ও বরফবন্দীর ডায়েরি।
 
আপনার স্কুলেও যদি এমন বিজ্ঞানের সেমিনার হয় তাহলে তার বর্ণনা জানিয়ে আমাদের ই-মেইল করুন [email protected]-এ।
 
 
বিজ্ঞান পত্রিকা ডাউনলোড করুন।
 

লেখাটি অনলাইন পড়তে হলে নিচের কোডটি স্ক্যান করো।

Scan the above code to read the post online.

Link: https://bigyan.org.in/cake

print

 

© and ® by বিজ্ঞান - Bigyan, 2013-25