কম্বিনেটরিক্সের মজার সমস্যা

প্রিয় গণিত ইশকুলের বন্ধুরা, তোমরা অনেক তো সংখ্যাতত্ত্ব ও জ্যামিতির সমস্যা সমাধান করলে। আজকে আমরা কম্বিনেটরিক্সের কিছু সমস্যা দেখব। তাহলে চলো শুরু করি!

সমস্যা ১: 11×11 ঘরের একটি টেবিলে 1, 2, 3, …, 121 সংখ্যাগুলো সাজানো আছে, যাতে প্রতিটি ঘরে একটি করে সংখ্যা থাকে। সাদিয়া প্রতিটি সারির সব কটি সংখ্যার গুণফল বের করে, অপর দিকে আঁখি প্রতিটি কলামের সব কটি সংখ্যার গুণফল বের করে। সাদিয়া ও আঁখির বের করা সংখ্যাগুলোর সেট কখনো সমান হবে?

সমাধান:

কম্বিনেটরিক্সে সমস্যা সমাধানের জন্য আগে সমস্যাটা ভালোমতো বোঝাটা জরুরি, তাই আমি বলব প্রথমে কিছুক্ষণ নিজে চেষ্টা করে তারপর সমাধান দেখতে।

এখানে প্রতিটি কেস–এর জন্য গুণফলগুলো হাতে গোনা বেশ কষ্টকর, তাই অন্য কিছু চেষ্টা করতে হবে। আমরা গুণফল হাতে না গুণে এর মৌলিক উৎপাদকগুলো দেখতে পারি, যেগুলোর কোনো গুণিতক [2×সংখ্যা, 3×সংখ্যা…এ রকম] 121 এর চেয়ে ছোট না। এ রকম কয়েকটি হচ্ছে 61, 67, 71, … ইত্যাদি। এগুলো পুরো টেবিলে একবার ই থাকবে আর এ ক্ষেত্রে মৌলিক সংখ্যা খুব বেশি নেই। তাই, এগুলো নিয়ে কাজ করা সহজ; এ জন্য আমরা এসব মৌলিক সংখ্যাগুলো বের করি– 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113।

মজার বিষয় হলো, এখানে মোট 13টা মৌলিক সংখ্যা আছে, তবে আমরা 12টি ব্যবহার করেও সমস্যাটি সমাধান করতে পারি। পায়রা খোপ নীতি (Pigeonhole principal) অনুযায়ী আমরা বলতে পারি যে কমপক্ষে একটি সারিতে 2টি মৌলিক সংখ্যা থাকবে। বোঝার সুবিধার্থে, আমরা ধরে নিচ্ছি 5 নং সারির 3 নং ও 8 নং কলামে 2টা মৌলিক সংখ্যা p₁, p₂ ∈ {­­61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113} আছে [বাকিগুলোর ক্ষেত্রেও একই যুক্তি প্রযোজ্য]। এবার নিচের চিত্র খেয়াল করো–

যেহেতু p₁ মৌলিক সংখ্যা টেবিলে আর কোথাও নেই, তাই 3 নং কলামের সব কটি সংখ্যার গুণফল 5 নং সারির সব কটি সারির গুণফলের সমান হতেই পারে। তবে এটি সম্ভব নয়। কারণ, 5 নং সারিতে p₂ আছে যা 3 নং কলামে নেই। এবার কিন্তু আমাদের সমস্যার সমাধান হয়ে গেছে কারণ, 5 নং সারির সব সংখ্যার গুণফলের সমান এমন কোনো কলাম নেই। এ জন্য আমরা বলতে পারি যে সাদিয়া ও আঁখির পাওয়া সংখ্যাগুলোর সেট কখনোই সমান হতে পারবে না।

সমস্যা ২: একটি xy সমতলে শাফি  (x, y) বিন্দু হতে (y, x), (3x, −2y), (−2x, 3y), (x + 1, y + 4), (x − 1, y − 4) ইত্যাদি বিন্দুতে যেতে পারে। প্রমাণ করো যে শাফি শুরুতে (0, 1) বিন্দুতে থাকলে সে কখনোই (0, 0) বিন্দুতে পৌঁছাতে পারবে না।

সমাধান:

এ ধরনের সমস্যা সমাধানের জন্য আমরা এমন কিছু খোঁজার চেষ্টা করব, যেটি কোনো ক্ষেত্রে পরিবর্তিত না হয়, এখানে আমরা modular arithmetic ব্যবহার করব (ভাগশেষ নিয়ে কাজ করব আরকি!)

এখানে আমরা (x + y) (mod 5) নিয়ে বা, প্রতিটি রাশিকে 5 দ্বারা ভাগ করে ভাগশেষ বিবেচনা করে পাই–

প্রথমে যদি x + y, 5 দ্বারা বিভাজিত না হয় তাহলে,

 x + y ≢  0 (mod 5)

3x − 2y ≡ 3x + 3y ≡ 3 (x + y ) ≢ 0 (mod 5)    [∵ 5 দ্বারা 3 বিভাজ্য না]

−2x + 3y ≡ 3x + 3y ≡ 3(x + y) ≢ 0 (mod 5)

(x + 1) + (y + 4) ≡ x + y + 5 ≡ x + y ≢ 0 (mod 5)

(x - 1) + (y - 4) ≡ x + y - 5 ≡ x + y ≢ 0 (mod 5)

এখান থেকে আমরা পাই যে কোনো একটি বিন্দু (x, y) এর জন্য, x + y, 5 দ্বারা বিভাজ্য না হলে তার সব পথের বিন্দুর ভুজ ও কোটির যোগফল 5 দ্বারা নিঃশেষে বিভাজ্য হবে না। আমাদের কাজ কিন্তু প্রায় শেষ। কারণ, (0, 0)  বিন্দুর ক্ষেত্রে  (0 + 0) ≡ 0 (mod 5); তবে (0,1) বিন্দুর ক্ষেত্রে,  (0 + 1) ≡ 1 ≢ 0(mod 5)  এ কারণে আমরা বলতে পারি যে শাফি কখনোই (0, 0) বিন্দুতে পৌঁছাতে পারবে না।