تاس‌های ناگذرا

به مجموعه‌ای از تاس‌ها ناگذرا می‌گوییم اگر شامل سه تاس، A, B و C باشد، به صورتی که عدد تاس A به احتمال بیش از نیم، بیشتر از عدد B بوده و عدد تاس B نیز به احتمال بیش از نیم، بیشتر از C باشد، با این حال نتوان نتیجه گرفت که عدد تاس A به احتمال بیشتر از نیم از تاس C بزرگ‌تر است.

به عبارت دیگر، اگر رابطهٔ “ در یک آزمایش، تاس X با احتمال بیشتر از نیم عددی بزرگ‌تر از تاس Y دارد “ را R بنامیم، مجموعه‌ای از تاس‌ها ناگذرا است اگر رابطهٔ R بر روی زوج مرتب‌هایی از تاس‌های مجموعه دارای خاصیت تراگذری نباشد. نام این مجموعه از تاس‌ها نیز از همین تعریف گرفته شده‌است.

با استفاده از چنین مجموعه‌هایی از تاس‌ها، می‌توان بازی‌هایی اختراع کرد که نتیجهٔ آن‌ها به‌طور متوسط به نفع یکی از بازیکنان باشد.

این تاس‌ها در دستهٔ جامع تناقض‌های ناگذرا قرار می‌گیرند که مطالعات بسیاری حول آن انجام می‌گیرد. به عنوان مثال یکی از معروف‌ترین مسائل در ناگذرایی، پارادوکس رای‌گیری است که اولین بار توسط مارکی دو کندورسه مطرح شد. مسئله برای جامعه‌ای با سه انتخاب A و B و C است که افراد در این جامعه A را به B, B را به C و C را به A ترجیح می‌دهند.

ثابت شده‌است که اگر احتمال برد تاس A از B را با p، احتمال برد B از C را با q و احتمال برد C از A را با r نمایش دهیم خواهیم داشت:‌ $1\leq p+q+r\leq 2$و برای q, p و r برابر در حالت بیشینه هر کدام ${\frac {2}{3}}$هستند. اما ثابت می‌شود که این حالت ممکن نیست. بنابراین نمی‌توان به طور دقیق از تاس‌های ناگذرا برای مدل‌سازی مسئله انتخابات استفاده کرد.

مثال

مجموعه‌ای از تاس‌های ناگذرا

فرض کنید یک بازی با قواعد زیر تعریف شده‌است:

• نفر اول تاسی انتخاب می‌کند.
• نفر دوم از میان تاس‌های باقی‌مانده یکی را انتخاب می‌کند.
• اکنون هر بازیکن یک بار تاس می‌اندازند و تاس با برآمد بیشتر برنده اعلام می‌شود.

اگر این بازی با مجموعه‌ای از تاس‌های گذرا انجام شود، بازی یا عادلانه است یا به نفع اولین بازیکن، زیرا می‌تواند تاسی را انتخاب کند که بیشتر از نیمی از مواقع ببرد.

اما اکنون مجموعه تاس‌های زیر را در نظر بگیرید:

• بر روی وجه‌های تاس A اعداد ۲و ۲و ۴و ۴و ۹و ۹ نوشته شده‌اند.
• بر روی وجه‌های تاس B اعداد ۱و ۱و ۶و ۶و ۸و ۸ نوشته شده‌اند.
• بر روی وجه‌های تاس C اعداد ۳و ۳و ۵و ۵و ۷و ۷ نوشته شده‌اند.

هر پیکان احتمالی برابر با ${\frac {5}{9}}$دارد.

در این مجموعه از تاس‌ها، احتمال برد A از B، برابر با احتمال برد B از C، برابر با احتمال برد C از A و برابر با ${\frac {5}{9}}$ است؛ بنابراین این مجموعه تاس‌ها ناگذرا هستند. در این صورت بازی به نفع نفر دوم خواهد بود، زیرا که می‌تواند تاسی را انتخاب کند که به احتمال ${\frac {5}{9}}$ تاس اول را شکست دهد.

تمام پیشامدهای ممکن از این بازی در جدول‌های زیر آمده‌اند:

بازیکن اول تاس A را انتخاب کند بازیکن دوم تاس C را انتخاب کند					بازیکن اول تاس B را انتخاب کند بازیکن دوم تاس A را انتخاب کند					بازیکن اول تاس C را انتخاب کند بازیکن دوم تاس B را انتخاب کند
A C	۲	۴	۹		B A	۱	۶	۸		C B	۳	۵	۷
۳	C	A	A		۲	A	B	B		۱	C	C	C
۵	C	C	A		۴	A	B	B		۶	B	B	C
۷	C	C	A		۹	A	A	A		۸	B	B	B

بازی دو نفره

فرض کنید شما و دوستی بازی شرح داده شده را با سه تاس زیر انجام می‌دهید.

• بر روی وجه‌های تاس A اعداد ۶و ۳و ۳و ۳و ۳و ۳ نوشته شده‌اند.
• بر روی وجه‌های تاس B اعداد ۵و ۵و ۵و ۲و ۲و ۲ نوشته شده‌اند.
• بر روی وجه‌های تاس C اعداد ۴و ۴و ۴و ۴و ۴ و۱ نوشته شده‌اند.

پس از چند شکست، دوستتان مشکوک می‌شود بنابراین شما استراتژی بازی را برای او توضیح می‌دهید. اکنون می‌توانید به دوست خود شانس دیگری دهید و ابتدا شما تاسی را انتخاب نمایید. با این حساب دوست شما می‌تواند تاسی را انتخاب کند که با احتمال بیشتر از نیم از شما می‌برد. اما در این دور از بازی هر شخص دوبار تاس می‌ریزد و مجموع مقایسه می‌شوند. انتظار می‌رود دوست شما شانس بیشتری در برنده شدن داشته باشد درحالی که چنین نیست! با دوبار تاس ریختن زنجیره برعکس می‌شود و این گونه همچنان شما برنده خواهید بود. احتمالات برنده شدن به شرح زیر هستند:

$Pr(A>C)={\frac {671}{1296}}$

$Pr(C>B)={\frac {85}{144}}$

$Pr(B>A)={\frac {85}{144}}$

انواعی از تاس‌های ناگذرا

تاس‌های افرون

تاس‌های افرون

ایدهٔ تاس‌های ناگذرا از اوایل دهه ۷۰ میلادی مطرح بوده‌است. یکی از مجموعه تاس‌های ناگذرا معروف، تاس‌های افرون هستند که توسط دانشمند آماری بردلی افرون مطرح شده‌اند. این مجموعه شامل چهار تاس به صورت زیر می‌باشد:

• بر روی وجه‌های تاس A اعداد ۴و ۴و ۴و ۴و ۰و ۰ نوشته شده‌اند.
• بر روی وجه‌های تاس B اعداد ۳و ۳و ۳و ۳و ۳و ۳ نوشته شده‌اند.
• بر روی وجه‌های تاس C اعداد ۶و ۶و ۲و ۲و ۲و ۲ نوشته شده‌اند.
• بر روی وجه‌های تاس D اعداد ۵و ۵و ۵و ۱و ۱و ۱ نوشته شده‌اند.

احتمالات

برای هر زوج متوالی میان تاس‌های بالا احتمال برد را محاسبه می‌کنیم:

• مقدار تاس B ثابت است بنابراین A آن را در ${\frac {2}{3}}$ حالات یعنی چهار حالتی که ۴ باشد شکست می‌دهد.
• به‌طور مشابهی، B در ${\frac {2}{3}}$ حالات C را شکست می‌دهد.
• احتمال برد C در برابر D را در دو حالت بررسی می‌کنیم:
  • اگر C مقدرا ۶ بگیرد، مستقل از D می‌برد.
  • اگر C مقدار ۲ بگیرد، تنها هنگامی می‌برد که D مقدار ۱ داشته باشد؛ بنابراین احتمال کل برد C می‌شود:

$\left({1 \over 3}\times 1\right)+\left({2 \over 3}\times {1 \over 2}\right)={2 \over 3}$

• به‌طور مشابه برای احتمال برد D در برابر A می‌شود

$\left({1 \over 2}\times 1\right)+\left({1 \over 2}\times {1 \over 3}\right)={2 \over 3}$

پس به صورت خلاصه داریم:

$Pr(A>B)=Pr(B>C)=Pr(C>D)=Pr(D>A)={2 \over 3}$

بهترین انتخاب

اکنون با فرض این که تاس دوم به صورت تصادفی انتخاب می‌شود، احتمال برد هر تاس و درنتیجه بهترین انتخاب ممکن را بررسی می‌کنیم:

• احتمال برد A در برابر یک تاس تصادفی:

${1 \over 3}\times \left({2 \over 3}+{1 \over 3}+{4 \over 9}\right)={13 \over 27}$

• احتمال برد B در برابر یک تاس تصادفی:

${1 \over 3}\times \left({2 \over 3}+{1 \over 3}+{1 \over 2}\right)={1 \over 2}$

• احتمال برد C در برابر یک تاس تصادفی:

${1 \over 3}\times \left({2 \over 3}+{1 \over 3}+{5 \over 9}\right)={14 \over 27}$

• احتمال برد D در برابر یک تاس تصادفی:

${1 \over 3}\times \left({2 \over 3}+{1 \over 3}+{1 \over 2}\right)={1 \over 2}$

بنابراین بهترین شانس برنده شدن برای تاس C با احتمال ۰٫۵۱۸۵ می‌باشد.

تاس‌های ناگذرا برای بیشتر از دو بازیکن

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

حالت سه بازیکن

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

تاس‌های اسکار

پازل ساز هلندی اسکار ون دونتر مجموعه‌ای از هفت تاس ناگذرا، با مقادیر ۱ تا ۲۱ پیشنهاد داده‌است. این تاس‌ها هرکدام با احتمال ${\frac {5}{9}}$ تاسی دیگر را به صورت ناگذرا شکست می‌دهند. اگر تاس‌ها عادی بودند احتمال شکست دادن همزمان هر دو رقیب چیزی حدود ۲۵٪ می‌شد. اما احتمال شکست دادن هر دو رقیب با تاس‌های اسکار حدود ۳۹٪ است. مسئله یافتن حالت بیشینه برای احتمال برد تاس‌ها همچنان قابل بحث است و راه حلی به جز جستجوی فراگیر تا برای آن ارائه نشده است.

تاس‌های گریم

دکتر جیمز گریم مجموعه‌ای از ۵ تاس به شرح زیر را ارائه کرده‌است:

• بر روی وجه‌های تاس A اعداد ۷و ۷و ۷و ۲و ۲و ۲ نوشته شده‌اند.
• بر روی وجه‌های تاس B اعداد ۶و ۶ و۶ و۶ و۱ و۱ نوشته شده‌اند.
• بر روی وجه‌های تاس C اعداد ۵و ۵ و۵ و۵ و۵ و۰ نوشته شده‌اند.
• بر روی وجه‌های تاس D اعداد ۹و ۴ و۴ و۴ و۴ و۴ نوشته شده‌اند.
• بر روی وجه‌های تاس E اعداد ۸و ۸و ۳و ۳و ۳و ۳ نوشته شده‌اند.

فرض کنید رابطهٔ تاس A تاس B را شکست می‌دهد با A->B نشان دهیم. در این مجموعه، اگر یک بار تاس بریزیم:

• A -> B -> C -> D -> E -> A
• A -> C -> E -> B -> D -> A

هرچند اگر دو بار تاس بریزیم زنجیره اول تغییری نمی‌کند اما زنجیره دوم معکوس می‌شود (A -> D -> B -> E -> C -> A). بنابراین مستقل از این که دو رقیب دیگر چه تاسی انتخاب می‌کنند، نفر سوم می‌تواند تاسی بردارد که هر دو را شکست دهد. تنها باید پس از انتخاب تاس مشخص کند که یک بار تاس ریخته می‌شود یا دو بار.

وارن بافت

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Nontransitive dice». در دانشنامهٔ ویکی‌پدیای انگلیسی.

پیوند به بیرون

• MathWorld page
• Ivars Peterson's MathTrek - Tricky Dice Revisited (۱۵ آوریل ۲۰۰۲)
• Jim Loy's Puzzle Page
• Miwin official site (German)
• Open Source nontransitive dice finder بایگانی‌شده در ۲ آوریل ۲۰۱۵ توسط Wayback Machine
• Nontransitive Dice by James Grime
• mgf.winkelmann Miwins intransitive Dodekaeder
• Maths Gear
• Conrey, B., Gabbard, J., Grant, K., Liu, A., & Morrison, K. (2016). Intransitive dice. Mathematics Magazine, 89(2), 133-143. Awarded by Mathematical Association of America
• Timothy Gowers' project on intransitive dice