قضیه رأی‌گیری برترند

فرض کنید در یک انتخابات کاندید $A$ ، $a$ رأی و کاندید $B$ ، $b$ رأی به دست می‌آورد؛ به طوری که $a>kb$ ( $k$ یک عدد صحیح مثبت است). تعداد (یا احتمال) حالاتی را به دست آورید که در تمام طول رأی‌گیری آرای $A$، دست کم $k$ تا بیشتر از آرای $B$ باشد.
پاسخ ${\frac {a-kb}{a+b}}{\binom {a+b}{a}}$ است. (احتمال آن برای حالت $k=1$ برابر با ${\frac {a-b}{a+b}}$ است.)

تاریخچه

در سال ۱۸۸۷ جوزف برترند که مسئلهٔ رأی‌گیری را بیان کرده‌بود برای حالت خاص $k=1$ راه حلی از طریق روابط بازگشتی ارائه داد و خواستار راه حل مستقیمی برای آن شد. بلافاصله بعد از آن که برترند پرسش خود را مطرح کرد E ́mile Barbier راه‌حلی برای هر $k$ اختیاری مطرح کرد اما هیچ اثباتی برای آن نداشت. اندکی بعد Désiré André اثبات ترکیبیاتی کوتاهی برای حالت $k=1$ مسئلهٔ برترند داد. در سال ۱۹۲۳ Aeppli اعلام کرد که اولین اثبات برای قضیهٔ رأی‌گیری به ازای $k\geq 1$ دارد و به خوانندگان مشتاق مقالهٔ دکتری خود را پیشنهاد کرد.

مثال

فرض کنید $k=1$ است. ۵ رأی‌دهنده داریم که ۳نفر به $A$ و ۲نفر به $B$ رأی خواهند داد. ( $1\times 2\leq 3$ ) می‌خواهیم در طول رأی‌گیری همواره تعداد رای‌های $A$ بیشتر از $B$ باشد. ۱۰ حالت برای ترتیب رأی‌ها وجود دارد:

• $AAABB$
• $AABAB$
• $ABAAB$
• $BAAAB$
• $AABBA$
• $ABABA$
• $BAABA$
• $ABBAA$
• $BABAA$
• $BBAAA$
  

در جدول زیر تعداد آرای هر کاندید را در هر مرحله از رأی‌گیری برای حالت $BABAA$ بررسی می‌کنیم:

A	A	B	A	B	رأی
۳	۳	۲	۲	۱	A
۲	۱	۱	۰	۰	B

برای هر ستون تعداد آرای A بیشتر از B است. برای حالت $AABBA$ در هر مرحله از رأی‌گیری داریم:

A	A	B	B	A	رأی
۳	۲	۲	۲	۱	A
۲	۲	۱	۰	۰	B

در این حالت تعداد رأی‌های $B$ در مرحلهٔ چهارم به $A$ رسیده. از بین ۱۰حالت ممکن برای ترتیب آرا تنها در ۲حالت $AABAB$ و $AAABB$ همواره تعداد رای‌های $A$ بیشتر از $B$ است که برابر مقدار ${\frac {3-2}{3+2}}{\binom {5}{3}}$ می‌باشد.
و احتمال آن ${\frac {2}{10}}$ است که برابر ${\frac {3-2}{3+2}}$ می‌باشد.

اثبات با انعکاس برای حالت $k=1$

آندره برای به دست آوردن تعداد حالت‌های مطلوب مسئله، حالت‌های نامطلوب را از تعداد کل حالات کم کرد. فرض کنید تعداد آرای کاندید $A$ ، $a$ تا و تعداد آرای کاندید $B$ ، $b$ تا باشد. می‌دانیم تمام جایگشت‌هایی که با $B$ شروع شوند نامطلوبند. می‌خواهیم تناظر یک به یکی بین جایگشت‌های نامطلوبی که با $A$ شروع می‌شوند و تمام جایگشت‌هایی که با $B$ شروع می‌شوند برقرار کنیم.
گره را نقطه‌ای تعریف می‌کنیم که تعداد رأی‌های $A$ و $B$ برابر باشند. اگر همواره آرای $A$ بیشتر از $B$ باشد نباید به گره‌ای برخورد کنیم. از آنجایی که تعداد رأی‌های $A$ بیشتر از $B$ است اگر رأی اول برای کاندید $B$ باشد بالاخره به گره می‌رسیم. برای هر رشته که با $A$ شروع شود و گره داشته باشد رأی‌ها را تا رسیدن به اولین گره معکوس می‌کنیم (یعنی هر $A$ را به $B$ تبدیل می‌کنیم و برعکس) و رشته‌ای که با $B$ شروع می‌شود می‌سازیم. به‌طور مشابه هر رشته‌ای که با $B$ شروع می‌شود را به رشته‌ای که با $A$ شروع می‌شود و گره دارد (نامطلوب است) تبدیل می‌کنیم. (می‌دانیم معکوس معکوس هر رأی همان رأی است. اگر ۲تبدیل‌یافته یکسان باشند معکوس تا گرهٔ اول آن‌ها که همان رشته‌هایی هستند که از آنها به دست آمده‌اند هم یکسان اند پس این تبدیل‌ها یک به یک است) در نتیجه تناظری یک به یک داریم. تعداد حالاتی که با $B$ شروع می‌شوند معادل جایگشت‌هایی است که می‌توان با $a$ تا $A$ و $b-1$ تا $B$ ساخت یعنی ${\binom {a+b-1}{b-1}}$.
در نتیجه تعداد حالات مطلوب از روابط زیر به‌دست می‌آید:
${\binom {a+b}{a}}-2{\binom {a+b-1}{a}}={\frac {a-b}{a+b}}{\binom {a+b}{a}}$
و احتمال و قوع آن برابر ${\frac {{\frac {a-b}{a+b}}{\binom {a+b}{a}}}{\binom {a+b}{a}}}={\frac {a-b}{a+b}}$ خواهدبود.

تعمیم‌یافته: مجاز بودن تساوی آرا

مسئلهٔ اصلی یافتن احتمال آن است که همواره تعداد رأی‌های کاندید اول اکیداً بیشتر از کاندید دوم باشد. حال فرض کنید می‌خواهیم احتمال آن را به دست بیاوریم که هیچگاه تعداد رأی‌های کاندید دوم از کاندید اول بیشتر نشود (یعنی وجود گره مجاز باشد). در این حالت پاسخ برابر ${\frac {a-b+1}{a+1}}{\binom {a+b}{a}}$ خواهدبود. مسئلهٔ جدید را می‌توان با روش معکوس کردن مشابه مسئلهٔ اصلی حل نمود. تعداد کل رشته‌هایی که با $a$ تا $A$ و $b$ تا $B$ برای حالات رأی‌گیری می‌توان ساخت برابر است با : ${\binom {a+b}{a}}$. هر رشتهٔ رأی‌گیری را به صورت مسیر شبکه ای روی صفحهٔ دکارتی نمایش می‌دهیم به‌طوری که:

• مسیر را از نقطهٔ (۰٬۰) شروع می‌کنیم.
• به ازای هر رأی $A$ یک واحد به راست حرکت می‌کنیم.
• به ازای هر رأی $B$ یک واحد به بالا حرکت می‌کنیم.
  

تناظر یک به یکی بین رشته‌ها و مسیرهای بین نقاط $(0,0)$ و $(a,b)$ با محدودیت حرکت به راست و بالا وجود دارد. یک رشته نامطلوب است اگر زمانی کاندید دوم رأی بیشتری از کاندید اول کسب کند یعنی مسیر متناظر آن از خط $y=x$ عبور کرده و به خط $y=x+1$ اصابت کند.

مسیر نامطلوب (آبی) و بازتاب شده‌اش (قرمز)

نقطهٔ شروع تا اولین تلاقی هر مسیر نامطلوب با خط $y=x+1$ را نسبت به خط مذکور قرینه می‌کنیم. مسیرهای جدید به دست آمده مسیری بین نقاط $(-1,1)$ و $(a,b)$ خواهد بود. به‌طور مشابه با اثبات مسئلهٔ اصلی مسیرهای نامطلوب از $(0,0)$ به $(a,b)$ تناظر یک به یکی با مسیرهای بین نقاط $(-1,1)$ و $(a,b)$ با محدودیت حرکت به راست و بالا دارند. تعداد این مسیرها ${\binom {a+b}{a+1}}$ است پس تعداد مسیرهای مطلوب به صورت زیر به دست می‌آید:
${\binom {a+b}{a}}-{\binom {a+b}{a+1}}={\frac {a-b+1}{a+1}}{\binom {a+b}{a}}$

و احتمال وقوع آن برابر ${\frac {{\frac {a-b+1}{a+1}}{\binom {a+b}{a}}}{\binom {a+b}{a}}}={\frac {a-b+1}{a+1}}$ خواهدبود.

در حقیقت راه حل مسئله بالا و مسئلهٔ اصلی مرتبطند. برای اینکه تعداد رأی کاندید $A$ همواره اکیداً بیشتر از کاندید $B$ باشد باید رأی اول را $A$ بیاورد و بعد از آن بدون در نظر گرفتن رأی اول، تعداد رأی‌هایش بزرگتر یا مساوی آرای $B$ باشد پس مانند این است که مسئلهٔ بالا را با $a-1$ رأی برای $A$ و $b$ رأی برای $B$ حل کنیم:

${\frac {a-1-b+1}{a-1+1}}{\binom {a+b-1}{a-1}}={\frac {a-b}{a}}{\frac {(a+b-1)!}{(a-1)!b!}}{\frac {a+b}{a+b}}={\frac {a-b}{a+b}}{\frac {(a+b)!}{a!b!}}={\frac {a-b}{a+b}}{\binom {a+b}{a}}$