Pigeonhole Principle (පරවි කූඩු මූලධර්මය)

 PIEGONHOLE PRINCIPLE

(පරවි කූඩු මූලධර්මය)

Pigeonhole මූලධර්මය සංයුක්ත විද්‍යාවේ (Discreate Mathematics) සහ විවික්ත ගණිතයේ (Combinatorics)  භාවිතා වන සරල නමුත් ප්‍රබල මෙවලමකි. එය Dirichlet box මූලධර්මය (ජර්මානු ගණිතඥය Dirichlet ට ගෞරවයක් වශයෙන්) හෝ ලාච්චු මූලධර්මය (Drawer Principle) ලෙසද හැඳින්වේ. පරෙවි කූඩු වලට වඩා පරවියන් වැඩි නම්, අවම වශයෙන් එක් පරෙවි කුහරයක පරෙවියෙකුට වඩා වැඩි ගණනක් තිබිය යුතු බව මූලධර්මයේ සඳහන් වේ. එය සුළුපටු ප්‍රකාශයක් ලෙස පෙනෙනු ඇත, නමුත් Pigeonhole මූලධර්මය පරිගණක විද්‍යාවේ (Computer Science) සිට ගුප්තකේතනය (Cryptography)  දක්වා විවිධ ක්ෂේත්‍රවල යෙදීම් (Applications) ඇත.

Pigeonhole  මූලධර්මය තේරුම් ගැනීමට, අපට පරෙවියන් 4 ක් සහ පරෙවි කූඩු 3 ක් ඇති අවස්ථාවක් සලකා බලන්න. අපි එක් එක් පරෙවියෙකු වෙනම පරෙවි කුහරයක තැබීමට උත්සාහ කළහොත්, අපට පරවියන් දෙදෙනෙකු සිටින එක් පරෙවි කුහරයක් ලැබෙනු ඇත. මෙයට හේතුව පරෙවි කූඩු වලට වඩා පරවියන් වැඩි වීමයි. 

සාමන්‍ය වශයෙන් ගත් කල, Pigeonhole මූලධර්මය පහත පරිදි දැක්විය හැකිය:

Theorem 1: (Pigeonhole Principle) 

වස්තු n ප්‍රමාණයක් m බහාලුම්වලට තැන්පත් කර ඇත්නම් (n>m), අවම වශයෙන් එක් පෙට්ටියක වස්තු එකකට වඩා අඩංගු විය යුතුය.

සාධනය: 
සෑම බහාලුමකම උපරිම වශයෙන්  වස්තූ 1 ක් අඩංගු වේ යැයි සිතමු.
එවිට මුළු වස්තූන් ගණන උපරිම වශයෙන් m වේ. 
මෙය n (n>m) පරවියන් සිටින බවට පටහැනි වේ. 

පරෙවි කුහරයේ මූලධර්මය තේරුම් ගැනීමට, අපි සරල උදාහරණයක් සලකා බලමු.

Example 1: 
පන්තියක සිසුන් හය දෙනෙකු සිටින අතර, සෑම සිසුවෙකුටම 1 සිට 5 දක්වා අනන්‍ය අංකයක් පවරනු ලැබේ යැයි සිතමු. Pigeonhole මූලධර්මය අපට පවසන්නේ අවම වශයෙන් සිසුන් දෙදෙනෙකුට එකම අංකයක් තිබිය යුතු බවයි. ඇයි ඒ? හොඳයි, ඇත්තේ වෙනස් අංක පහක් පමණි, නමුත් සිසුන් හය දෙනෙක්. එබැවින්, සිසුන් දෙදෙනෙකුට අවම වශයෙන් එක් අංකයක් පැවරිය යුතුය.

ගැටලුවක් විසඳීම සඳහා Pigeonhole මූලධර්මය භාවිතා කරන්නේ කෙසේදැයි බැලීමට තවත් උදාහරණයක් සලකා බලමු. 

Example 2:

පෙට්ටියක රතු, නිල් සහ සුදු යන මේස් යුගල තුනක් අඩංගු වේ. පුද්ගලයෙක් මේස් දිහා නොබලා එළියට ගන්නවා කියලා හිතමු. ඔහුට අවම වශයෙන් එකම පාට මේස් යුගලයක් ඇති බවට සහතික වීමට ඔහු අවම වශයෙන් මේස් කීයක් පෙට්ටියෙන් පිටතට ගත යුතුද?

පිලිතුර:

ඔහු මේස් 2 ක් හෝ 3 ක් පමණක් ගන්නවා නම්, ඒවා සියල්ලම වෙනස් විය හැකිය. උදාහරණයක් ලෙස, ඔවුන් එකක් රතු සහ එකක් නිල් විය හැක; හෝ රතු එකක්, නිල් එකක් සහ සුදු එකක් විය හැක. නමුත් මම මේස් 4 ක් එළියට ගන්නවා නම්, එකම පාට මේස් යුගලයක් ඇතුළත් විය යුතුය. මෙහි තෝරාගත් මේස් හතර "වස්තු" වන අතර වර්ණ 3 "බහාලුම්" වේ;(Theorem 1). Pigeonhole මූලධර්මයට අනුව, තෝරා ගත් හතරෙන් අවම වශයෙන් දෙකක් එකම වර්ණයක් තිබිය යුතු අතර එබැවින් ගැලපෙන යුගලයක් විය යුතුය. මේ අනුව පිටතට ගත යුතු අවම මේස් ගණන 4 කි.

මෙවැනි ගැටලුවක් මෙම Blog අඩවියේම පලවිය. ඒ සදහා Click here. 

 

Example 3:
එකම මුල් අකුරු දෙක (Same first two initials) ඇති සිසුන් අවම වශයෙන් දෙදෙනෙකු වත් සිටින බවට සහතික වීමට පාසලක සිසුන් කී දෙනෙක් සිටීමට අවශ්‍යද?

පිලිතුර:
A, B, C, ..., Z, යන අකුරු 26 භාවිතයෙන් ලබා ගත හැකි මුලකුරු දෙකක විවිධ විය හැකි කට්ටල 26×26=676 ඇත. එබැවින් සිසුන් සංඛ්‍යාව 676 ට වැඩි විය යුතුය.

මේ අනුව අවම සිසුන් සංඛ්‍යාව 677 කි. 

Example 4:

ඔබට පුද්ගලයන් 400 දෙනෙකුගෙන් යුත් කණ්ඩායමක් සිටින බව සිතන්න, ඔවුන්ගෙන් ඕනෑම දෙදෙනෙක් එකම උපන්දිනයක් බෙදා ගන්නේද යන්න ඔබට දැන ගැනීමට අවශ්‍යයි. මෙම ගැටළුව විසඳීම සඳහා, අපට pigeonhole මූලධර්මය භාවිතා කළ හැකිය. වසරකට දින 365 ක් ඇත, නමුත් කණ්ඩායමේ පුද්ගලයින් 400 දෙනෙක් සිටිති. ඉතින් අවුරුද්දකට දවස් ගානට වඩා මිනිස්සු ඉන්නවා. එමනිසා, Pigeonhol මූලධර්මය අනුව, අවම වශයෙන් පුද්ගලයන් දෙදෙනෙකු එකම උපන්දිනයක් බෙදා ගත යුතුය.

වඩාත් සංකීර්ණ ගැටළු විසඳීම සඳහා පරෙවි කුහරයේ මූලධර්මය ද භාවිතා කළ හැකිය.

Example 5: 

ඔබ පළමු 2022 ධන නිඛිල වලින් k අහඹු ලෙස තෝරා ගත්තා යැයි සිතමු. තෝරාගත් පූර්ණ සංඛ්‍යාවෙන් අවම වශයෙන් එක් යුගලයක් 2023 ට එකතු වන බවට සහතික වන කුඩාම k කුමක්ද?

පිලිතුර:

2023 ට එකතු වන නිඛිල සංඛ්‍යා යුගල 2022/2=1011 පවතී. එවා (1,2022),(2,2021),(3,2020),..., (1011,1012) වේ. ධන නිඛිල 1008ක් පමණක් තෝරන ලද්දේ නම්, , ඒ කිසිවක් යුගල වශයෙන් 2023 ට එකතු නොවන පරිදි ධන නිඛිල 1008ක් තෝරාගත හැක. නිඛිල 1008ක් පමණක් තෝරා ගන්නේ නම්, ධන නිඛිල 1008ක් තෝරාගත හැකි අතර, ඒ කිසිවක් යුගල වශයෙන් 2023ට එකතු නොවේ. Pigeonhole මූලධර්මය අනුව, අවම වශයෙන් නිඛිල 1011+1=1012 ක් තෝරාගැනීමෙන්, අවම වශයෙන් එක් යුගලයක්වත් 2023ට එකතු වන යුගලයක කොටසක් වනු ඇති බවට සහතික වේ.

දැන් අපි මෙහි ප්‍රායේගික ලොකයේ ඇති යෙදුම් කිහිපයක් බලමු. 

Pigeonhole මූලධර්මය පරිගණක විද්‍යාව (Computer Science) සහ ගුප්තකේතනය (Cryptography) සිට සංගීත න්‍යාය (Music Theory) සහ ක්‍රීඩා කාලසටහන් සැකසීම (Sports Secluding) දක්වා විවිධ සන්දර්භවල භාවිතා වේ. උදාහරණ කිහිපයක් පහත දැක්වේ:

• පරිගණක විද්‍යාව: පරිගණක විද්‍යාවේදී, මෙම මූලධර්මය ඇතැම් විසඳුම් පවතින බව ඔප්පු කිරීමට සහ ඇල්ගොරිතම විශ්ලේෂණය කිරීමට භාවිතා කරයි. පරිගණක විද්‍යාවේ පරෙවි සිදුරු මූලධර්මයේ යෙදුමක එක් උදාහරණයක් වන්නේ හැෂ් ශ්‍රිත විශ්ලේෂණයයි (Analyzing of Hash Functions). හැෂ් ශ්‍රිතයක් විශාල ආදාන අවකාශය (Input space) කුඩා ප්‍රතිදාන අවකාශයකට (output Space) සිතියම් ගත (Map) කරයි. Pigeonhole මූලධර්මයට අනුව, ආදාන අවකාශය ප්‍රතිදාන අවකාශයට වඩා විශාල නම්, වෙනස් අදාන දෙකක් එකම ප්‍රතිදානයට සිතියම්ගත කළ යුතුය. මෙය ගැටීමක් (Collison) ලෙස හඳුන්වනු ලබන අතර එය හැෂ් ශ්‍රිත නිර්මාණයේ මූලික ගැටලුවකි. සිදුවිය හැකි ගැටීම් සංඛ්‍යාව විශ්ලේෂණය කිරීමෙන් පරිගණක විද්‍යාඥයින්ට හැෂ් ශ්‍රිතයක කාර්යක්ෂමතාව සහ ආරක්ෂාව තීරණය කළ හැක.
  
  
• ගුප්තකේතනය: කිසිදු සංකේතාංකන ක්‍රමයක් (Encryption Scheme) සම්පූර්ණයෙන්ම නොබිඳිය හැකි බව පෙන්වීමට Pigeonhole මූලධර්මය භාවිතා කළ හැක.තිබිය හැකි සියලුම යතුරු (All possible keys) වලට වඩා වැඩි පණිවිඩ ගණනක් ඇති විට, අවම වශයෙන් එක් පණිවිඩයක් එකම යතුරකින් කේතනය කළ යුතුය. මෙය Collison (ඝට්ටනයක්) ලෙස හඳුන්වනු ලබන අතර, එයින් අදහස් වන්නේ සංකේතාංකන ක්‍රමය ප්‍රහාරයට ගොදුරු විය හැකි බවයි.(ගුප්තකේතනකරනයේදි යතුරක් (key) යනු, ගුප්ත ලේඛන ඇල්ගොරිතමයක් හරහා සැකසූ විට, ගුප්ත ලේඛන දත්ත සංකේතනය (Encryption) කිරීමට හෝ විකේතනය (Decryption) කිරීමට හැකි තොරතුරු කොටසකි. (මෙය සාමාන්‍යයෙන් ගොනුවක ගබඩා කර ඇති අංක හෝ අකුරු මාලාවකි.))

• ක්‍රීඩා කාලසටහන් සකස් කිරීම: එක් එක් කණ්ඩායම සමාන ක්‍රීඩා සංඛ්‍යාවක් ක්‍රීඩා කරන බව සහතික කිරීම සඳහා ක්‍රීඩා කාලසටහන් ගත කිරීමේදී Pigeonhole මූලධර්මය භාවිතා කරයි. උදාහරණයක් ලෙස, කණ්ඩායම් 10 ක් සහ තරඟ 9 ක කාලසටහනක් සහිත ලීගයකදී, සෑම කණ්ඩායමක්ම අවම වශයෙන් එක් ප්‍රතිවාදියෙකු දෙවරක් ක්‍රීඩා කළ යුතුය.

අවසාන වශයෙන්, Pigeonhole මූලධර්මය යනු පුළුල් පරාසයක ගැටළු විසඳීම සඳහා භාවිතා කළ හැකි බලවත් මෙවලමකි. මූලධර්මය අවබෝධ කර ගැනීමෙන් සහ විවිධ අවස්ථාවන්ට එය අදාළ කර ගැනීමෙන්, අපට නව අවබෝධයක් ලබා ගත හැකි අතර, වෙනත් ආකාරයකින් විසඳිය නොහැකි යැයි පෙනෙන ගැටළු විසඳා ගත හැකිය. ඔබ ගණිතඥයෙක්, පරිගණක විද්‍යාඥයෙක්, සංගීතඥයෙක් හෝ ක්‍රීඩා ලෝලියෙක් වේවා, Pigeonhole මූලධර්මය ඔබ හුරුපුරුදු විය යුතු සංකල්පයකි.

ලිපිය ලිවිමට ආධර කරගත් දෑ

• https://brilliant.org/wiki/pigeonhole-principle-definition/
• https://en.wikipedia.org/wiki/Pigeonhole_principle

Ashan Jayamal