يك دسته 7 تايي كارت كه روي آنها اعداد 0 تا 6 نوشته شده است بين سه عامل a , b و c توزيع شده است، به طوريكه به دو عامل a وb هر نفر سه كارت، و به عامل c يك كارت داده شده است.
عاملهاي a و b ميخواهند همديگر را از كارتهاي خود مطلع كند بدون آنكه عامل c اطلاعي در مورد دست آنها پيدا كند. اما سيستم ارتباطي به گونه اي است كه هر خبري را كه يكي از عاملها براي عاملي ديگر ميفرستد، همه عاملها از آن مطلع ميشوند. يعني ارتباط دو عامل تنها از راه اعلان عمومي ميسر است. چگونه اين كار امكان پذير است؟
۱۰ نظر:
هر کدام از a و b سه عدد تصادفی انتخاب می‌کند به طوری که جمع سه عدد بر ۷ بخش‌پذیر باشد. سپس به هر یک از سه عدد مقدار روی یکی از کارت‌هایش را افزوده و سه عدد حاصل را اعلام می‌کند.
هر کدام نیز سه عددی را که از شخص مقابل شنیده، با اعداد روی کارتهای خود جمع زده و باقی‌مانده‌اش بر ۷ را حساب کرده و از ۶ کم می‌کند تا به کارت شخص c پی ببرد و با مقایسه با دست خود، دست نفر دیگر را نیز بفهمد.
از كجا مطمئني كه C هيچي از كارتها دو نفر ديگر رو نمي فهمه؟
حق با شماست، اشتباه شد!
تو الگوریتمی که گفتم به وضوح نفر c باقیمانده جمع کارتهای هر نفر بر ۷ رو می‌فهمه.
این جوری تغییر بدیم الگوریتم رو:
هر کدام از a و b سه عدد تصادفی انتخاب می‌کند به طوری که جمع سه عدد بر ۷ بخش‌پذیر باشد. این کار را هم این گونه انجام می‌دهند که ابتدا دو عدد تصادفی یونیفرم بین صفر تا شش انتخاب کرده، سپس عدد سوم را از روی آنها به دست می‌آورند. سپس به هر یک از سه عدد مقدار روی یکی از کارت‌هایش را افزوده و سه عدد حاصل را به یاد می‌سپرد.
سپس a باقی‌مانده‌ی عدد اول به دست آمده‌ی خود بر ۷ را اعلام می‌کند. آنگاه b آن عدد را گرفته، عدد اول خود را به آن افزوده و باقی‌مانده‌اش بر ۷ را اعلام می‌کند. a نیز عددِ جدید را گرفته، عددِ دوم خود را به آن می‌افزاید و دوباره باقی‌مانده‌اش بر ۷ را اعلام می‌کند.
این کار را هر کدام سه بار انجام می‌دهند. سپس، عدد پایانی را گرفته، از ۶ کم می‌کنند تا به کارت شخص c پی ببرند و با مقایسه با دست خود، دست نفر دیگر را نیز بفهمد.
برای اثبات می‌توان این گونه استدلال کرد که هر یک از شش عدد اعلام شده، به غیر از عدد آخر، همواره باقی‌مانده‌ی جمع تعدادی عدد بر ۷ بوده که حداقل یکی از این اعداد تصادفی یونیفورم بین صفر تا شش و مستقل از بقیه اعداد بوده. پس توزیع پنج عدد اول یونیفورم صفر تا شش و در نتیجه مستقل از کارتهای a و b است.
درسته؟
هوم. سر عدد پنجم مشکل داره استدلالم.
یه راه حل ساده :
نفر A کارتهای 1و2و3 را دارد.
نفر A بگه : من یا B کارتهای 1و2و3 را دارم.
در این صورت C نمی تونه بگه کی چی داره...
خوب نفر c هم می‌فهمه که! مهم نیست a چی می‌گه، همه از پروتکل خبر دارن.
فکر نکنم همه از پروتکل خبر داشته باشن...توی متن سوال نگفته که ...
حتی بدون چنین فرضی، باز هم الگوریتم شما مشکل داره چون c تقسیم کارت‌ها رو می‌فهمه.
همه از پروتكل خبر دارند
من چندین بار به این سوال فکر کردم ولی هنوز جواب کاملی نیافتم... کمکی، پیشنهادی اگر کسی داره ممنون می‌شم.
ارسال یک نظر