{"id":881,"date":"2016-07-29T19:00:01","date_gmt":"2016-07-30T00:00:01","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=881"},"modified":"2016-09-03T18:52:55","modified_gmt":"2016-09-03T23:52:55","slug":"the-traitorous-generals","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/the-traitorous-generals\/","title":{"rendered":"The Traitorous Generals"},"content":{"rendered":"<p>This <a href=\"http:\/\/fivethirtyeight.com\/features\/can-you-sniff-out-the-traitorous-generals\/\">Riddler problem<\/a> is a logic puzzle about liars and truth-tellers.<\/p>\n<blockquote><p>\nYou are the emperor of Byzantium (lucky you!) and you have N generals working for you. You know that more than half of your generals are loyal, and the rest are traitors. You can ask any general about the loyalty of any other general: If the general you ask is loyal, he will answer correctly, but if he is a traitor he can answer however he likes. Your goal is to find one general you are absolutely certain is loyal while asking the fewest possible questions.<\/p>\n<p>What is the minimum number of questions (in terms of N) that will guarantee a solution, and what strategy produces it?\n<\/p><\/blockquote>\n<p>There is a problem in cryptography known as the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Byzantine_fault_tolerance\">Byzantine Generals Problem<\/a>, which has to do with achieving consensus in the presence of traitors that can sabotage communications. The Riddler problem above also involves liars and truth-tellers, but it&#8217;s a very different problem.<\/p>\n<p>The following is adapted from a comment by <a href=\"http:\/\/theorie.ikp.physik.tu-darmstadt.de\/qcd\/\">Guy Moore<\/a>. A similar solution that obtains the same final result was also found by <a href=\"http:\/\/web.mit.edu\/dmytro\/www\/main.htm\">Dmytro Taranovsky<\/a>. Thank you both for your insights!<\/p>\n<p><a href=\"javascript:Solution('soln_generals','toggle_generals')\" id=\"toggle_generals\">[Show Solution]<\/a><\/p>\n<div id=\"soln_generals\" style=\"display: none\">\nThe $N$ generals have the property that there is a loyal majority. This solution efficiently eliminates generals such that the remaining group of generals preserves the loyalty majority property. The strategy is:<\/p>\n<ol>\n<li> If there is an even number of generals, eliminate one of the generals (doesn&#8217;t matter which).<\/li>\n<li> If there is an odd number of generals, set one general aside. Pair up the rest of the generals and for each pair, ask the first general if the second one is a traitor.\n<ul>\n<li> If the first general says the other is a traitor, eliminate both generals.<\/li>\n<li> If the first general says the other is loyal, eliminate the first general and keep the second.<\/li>\n<\/ul>\n<li> If we kept an odd number of generals, eliminate the general that was set aside. Otherwise, re-include the general that was set aside.\n<li> If there is only one general left, this general is loyal and we may stop. Otherwise, return to the first step and repeat the process with the generals that are left.<\/li>\n<\/ol>\n<h3>Why does this work?<\/h3>\n<p>At each step, the loyalty majority property is preserved. To see why, let&#8217;s examine each case.<\/p>\n<ul>\n<li> If the first general says the second is a traitor, they cannot both be loyal. Therefore, by eliminating both, we eliminate at least as many traitors as loyal generals.<\/li>\n<li> If the first general says the second is loyal, we eliminate the first one. If the general that remains is a traitor, then both of them were traitors. This can happen for at most half of the pairs, since otherwise there would be a majority of traitors. If it happens for exactly half of the pairs, then the general we set aside must be loyal and so by re-including the general we set aside we retain loyal majority.<\/li>\n<li> If there is only one general remaining, then the loyalty majority implies that this general must be loyal.<\/li>\n<\/ul>\n<h3>How well does the strategy perform?<\/h3>\n<p>If we have $k$ generals, we ask $\\left\\lfloor{\\frac{k-1}{2}}\\right\\rfloor$ questions. In the worst case, each question leads to only one elimination. We also re-include the general we set aside depending on parity. So the number of generals remaining in the next round is:<\/p>\n<p>\\[<br \/>\n\\begin{cases}<br \/>\n\\left\\lfloor\\frac{k-1}{2}\\right\\rfloor &#038; \\text{if }k\\text{ is odd}\\\\<br \/>\n\\left\\lfloor\\frac{k-1}{2}\\right\\rfloor + 1 &#038; \\text{if }k\\text{ is even}<br \/>\n\\end{cases}<br \/>\n\\]<\/p>\n<p>This is equivalent to<\/p>\n<p>\\[<br \/>\n1 + 2\\left\\lfloor\\frac{1}{2}\\left\\lfloor\\frac{k-1}{2}\\right\\rfloor\\right\\rfloor = 1 + 2\\left\\lfloor\\frac{k-1}{4}\\right\\rfloor<br \/>\n\\]<\/p>\n<p>We can make this simplification thanks to the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Floor_and_ceiling_functions#Nested_divisions\">nested division property<\/a> of the floor function. So if $q(k)$ is the maximum number of questions required, we have the recursion:<\/p>\n<p>\\begin{align}<br \/>\nq(1) &#038;= 0 \\\\<br \/>\nq(k) &#038;= \\left\\lfloor{\\tfrac{k-1}{2}}\\right\\rfloor + q\\left( 1 + 2\\left\\lfloor{\\tfrac{k-1}{4}}\\right\\rfloor \\right)<br \/>\n\\end{align}<\/p>\n<p>If we define $f(k) = k-q(k+1)$ and do some rearrangements, we can write the following recursion for $f(k)$:<\/p>\n<p>\\begin{align}<br \/>\nf(0) &#038;= 0 \\\\<br \/>\nf(k) &#038;= k- \\left\\lfloor{\\tfrac{k}{2}}\\right\\rfloor- 2\\left\\lfloor{\\tfrac{k}{4}}\\right\\rfloor + f\\left(1+2\\left\\lfloor{\\tfrac{k}{4}}\\right\\rfloor\\right)<br \/>\n\\end{align}<\/p>\n<p>It turns out that $f(k)$ is the number of 1&#8217;s in the binary representation of $k.$ Or, equivalently, $f(k)$ is the sum of the binary digits of $k$. I&#8217;ll omit the derivation, but you can work it out by writing $k$ in binary and noting that each operation does something simple to the digits. For example, if $x = abcde_2$ then $\\lfloor x\/2 \\rfloor = abcd_2$. Therefore, we conclude that if there are $N$ generals, the number of questions required in order to ensure we can select a loyal general is:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nq(N) = N-1-f(N-1)<br \/>\n$<\/span><\/p>\n<p>where $f(k)$ is the number of 1&#8217;s in the binary representation of $k.$ Here is a plot showing the questions needed as a function of the number of generals.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals_correct.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals_correct-1024x657.png\" alt=\"generals_correct\" width=\"840\" height=\"539\" class=\"aligncenter size-large wp-image-899\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals_correct-1024x657.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals_correct-300x192.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals_correct-768x492.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals_correct-1200x770.png 1200w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals_correct.png 1784w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>We always require slightly fewer questions that there are generals, and we can bound the number of questions as:<\/p>\n<p>\\[<br \/>\nN-1-\\log_2(N) \\le q(N) \\le N-2<br \/>\n\\]<\/p>\n<\/div>\n<p><!--\nHere is my solution:\n<a href=\"javascript:Solution('soln_generals','toggle_generals')\" id=\"toggle_generals\">[Show Solution]<\/a>\n\n\n<div id=\"soln_generals\" style=\"display: none\">\n\nLet $f(k)$ be the minimum number of questions we must ask in order to definitively identify a loyal general given that there are at most $k$ traitors. We will now evaluate $f$ recursively.\n\n<b>One traitor:<\/b> For the base case, $f(1) = 2$. The strategy is to pick two generals and ask each of them about a third general, whom we'll call $X$. This requires two queries, and there are several possible cases:\n\n\n<ol>\n\n\n<li> If both agree that $X$ is loyal, then $X$ is definitely loyal.<\/li>\n\n\n\n\n<li> If both agree that $X$ is a traitor, then $X$ is definitely a traitor, which means the generals we queried are both definitely loyal.<\/li>\n\n\n\n\n<li> If there is disagreement about $X$ then one of the generals we asked must be a traitor, which means $X$ is definitely loyal.<\/li>\n\n\n<\/ol>\n\n\n\n<b>$k$ traitors:<\/b> We'll show that $f(k) = 2k + f(k-1)$. The strategy is to pick $2k$ generals, and ask each of them about another general, whom we'll call $X$. This requires $2k$ queries, and here are the possible cases:\n\n\n<ol>\n\n\n<li> If all agree that $X$ is loyal, then $X$ is definitely loyal.<\/li>\n\n\n\n\n<li> If all agree that $X$ is a traitor, then $X$ is definitely a traitor. We can exclude the traitorous general and so we will require an additional $f(k-1)$ queries to find a loyal general, bringing our total to $f(k)=2k+f(k-1)$ total queries.<\/li>\n\n\n\n\n<li> If there is disagreement about $X$ then we can divide the $2k$ generals we queried into two groups depending on what they said about $X$. At most $k$ generals are traitors by definition therefore at least $k+1$ are loyal. The loyal generals must mutually agree, so they all deliver the same verdict about $X$ (and therefore all belong to the same group). Here are the possibilities:\n\n\n<ul>\n\n\n<li>There is an equal split: $k$ say that $X$ is loyal and the other $k$ say that $X$ is a traitor. In this case, one of these two groups is entirely loyal and the other is entirely traitorous. Therefore, the final remaining loyal general must be $X$.<\/li>\n\n\n\n\n<li>If one group has more than $k$ members, the other group will have fewer than $k$, which means it cannot contain all the loyal generals. So if the larger group says that $X$ is loyal, then $X$ is definitely loyal.<\/li>\n\n\n\n\n<li>Likewise, if the larger group says $X$ is a traitor, then $X$ is definitely a traitor, and so are all the members of the smaller group. We can therefore exclude all of the traitors and $f(k) = 2k + f(k-1-s)$ where $s$ is the number of generals in the smaller group.<\/li>\n\n\n<\/ul>\n\n\n<\/ol>\n\n\nOut of all the scenarios, the worst-case one is the second one, which leads to $f(k) = 2k+f(k-1)$. We can solve this recursion and obtain:\n\n\\[\nf(k) = 2k+f(k-1) = \\dots = 2k+(2k-1)+\\dots+2+1 = k(k+1)\n\\]\n\nIn the original problem statement, we have $N$ generals and at most $k=\\lfloor{\\tfrac{N-1}{2}}\\rfloor$ of them are traitors. Here, $\\lfloor{x}\\rfloor$ denotes the integer part (round down) of $x$. Therefore, the number of questions required to find a loyal general is\n\n\n\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle\n\\text{number of questions} = \\left\\lfloor\\frac{N-1}{2}\\right\\rfloor \\left\\lfloor\\frac{N+1}{2}\\right\\rfloor\n$<\/span><\/p>\n\n\n\nAn alternate equivalent formula is $\\lceil\\tfrac{N}{2}\\rceil (\\lceil\\tfrac{N}{2}\\rceil-1)$, where $\\lceil{x}\\rceil$ is the smallest integer greater than or equal to $x$ (round $x$ up). Here is a plot showing how many questions are needed as a function of the number of generals.\n\n<a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals-1024x663.png\" alt=\"generals\" width=\"840\" height=\"544\" class=\"aligncenter size-large wp-image-893\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals-1024x663.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals-300x194.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals-768x497.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals-1200x777.png 1200w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/07\/generals.png 1832w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a>\n\nMore simply put:\n\n\n<ul>\n\n\n<li> For 3 or 4 generals (up to 1 traitor), it takes at most $2$ questions to find a loyal general.<\/li>\n\n\n\n\n<li> For 5 or 6 generals (up to 2 traitors), it takes at most $2+4 = 6$ questions to find a loyal general.<\/li>\n\n\n\n\n<li> For 7 or 8 generals (up to 3 traitors), it takes at most $2+4+6 = 12$ questions to find a loyal general.<\/li>\n\n\n<\/ul>\n\n\nand so on.\n<\/div>\n\n\n\n--><\/p>\n","protected":false},"excerpt":{"rendered":"<p>This Riddler problem is a logic puzzle about liars and truth-tellers. You are the emperor of Byzantium (lucky you!) and you have N generals working for you. You know that more than half of your generals are loyal, and the rest are traitors. You can ask any general about the loyalty of any other general: &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/the-traitorous-generals\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;The Traitorous Generals&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[23,24,15,2],"class_list":["post-881","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-logic","tag-pigeonhole-principle","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/881","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=881"}],"version-history":[{"count":21,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/881\/revisions"}],"predecessor-version":[{"id":907,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/881\/revisions\/907"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=881"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=881"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=881"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}