مساله ۳۵. بنگاه املاک هشمت

هشمت و ۷ تا مشاور املاک دیگه میخوان حساب کنن ۸ نفری جمعا در سال گذشته چند معامله انجام دادن. ولی هیچ‌کس نمی‌خواد عدد دقیق تعداد معاملاتش لو بره. با چه استراتژی‌ای می‌تونن مجموع کل تعداد معاملات رو حساب کنن؟

لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1701104664111124772

راه‌های متنوعی برای حل این مساله وجود دارد. یک راه نسبتا ساده این است که نفر اول یک عدد تصادفی انتخاب کند و با تعداد معاملات خود جمع و حاصل را تو گوش نفر دوم بگوید، سپس نفر ۲ ام عدد گرفته شده را با تعداد معاملات خود جمع کند و تو گوش نفر سوم بگوید، نفر سوم عدد گرفته از نفر دوم را با تعداد معاملات خود جمع کرده و تو گوش نفر چهارم بگوید، و به همین ترتیب ادامه دهند تا نفر هشتم عدد گرفته شده از نفر هفتم را با تعداد معاملات خود جمع کرده و به نفر اول دهد.

سپس نفر اول عدد تصادفی اولیه را از عددی که از نفر هشتم گرفته کم کرده و حاصل را به عنوان مجموع تعداد معاملات اعلام می‌کند.

دقت کنید که در هر الگوریتمی اگر تعداد معاملات همه به غیر از یک نفر صفر باشد، آن یک نفر با فهمیدن اینکه مجموع معاملات برابر تعداد معاملات اوست، خواهد فهمید که بقیه هیچ معامله‌ای نکرده‌اند! پس حداقل شرط لو نرفتن این است که تعداد معاملات حداقل دو نفر بیشتر از صفر باشد.