<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@e98f377558364fff9931553a57df012d" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">The Easy Hat-Problem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@950e4b80ed924252a486b56e4601372f">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@950e4b80ed924252a486b56e4601372f" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h3><span style="font-family: 'book antiqua', palatino;">The Easy Hat-Problem </span><br /><span style="font-family: 'book antiqua', palatino;"> Paradox Grade: 0</span></h3>
<p><span style="font-family: 'book antiqua', palatino;">You may have heard of the following brain teaser:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;"><em>Setup:</em> Ten prisoners, <span class="math inline">\(P_1, P_2,\ldots P_{10}\)</span>, are standing in line. <span class="math inline">\(P_1\)</span> is at the end of the line, in front of her is <span class="math inline">\(P_2\)</span>, in front of him is <span class="math inline">\(P_3\)</span>, and so forth, with <span class="math inline">\(P_{10}\)</span> standing at the front of the line. Each of them is wearing a hat. The color of each prisoner’s hat determined by the toss of a fair coin: people whose coin lands Heads get a blue hat, people whose coin lands Tails get a red hat. Nobody knows the color of her own hat, but each prisoner can see the colors of the hats of everyone standing in front of her. (For instance, <span class="math inline">\(P_6\)</span> can see the colors of the hats worn by <span class="math inline">\(P_7,P_8,P_9,\)</span> and <span class="math inline">\(P_{10}\)</span>.) Now assume that a guard will start at the end of the line, and ask each prisoner to guess the color of her own hat. Prisoners answer in turn, with everyone being in a position to hear the answers of everyone else. Prisoners who correctly call out the color of their own hats will be spared. Everyone else will be shot.</span></p>
<p><span style="font-family: 'book antiqua', palatino;"><em>Problem:</em> if the prisoners are allowed to confer with each other beforehand, is there a strategy they can agree upon in advance to improve their chances of surviving?</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">The answer is "yes". </span></p>
<p><span style="font-family: 'book antiqua', palatino;">In fact, the prisoners can guarantee that <span class="math inline">\(P_2,\ldots,P_{10}\)</span> survive, and that <span class="math inline">\(P_1\)</span> gets a 50% chance of survival. (I’ll ask you to verify this in the exercise below.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">That’s a fun puzzle. It’s a bit tricky, but it’s certainly not paradoxical. Here we will be concerned with a much harder version of the hat-problem, one which arguably <em>is</em> paradoxical. Read on …</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@2ee18824e79c43f49ca0f72786fbeb9d">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@2ee18824e79c43f49ca0f72786fbeb9d" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_2ee18824e79c43f49ca0f72786fbeb9d" class="problems-wrapper" role="group"
aria-labelledby="2ee18824e79c43f49ca0f72786fbeb9d-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@2ee18824e79c43f49ca0f72786fbeb9d" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@2ee18824e79c43f49ca0f72786fbeb9d/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="2ee18824e79c43f49ca0f72786fbeb9d-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@2ee18824e79c43f49ca0f72786fbeb9d-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@2ee18824e79c43f49ca0f72786fbeb9d-problem-progress"></div>
<div class="problem">
<div>
<p>
<span style="font-family: 'book antiqua', palatino;">Identify a strategy that guarantees that <span class="math inline">\(P_2,\ldots,P_{10}\)</span> survive, and gives <span class="math inline">\(P_1\)</span> a 50% chance of survival.</span>
</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_2ee18824e79c43f49ca0f72786fbeb9d_2_1">
<fieldset aria-describedby="status_2ee18824e79c43f49ca0f72786fbeb9d_2_1">
<div class="field">
<input type="radio" name="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1" id="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="2ee18824e79c43f49ca0f72786fbeb9d_2_1-choice_0-label" for="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_2ee18824e79c43f49ca0f72786fbeb9d_2_1">
<span style="font-family: 'book antiqua', palatino;">Each person, <span class="math inline">\(P_1,\ldots,P_{10}\)</span>, looks at the color of the hat immediately in front of them. If the person sees a red hat, they say "Blue!". If they see a blue hat, they say "Red!". </span>
</label>
</div>
<div class="field">
<input type="radio" name="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1" id="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="2ee18824e79c43f49ca0f72786fbeb9d_2_1-choice_1-label" for="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_2ee18824e79c43f49ca0f72786fbeb9d_2_1">
<span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(P_1\)</span> announce "Red!" if they see more red hats than blue hats. Announce "Blue!" otherwise.</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1" id="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="2ee18824e79c43f49ca0f72786fbeb9d_2_1-choice_2-label" for="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_2ee18824e79c43f49ca0f72786fbeb9d_2_1">
<span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(P_1\)</span> announce "Red!" if they see an odd number of red hats and announce "Blue!" otherwise.</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1" id="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="2ee18824e79c43f49ca0f72786fbeb9d_2_1-choice_3-label" for="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_2ee18824e79c43f49ca0f72786fbeb9d_2_1">
<span style="font-family: 'book antiqua', palatino;">Person <span class="math inline">\(P_1\)</span> announces the color of the hat of person <span class="math inline">\(P_2\)</span>. Everyone else announces <i>the opposite</i> of the color that was announced previously.</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1" id="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="2ee18824e79c43f49ca0f72786fbeb9d_2_1-choice_4-label" for="input_2ee18824e79c43f49ca0f72786fbeb9d_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_2ee18824e79c43f49ca0f72786fbeb9d_2_1">
<span style="font-family: 'book antiqua', palatino;">Let everyone announce "red!" if they see an even number of blue hats and announce "Blue!" otherwise.</span>
</label>
</div>
<span id="answer_2ee18824e79c43f49ca0f72786fbeb9d_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_2ee18824e79c43f49ca0f72786fbeb9d_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_2ee18824e79c43f49ca0f72786fbeb9d_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_2ee18824e79c43f49ca0f72786fbeb9d" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_2ee18824e79c43f49ca0f72786fbeb9d">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="2ee18824e79c43f49ca0f72786fbeb9d-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="2ee18824e79c43f49ca0f72786fbeb9d-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="2ee18824e79c43f49ca0f72786fbeb9d-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@5992963aeb8d44c393367c3ee7c22e9b" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">The Hard Hat-Problem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@1395b72a20464b2a86e483beb35fcbfe">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@1395b72a20464b2a86e483beb35fcbfe" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h3><span style="font-family: 'book antiqua', palatino;">Bacon's Puzzle </span><br /><span style="font-family: 'book antiqua', palatino;"> Paradox Grade: 7</span></h3>
<p></p>
<p><span style="font-family: 'book antiqua', palatino;">Let me now tell you about a hard version of the hat-problem, which is due to University of Southern California philosopher Andrew Bacon.</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;"><em>Setup:</em> As before, we have a line of prisoners. They are all wearing hats, and for each prisoner, a coin was flipped to determine whether to give her a red hat or a blue hat. This time, however, the prisoners form an <span class="math inline">\(\omega\)</span>-sequence, with one prisoner for each natural number: <span class="math inline">\(P_1,P_2,P_3,\dots\)</span>. As before, <span class="math inline">\(P_1\)</span> is at the very end of the line, in front of her is <span class="math inline">\(P_2\)</span>, in front of him is <span class="math inline">\(P_3\)</span>, and so forth. Each prisoner knows her position in line. As before, each person in the sequence can see the hats of the prisoners in front of her, but cannot see her own hat (or the hat of anyone behind her). This time, however, the prisoners will not be called on one at a time to guess their hat color; instead, at a set time, everyone has to guess the color of her own hat by crying out “Red!" or “Blue!" Everyone is to speak simultaneously, so that nobody’s guess can be informed by what others say. People who correctly call out the color of their own hats will be spared. Everyone else will be shot.</span></p>
<p><span style="font-family: 'book antiqua', palatino;"><em>Problem:</em> Find a strategy that <span class="math inline">\(P_1, P_2, P_3, \ldots\)</span> could agree upon in advance, and which would guarantee that at most finitely many people are shot.</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">Astonishingly, it is possible to find such a strategy. In fact, describing the strategy is relatively straightforward, and we shall do so shortly. The hard part, and the reason I give this puzzle a paradoxicality grade of 7, is making sense of the fact that the strategy exists.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: Bacon's Puzzle</h3>
<div
id="video_38d893f218034398817a4e553ca62f01"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01/handler/publish_completion", "streams": "1.00:y1yCpV0yYP8", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="38d893f218034398817a4e553ca62f01"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_38d893f218034398817a4e553ca62f01">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_38d893f218034398817a4e553ca62f01">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@38d893f218034398817a4e553ca62f01/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@a9c5be9b7f68431499f4b2222f7d6a21" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">The strategy: preliminaries</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@b4e0e5111ce34b16bb863948d0f15400">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@b4e0e5111ce34b16bb863948d0f15400" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Here is a strategy that <span class="math inline">\(P_1,P_2,\ldots\)</span> could use to guarantee that at most finitely many people get shot.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Let us represent an assignment of hats to individuals as an <span class="math inline">\(\omega\)</span>-sequence of zeroes and ones. A zero in the <span class="math inline">\(k\)</span>th position means that <span class="math inline">\(P_k\)</span>’s hat is red, and a one in the <span class="math inline">\(k\)</span>th position means that <span class="math inline">\(P_k\)</span>’s hat is blue. (So, for instance, the sequence <span class="math inline">\(\langle0,1,1,1,0,\ldots\rangle\)</span> represents a scenario in which <span class="math inline">\(P_1\)</span>’s hat is red, <span class="math inline">\(P_2\)</span>’s hat is blue, and so forth.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Let <span class="math inline">\(S\)</span> be the set of all <span class="math inline">\(\omega\)</span>-sequences of zeroes and ones. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">We’ll start by <strong>partitioning</strong> <span class="math inline">\(S\)</span>. In other words, we’ll divide <span class="math inline">\(S\)</span> into a family of non-overlapping "cells", whose union is \(S\). </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Cells are defined in accordance with the following principle:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">Sequences <span class="math inline">\(s\)</span> and <span class="math inline">\(s'\)</span> in <span class="math inline">\(S\)</span> are members of the same cell if and only if there are at most finitely many numbers <span class="math inline">\(k\)</span> such that the <span class="math inline">\(s\)</span> and <span class="math inline">\(s'\)</span> differ in the <span class="math inline">\(k\)</span>th position.</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">For instance, <span class="math inline">\(\langle0,0,0,0\ldots\rangle\)</span> and <span class="math inline">\(\langle1,0,0,0\ldots\rangle\)</span> are in the same cell because they differ only in the first position. But the <span class="math inline">\(\langle0,0,0,0\ldots\rangle\)</span> and <span class="math inline">\(\langle1,0,1,0\ldots\rangle\)</span> are in different cells because they differ in infinitely many positions.</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a4f233eb1034936acb5dcb8cec001b0">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a4f233eb1034936acb5dcb8cec001b0" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_9a4f233eb1034936acb5dcb8cec001b0" class="problems-wrapper" role="group"
aria-labelledby="9a4f233eb1034936acb5dcb8cec001b0-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a4f233eb1034936acb5dcb8cec001b0" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@9a4f233eb1034936acb5dcb8cec001b0/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="9a4f233eb1034936acb5dcb8cec001b0-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@9a4f233eb1034936acb5dcb8cec001b0-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@9a4f233eb1034936acb5dcb8cec001b0-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">For <span class="math inline">\(a,b,c \in S\)</span>, determine whether or not each of the following are true:</span>
</p>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(a\)</span> is in the same cell as itself.</span>
</p>
</blockquote>
<div class="choicegroup capa_inputtype" id="inputtype_9a4f233eb1034936acb5dcb8cec001b0_2_1">
<fieldset aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_2_1">
<div class="field">
<input type="radio" name="input_9a4f233eb1034936acb5dcb8cec001b0_2_1" id="input_9a4f233eb1034936acb5dcb8cec001b0_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="9a4f233eb1034936acb5dcb8cec001b0_2_1-choice_0-label" for="input_9a4f233eb1034936acb5dcb8cec001b0_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_2_1">
<span style="font-family: 'book antiqua', palatino;">True</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_9a4f233eb1034936acb5dcb8cec001b0_2_1" id="input_9a4f233eb1034936acb5dcb8cec001b0_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="9a4f233eb1034936acb5dcb8cec001b0_2_1-choice_1-label" for="input_9a4f233eb1034936acb5dcb8cec001b0_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_2_1">
<span style="font-family: 'book antiqua', palatino;">False</span>
</label>
</div>
<span id="answer_9a4f233eb1034936acb5dcb8cec001b0_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_9a4f233eb1034936acb5dcb8cec001b0_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_9a4f233eb1034936acb5dcb8cec001b0_solution_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">If <span class="math inline">\(a\)</span> is in the same cell as <span class="math inline">\(b\)</span>, then <span class="math inline">\(b\)</span> is in the same cell as <span class="math inline">\(a\)</span>.</span>
</p>
</blockquote>
<div class="choicegroup capa_inputtype" id="inputtype_9a4f233eb1034936acb5dcb8cec001b0_3_1">
<fieldset aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_3_1">
<div class="field">
<input type="radio" name="input_9a4f233eb1034936acb5dcb8cec001b0_3_1" id="input_9a4f233eb1034936acb5dcb8cec001b0_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="9a4f233eb1034936acb5dcb8cec001b0_3_1-choice_0-label" for="input_9a4f233eb1034936acb5dcb8cec001b0_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_3_1">
<span style="font-family: 'book antiqua', palatino;">True</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_9a4f233eb1034936acb5dcb8cec001b0_3_1" id="input_9a4f233eb1034936acb5dcb8cec001b0_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="9a4f233eb1034936acb5dcb8cec001b0_3_1-choice_1-label" for="input_9a4f233eb1034936acb5dcb8cec001b0_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_3_1">
<span style="font-family: 'book antiqua', palatino;">False</span>
</label>
</div>
<span id="answer_9a4f233eb1034936acb5dcb8cec001b0_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_9a4f233eb1034936acb5dcb8cec001b0_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_9a4f233eb1034936acb5dcb8cec001b0_solution_2"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">If <span class="math inline">\(a\)</span> is in the same cell as <span class="math inline">\(b\)</span> and <span class="math inline">\(b\)</span> is in the same cell as <span class="math inline">\(c\)</span>, then <span class="math inline">\(a\)</span> is in the same cell as <span class="math inline">\(c\)</span>.</span>
</p>
</blockquote>
<div class="choicegroup capa_inputtype" id="inputtype_9a4f233eb1034936acb5dcb8cec001b0_4_1">
<fieldset aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_4_1">
<div class="field">
<input type="radio" name="input_9a4f233eb1034936acb5dcb8cec001b0_4_1" id="input_9a4f233eb1034936acb5dcb8cec001b0_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="9a4f233eb1034936acb5dcb8cec001b0_4_1-choice_0-label" for="input_9a4f233eb1034936acb5dcb8cec001b0_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_4_1">
<span style="font-family: 'book antiqua', palatino;">True</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_9a4f233eb1034936acb5dcb8cec001b0_4_1" id="input_9a4f233eb1034936acb5dcb8cec001b0_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="9a4f233eb1034936acb5dcb8cec001b0_4_1-choice_1-label" for="input_9a4f233eb1034936acb5dcb8cec001b0_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_9a4f233eb1034936acb5dcb8cec001b0_4_1">
<span style="font-family: 'book antiqua', palatino;">False</span>
</label>
</div>
<span id="answer_9a4f233eb1034936acb5dcb8cec001b0_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_9a4f233eb1034936acb5dcb8cec001b0_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_9a4f233eb1034936acb5dcb8cec001b0_solution_3"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_9a4f233eb1034936acb5dcb8cec001b0" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_9a4f233eb1034936acb5dcb8cec001b0">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9a4f233eb1034936acb5dcb8cec001b0-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9a4f233eb1034936acb5dcb8cec001b0-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="9a4f233eb1034936acb5dcb8cec001b0-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@569b6a1f8bc84031a2e4faf7f65f822c">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@569b6a1f8bc84031a2e4faf7f65f822c" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_569b6a1f8bc84031a2e4faf7f65f822c" class="problems-wrapper" role="group"
aria-labelledby="569b6a1f8bc84031a2e4faf7f65f822c-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@569b6a1f8bc84031a2e4faf7f65f822c" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@569b6a1f8bc84031a2e4faf7f65f822c/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="569b6a1f8bc84031a2e4faf7f65f822c-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@569b6a1f8bc84031a2e4faf7f65f822c-problem-progress" tabindex="-1">
Problem 2
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@569b6a1f8bc84031a2e4faf7f65f822c-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">How many sequences does a given cell contain?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_569b6a1f8bc84031a2e4faf7f65f822c_2_1">
<fieldset aria-describedby="status_569b6a1f8bc84031a2e4faf7f65f822c_2_1">
<div class="field">
<input type="radio" name="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1" id="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="569b6a1f8bc84031a2e4faf7f65f822c_2_1-choice_0-label" for="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_569b6a1f8bc84031a2e4faf7f65f822c_2_1">
<span style="font-family: 'book antiqua', palatino;">\(|\mathbb{N}|\)</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1" id="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="569b6a1f8bc84031a2e4faf7f65f822c_2_1-choice_1-label" for="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_569b6a1f8bc84031a2e4faf7f65f822c_2_1">
<span style="font-family: 'book antiqua', palatino;">\(|\mathbb{R}|\)</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1" id="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="569b6a1f8bc84031a2e4faf7f65f822c_2_1-choice_2-label" for="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_569b6a1f8bc84031a2e4faf7f65f822c_2_1">
<span style="font-family: 'book antiqua', palatino;">\(2\)</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1" id="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="569b6a1f8bc84031a2e4faf7f65f822c_2_1-choice_3-label" for="input_569b6a1f8bc84031a2e4faf7f65f822c_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_569b6a1f8bc84031a2e4faf7f65f822c_2_1">
<span style="font-family: 'book antiqua', palatino;">None of the above</span>
</label>
</div>
<span id="answer_569b6a1f8bc84031a2e4faf7f65f822c_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_569b6a1f8bc84031a2e4faf7f65f822c_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_569b6a1f8bc84031a2e4faf7f65f822c_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 2" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_569b6a1f8bc84031a2e4faf7f65f822c" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_569b6a1f8bc84031a2e4faf7f65f822c">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="569b6a1f8bc84031a2e4faf7f65f822c-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="569b6a1f8bc84031a2e4faf7f65f822c-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="569b6a1f8bc84031a2e4faf7f65f822c-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@adb3d70e509a41b5949c84972a63abab">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@adb3d70e509a41b5949c84972a63abab" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_adb3d70e509a41b5949c84972a63abab" class="problems-wrapper" role="group"
aria-labelledby="adb3d70e509a41b5949c84972a63abab-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@adb3d70e509a41b5949c84972a63abab" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@adb3d70e509a41b5949c84972a63abab/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="adb3d70e509a41b5949c84972a63abab-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@adb3d70e509a41b5949c84972a63abab-problem-progress" tabindex="-1">
Problem 3
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@adb3d70e509a41b5949c84972a63abab-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;">How many cells are there?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_adb3d70e509a41b5949c84972a63abab_2_1">
<fieldset aria-describedby="status_adb3d70e509a41b5949c84972a63abab_2_1">
<div class="field">
<input type="radio" name="input_adb3d70e509a41b5949c84972a63abab_2_1" id="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="adb3d70e509a41b5949c84972a63abab_2_1-choice_0-label" for="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_adb3d70e509a41b5949c84972a63abab_2_1">
<span style="font-family: 'book antiqua', palatino;">\(|\mathbb{N}|\)</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_adb3d70e509a41b5949c84972a63abab_2_1" id="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="adb3d70e509a41b5949c84972a63abab_2_1-choice_1-label" for="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_adb3d70e509a41b5949c84972a63abab_2_1">
<span style="font-family: 'book antiqua', palatino;">\(|\mathbb{R}|\)</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_adb3d70e509a41b5949c84972a63abab_2_1" id="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="adb3d70e509a41b5949c84972a63abab_2_1-choice_2-label" for="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_adb3d70e509a41b5949c84972a63abab_2_1">
<span style="font-family: 'book antiqua', palatino;">\(2\)</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_adb3d70e509a41b5949c84972a63abab_2_1" id="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="adb3d70e509a41b5949c84972a63abab_2_1-choice_3-label" for="input_adb3d70e509a41b5949c84972a63abab_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_adb3d70e509a41b5949c84972a63abab_2_1">
<span style="font-family: 'book antiqua', palatino;">None of the above</span>
</label>
</div>
<span id="answer_adb3d70e509a41b5949c84972a63abab_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_adb3d70e509a41b5949c84972a63abab_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_adb3d70e509a41b5949c84972a63abab_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_adb3d70e509a41b5949c84972a63abab" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_adb3d70e509a41b5949c84972a63abab">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="adb3d70e509a41b5949c84972a63abab-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="adb3d70e509a41b5949c84972a63abab-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="adb3d70e509a41b5949c84972a63abab-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@d7c3ef2765ef4aeeac7106c741113ef8" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">The Strategy</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@8218452de2714fa4b4d684ee9538a22f">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@8218452de2714fa4b4d684ee9538a22f" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Our strategy relies on getting <span class="math inline">\(P_1,P_2,\ldots\)</span> to agree in advance on a "representative" from each cell. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">So, for instance, they might agree that <span class="math inline">\(\langle0,1,0,0\ldots\rangle\)</span> is to be the representative for the cell that contains <span class="math inline">\(\langle0,0,0,0\ldots\rangle\)</span>. (The ability to pick a representative from each cell presupposes the Axiom of Choice, which we’ll discuss further in Lectures 7 and 8.)</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Imagine that <span class="math inline">\(P_1,P_2,\ldots\)</span> are all lined up, and that they’ve agreed on a choice of representatives. Each of them knows her position in line and can see the hat colors of everyone ahead of her. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Now consider person <span class="math inline">\(P_{k}\)</span>. She can see the colors of the hats of <span class="math inline">\(P_{k+1},P_{k+2},P_{k+3},\ldots\)</span>, but not of <span class="math inline">\(P_1\ldots P_k\)</span>. So she doesn’t know exactly what the actual assignment of hats to persons is. But, crucially, she is in a position to determine which <em>cell</em> contains the sequence of zeroes and ones corresponding to that assignment. To see this, suppose that <span class="math inline">\(P_k\)</span> sees the following:</span></p>
<p><span style="font-family: 'book antiqua', palatino;"><span class="math display">\[\begin{array}{ccccccccc} P_1 &P_2 & \ldots &P_k &P_{k+1} &P_{k+2} &P_{k+3} &P_{k+4} &\ldots\\ \downarrow &\downarrow &\ldots &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\ldots \\ ? &? &\ldots &? &\text{red} &\text{blue} &\text{red} &\text{red} &\ldots \end{array}\]</span> Let her fill in the missing information arbitrarily—using "blue", for example: <span class="math display">\[\begin{array}{ccccccccc} P_1 &P_2 & \ldots &P_k &P_{k+1} &P_{k+2} &P_{k+3} &P_{k+4} &\ldots\\ \downarrow &\downarrow &\ldots &\downarrow &\downarrow &\downarrow &\downarrow &\downarrow &\ldots \\ blue & blue &\ldots & blue &\text{red} &\text{blue} &\text{red} &\text{red} &\ldots \end{array}\]</span> Since the resulting assignment of hat-colors differs from the actual assignment at most in the first <span class="math inline">\(k\)</span> positions, the corresponding sequences of zeroes and ones must belong to the same cell. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">So <span class="math inline">\(P_k\)</span> has all the information she needs to identify the relevant cell. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">And, of course, everyone else is in a position to use a similar technique. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">So even though each of <span class="math inline">\(P_1,P_2,\ldots\)</span> has incomplete information about the distribution of hat-colors, they are each in a position to know which cell contains the <span class="math inline">\(\omega\)</span>-sequence representing the actual hat distribution. Call this cell <span class="math inline">\(O\)</span>, and let <span class="math inline">\(r_O\)</span> be the representative that had been previously agreed upon for <span class="math inline">\(O\)</span>. Let the group agree on the following strategy:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">Everyone is to answer their question on the assumption that the actual sequence of hats is correctly described by <span class="math inline">\(r_O\)</span>.</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">In other words, <span class="math inline">\(P_k\)</span> will cry out "Red!" if <span class="math inline">\(r_O\)</span> contains a zero in its <span class="math inline">\(k\)</span>th position, and she will cry out "Blue!" if <span class="math inline">\(r_O\)</span> contains a one in its <span class="math inline">\(k\)</span>th position. Because <span class="math inline">\(r_O\)</span> and the sequence corresponding to the actual hat distribution are members of the same cell, we know they differ in at most finitely many positions. So, as long as everyone conforms to the agreed-upon strategy, at most finitely many people will guess incorrectly. QED.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">(It goes without saying that this strategy presupposes that every prisoner has super-human capabilities. For instance, they must be able to absorb information about infinitely many hat colors in a finite amount of time, and they must be able to pick representatives from sets with no natural ordering. This entails that no actual human could implement this strategy. But what that matters for present purposes is that the strategy exists. Recall that we are interested in logical possibility, not medical possibility.)</span></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: The Strategy</h3>
<div
id="video_df7a69a0842249efb3051f5787726346"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346/handler/publish_completion", "streams": "1.00:rn6ju1Rm_gk", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="df7a69a0842249efb3051f5787726346"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_df7a69a0842249efb3051f5787726346">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_df7a69a0842249efb3051f5787726346">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@df7a69a0842249efb3051f5787726346/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@6ae09e1d64ff4139a2c33654098835c1" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">Puzzle solved?</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@47aa5cfbadc74b36a589c97741c46089">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@47aa5cfbadc74b36a589c97741c46089" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">We have succeeded in identifying a strategy that guarantees that at most finitely many people will guess incorrectly. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Unfortunately, our success leads to paradox. For there is a seemingly compelling argument for the conclusion that it should be <em>impossible</em> for there to be such a strategy:</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;">We know that a random process will be used to decide what kind of hat to place on each person. Let us imagine that it works as follows. Each person has an "assistant". While the person closes his or her eyes, the assistant flips a coin. If the coin lands Heads, the assistant places a red hat on the person’s head. If the coin lands Tails, the assistant places a blue hat on the person’s head.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">We shall assume that assistants always use fair coins. Accordingly, the probability that a coin toss lands Heads is exactly 50%, independently of how other coin tosses might have landed. This means, in particular, that knowing the colors of the hats ahead of you gives you <em>no information whatsoever</em> about the color of your own hat. So even after you’ve seen the colors of the hats of everyone in front of you, you should assign a probability of 50% to the proposition that your own hat is red.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">This seems to entail that that none of the <span class="math inline">\(P_1, P_2, P_3, \ldots\)</span> could have a better than 50% chance of correctly guessing the color of their hat. </span><span style="font-family: 'book antiqua', palatino;">But if this is so, it should be impossible for there be a strategy that guarantees that the vast majority of \(P_1, P_2, P_3, \ldots\) answers correctly.</span></p>
</blockquote>
<p><span style="font-family: book antiqua,palatino;">Since we have found such a strategy, we know that this argument must go wrong somewhere. To solve the paradox, we must understand where the argument goes wrong.</span><span style="font-family: book antiqua,palatino;"></span></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="video" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Video Review: There is Still Something Puzzling</h3>
<div
id="video_3089957ee21f44ac8a86a421233569fe"
class="video closed"
data-metadata='{"speed": null, "publishCompletionUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe/handler/publish_completion", "streams": "1.00:TGqncsOmG9s", "prioritizeHls": false, "completionEnabled": false, "autoAdvance": false, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "recordedYoutubeIsAvailable": true, "showCaptions": "true", "completionPercentage": 0.95, "saveStateUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe/handler/xmodule_handler/save_user_state", "ytMetadataEndpoint": "", "duration": 0.0, "autohideHtml5": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": [], "transcriptAvailableTranslationsUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe/handler/transcript/available_translations", "savedVideoPosition": 0.0, "transcriptTranslationUrl": "/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe/handler/transcript/translation/__lang__", "saveStateEnabled": false, "ytTestTimeout": 1500, "poster": null, "autoplay": false, "generalSpeed": 1.0, "start": 0.0, "end": 0.0}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="3089957ee21f44ac8a86a421233569fe"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_3089957ee21f44ac8a86a421233569fe">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_3089957ee21f44ac8a86a421233569fe">
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@video+block@3089957ee21f44ac8a86a421233569fe/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@1c1bc34ed8c340c6b3e84e4d8137af18">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@1c1bc34ed8c340c6b3e84e4d8137af18" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: book antiqua,palatino;">Towards a Solution</span></h4>
<p><span style="font-family: book antiqua,palatino;">Let me begin with a preliminary observation. There is a difference between saying that the group increases its probability of <em>collective</em> success and saying that each member of the group increases her own probability of success. To see this, imagine that the group has two options: </span></p>
<p style="padding-left: 30px;"><span style="font-family: book antiqua,palatino;"><strong>Strategy</strong> each member of the group follows the strategy outlined above<br /></span><br /><span style="font-family: book antiqua,palatino;"><strong>Coin Toss</strong> each member of the group makes her decision by tossing a coin</span></p>
<p><span style="font-family: book antiqua,palatino;">Of the uncountably many outcomes that Coin Toss allows, only countably many are such that at most finitely many people answer incorrectly. So one should expect that following Strategy will lead to a better collective outcome than following Coin Toss.</span><br /><br /><span style="font-family: book antiqua,palatino;">On the other hand, it is not at all clear that choosing Strategy over Coin Toss would increase the probability that any individual member of the group will answer correctly. To see this, suppose that the group decides to follow Strategy, and imagine yourself in \(P_k\)'s position. Although you can be confident that the number of people who will die is finite, you have no idea how large that number will be. All you know is that there is some number \(n\) such that, for any \(m> n\), \(P_m\) will survive. Notice, moreover, that the vast majority of values that \(n\) could take---all except for the first \(k\)---are too large to offer you much comfort. So it's not clear that you should expect to be better off following Strategy than following Coin Toss.</span><br /><br /><span style="font-family: book antiqua,palatino;">The core of the paradox we are considering is that it seems hard to reconcile two facts. On the one hand, there are reasons for thinking that none of the \(P_1, P_2, P_3, \ldots\) could have a better than 50% chance of correctly guessing the color of their hat. On the other, we have found a strategy that guarantees that the vast majority of \(P_1, P_2, P_3, \ldots\) answers correctly. This would seem very puzzling indeed if the upshot of the strategy was that each individual member of the group was able to increase her probability of success 50%. But we have now seen that it is not clear that this is so. All we know is that the group increases its probability of <em>collective</em> success.</span><br /><br /><span style="font-family: book antiqua,palatino;">To fully answer the paradox, however, we need an understanding of how it is that the group is able to increase its probability of collective success. To this we now turn.</span></p>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+24.118x+2T2020+type@problem+block@1acf59c61940482691370a9156519a4e">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@problem+block@1acf59c61940482691370a9156519a4e" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="problem" data-has-score="True" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_1acf59c61940482691370a9156519a4e" class="problems-wrapper" role="group"
aria-labelledby="1acf59c61940482691370a9156519a4e-problem-title"
data-problem-id="block-v1:MITx+24.118x+2T2020+type@problem+block@1acf59c61940482691370a9156519a4e" data-url="/courses/course-v1:MITx+24.118x+2T2020/xblock/block-v1:MITx+24.118x+2T2020+type@problem+block@1acf59c61940482691370a9156519a4e/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="1acf59c61940482691370a9156519a4e-problem-title" aria-describedby="block-v1:MITx+24.118x+2T2020+type@problem+block@1acf59c61940482691370a9156519a4e-problem-progress" tabindex="-1">
Problem 1
</h3>
<div class="problem-progress" id="block-v1:MITx+24.118x+2T2020+type@problem+block@1acf59c61940482691370a9156519a4e-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>
<span style="font-family: 'book antiqua', palatino;"><span class="math inline">\(P_k\)</span> is feeling pretty good about her chances of surviving because of the following thought:</span>
</p>
<blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Of the infinitely many people in the group, there are only finitely many&#8212;an incredibly small minority&#8212;who will die.</span>
</p>
</blockquote>
<p>
<span style="font-family: 'book antiqua', palatino;">Is <span class="math inline">\(P_k\)</span> right to feel optimistic on the basis of this thought?</span>
</p>
<div class="choicegroup capa_inputtype" id="inputtype_1acf59c61940482691370a9156519a4e_2_1">
<fieldset aria-describedby="status_1acf59c61940482691370a9156519a4e_2_1">
<div class="field">
<input type="radio" name="input_1acf59c61940482691370a9156519a4e_2_1" id="input_1acf59c61940482691370a9156519a4e_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="1acf59c61940482691370a9156519a4e_2_1-choice_0-label" for="input_1acf59c61940482691370a9156519a4e_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_1acf59c61940482691370a9156519a4e_2_1">
<span style="font-family: 'book antiqua', palatino;">Absolutely!</span>
</label>
</div>
<div class="field">
<input type="radio" name="input_1acf59c61940482691370a9156519a4e_2_1" id="input_1acf59c61940482691370a9156519a4e_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="1acf59c61940482691370a9156519a4e_2_1-choice_1-label" for="input_1acf59c61940482691370a9156519a4e_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_1acf59c61940482691370a9156519a4e_2_1">
<span style="font-family: 'book antiqua', palatino;">It's more complicated than that...</span>
</label>
</div>
<span id="answer_1acf59c61940482691370a9156519a4e_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_1acf59c61940482691370a9156519a4e_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_1acf59c61940482691370a9156519a4e_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Problem 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_1acf59c61940482691370a9156519a4e" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_1acf59c61940482691370a9156519a4e">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1acf59c61940482691370a9156519a4e-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1acf59c61940482691370a9156519a4e-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="1acf59c61940482691370a9156519a4e-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@6809e885300b4908b95870d6c2f9e12e" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">The Three Prisoners</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@62a45143d59448459397ba4f1e10dfc0">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@62a45143d59448459397ba4f1e10dfc0" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">Let me start by telling you about a different puzzle: the <strong>Problem of the Three Prisoners</strong>. I don’t know who invented it, but I learned about it thanks to philosopher and computer scientist Rohit Parikh, from the City University of New York.</span></p>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;"><em>Setup:</em> Suppose there are three prisoners in a room. They all close their eyes, and each of them is approached by a guard. Each guard flips a fair coin. If the coin lands Heads, he gives his prisoner a red hat; if it lands tails, he gives his prisoner a blue hat.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Once all three prisoners have been assigned hats, they are all allowed to open their eyes. Each of them can see the colors of the others’ hats but has no idea about the color of his own hat.</span></p>
<p><span style="font-family: 'book antiqua', palatino;">As soon as everyone knows the color of everyone else’s hat, the prisoners are taken into separate cells, so that they are unable to communicate with each other. At that point, they are each to be asked about the color of their hat. They are free to offer an answer or remain silent. The guards will then proceed as follows:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">If all three prisoners remain silent, all three will be killed.</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">If one of them answers incorrectly, all three will be killed.</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">If at least one prisoner offers an answer, and everyone who offers an answer answers correctly, then all three prisoners will be set free.</span></p>
</li>
</ul>
</blockquote>
<blockquote>
<p><span style="font-family: 'book antiqua', palatino;"><em>Problem:</em> Find a strategy that the prisoners could agree upon ahead of time which would guarantee that their chance of survival is above 50%.</span></p>
</blockquote>
<p><span style="font-family: 'book antiqua', palatino;">Before attempting to solve the puzzle, notice that there certainly is a strategy that gives the prisoners a chance of survival of <em>exactly</em> 50%. The prisoners can select one amongst them to serve as their "captain", and agree that only the captain is to offer an answer. Since the captain has no idea of the color of his hat, he must answer at random. And because the color of his has was chosen by the toss of a fair coin, he has a 50% chance of answering correctly.</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@8474a08ca5bd4611b54ca2b4598a694d" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">A solution to the Three Prisoners Puzzle</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@1411f46177074ddd92259d7a3b3dd1cf">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@1411f46177074ddd92259d7a3b3dd1cf" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p><span style="font-family: 'book antiqua', palatino;">One strategy is for each prisoner is to follow these instructions:</span></p>
<ul>
<li>
<p><span style="font-family: 'book antiqua', palatino;">If you see that the other two prisoners have hats of the same color, answer the guard’s question on the assumption that your hat is of the opposite color.</span></p>
</li>
<li>
<p><span style="font-family: 'book antiqua', palatino;">If you see that the other two prisoners have hats of different colors, refrain from answering the guard’s question.</span></p>
</li>
</ul>
<p><span style="font-family: 'book antiqua', palatino;">If all three prisoners follow this procedure, their chance of survival will be 75%. For (as shown below) there are eight possible hat distributions, all equally likely, and as long as they follow the strategy the prisoners are set free in six of those eight possibilities (<span class="math inline">\(6/8 = 75\%\)</span>).</span></p>
<p><span class="math display" style="font-family: 'book antiqua', palatino;">\[\begin{array}{cccc} \text{ Prisoner $A$} & \text{ Prisoner $B$} & \text{ Prisoner $C$} &\text{ Result of following Strategy} \\ \text{ red} & \text{ red} & \text{ red} & \text{ Everyone answers incorrectly} \\ \text{ red} & \text{ red} & \text{ blue} & \text{ $C$ answers correctly} \\ \text{ red} & \text{ blue} & \text{ red} & \text{ $B$ answers correctly} \\ \text{ red} & \text{ blue} & \text{ blue} & \text{ $A$ answers correctly} \\ \text{ blue} & \text{ red} & \text{ red} & \text{ $A$ answers correctly} \\ \text{ blue} & \text{ red} & \text{ blue} & \text{ $B$ answers correctly} \\ \text{ blue} & \text{ blue} & \text{ red} & \text{ $C$ answers correctly} \\ \text{ blue} & \text{ blue} & \text{ blue} & \text{ Everyone answers incorrectly} \\ \end{array}\]</span></p>
<p><span style="font-family: 'book antiqua', palatino;">Note that although it is true that the prisoners increase their chance of collective of success to 75%, the chance that any given prisoner answers correctly, given that he offers an answer, remains fixed at 50%. </span></p>
<p><span style="font-family: 'book antiqua', palatino;">Suppose, for example, that you are prisoner <span class="math inline">\(A\)</span>, and that you see two red hats before you. The agreed-upon strategy asks you to answer "Blue!". But because the color of each hat was chosen on the basis of an independent coin toss, a <span class="math inline">\(\langle\text{Blue}, \text{Red}, \text{Red}\rangle\)</span> hat distribution is exactly is likely as a <span class="math inline">\(\langle \text{Red}, \text{Red}, \text{Red}\rangle\)</span> hat distribution. So the probability that you will answer correctly is precisely 50%.</span></p>
<p><span style="font-family: book antiqua, palatino;">The group improves its chances of collective success not because it increases the chance of success of individual answers, but because it manages to coordinate individual successes and failures in a certain kind of way. To see this, go back to the figure above, and consider the eight different hat distributions that are possible. Each prisoner answers correctly in two of these eight hat distributions, answers incorrectly in two, and remains silent in four. So each prisoner has as many successes as failures (which is why his chances of answering correctly, given that he answers, are 50%). But the prisoners’ individual successes and failures are distributed unevenly across the space of possible hat distributions. They are coordinated in such a way that only two of the eight possibilities involve failures (which is why the strategy gives the group a 75% chance of success).</span></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@vertical+block@c5b7890e301045f1b52f4816b3740d18" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="vertical" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<h2 class="hd hd-2 unit-title">Assessment of Bacon's Puzzle</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+24.118x+2T2020+type@html+block@243330c037f749ffaf0ca76f1523e401">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:MITx+24.118x+2T2020+type@html+block@243330c037f749ffaf0ca76f1523e401" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:MITx+24.118x+2T2020" data-block-type="html" data-has-score="False" data-graded="False" data-request-token="cb108b80fe5611ee9b8b16fff75c5923">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<h4><span style="font-family: 'book antiqua', palatino;">Back to Bacon's Puzzle</span></h4>
<p><span style="font-family: book antiqua, palatino;">Now that we have discussed the Three Prisoners Puzzle I would like to return to the problem of understanding how it is that the \(P_1, P_2, P_3, \ldots\) is able to increase its probability of collective success in Bacon's Puzzle, even though it is not clear that any individual member of the group is able bring her probability of success over 50%.</span><br /><br /><span style="font-family: book antiqua, palatino;">A useful way of addressing this point is to draw on an analogy between the Three Prisoners Puzzle and Bacon's Puzzle. In each case, the group improves its chances of collective success not by increasing the chance of success of individual answers, but by coordinating successes and failures in a certain kind of way. </span><br /><br /><span style="font-family: book antiqua, palatino;">Recall that in Bacon's Puzzle \(P_1, P_2, P_3, \ldots\) are able to identify the cell containing the actual hat distribution, and that everyone agrees to answer on the assumption that their actual hat color is as described by the representative of that cell. Because everyone knows which cell contains the actual hat distribution, and because they're all agreed on a representative for that cell, they are able to <em>coordinate</em> their individual successes and failures so as to make sure that their answers form a sequence which is included in the same cell as the actual distribution of hat colors. And since members of the same cell differ at most finitely, this guarantees that at most finitely many people answer incorrectly, even if none of the \(P_1, P_2, P_3, \ldots\) increases her chances of guessing correctly beyond 50%. </span><br /><br /><span style="font-family: book antiqua, palatino;">This concludes my response to Bacon's Puzzle. I have proceeded in two steps. The first step is to note that although it would be very surprising if someone could increase her probability of individual success by following the proposed strategy, the proposed strategy does not presuppose such increase. All it requires is that the group increase its probability of <em>collective</em> success by following the strategy. The second step is to explain how the group is able to increase its probability of collective success even if no member of the group increases her probability of individual success. I have suggested that this is possible because, as in the case of the Three Prisoners Puzzle, individual members of the group to <em>coordinate</em> their successes and failures in the right sort of way.</span><br /><br /><span style="font-family: book antiqua, palatino;">One final question: what is the probability that an individual who follows the strategy will answer correctly? I don't know the answer to this question, but I suspect that when one follows the strategy one's probability of success is best thought of ill-defined. A little more specifically: I doubt there is a reasonable way of assigning a probability to the proposition that the representative of a given cell has a 1 in its \(k\)th position, and therefore to the proposition that \(P_k\) guesses correctly, given that she guesses in accordance with the strategy. </span><br /><br /><span style="font-family: book antiqua, palatino;">If it is true that there is no reasonable way of assigning a probability to the proposition that someone acting accordance with the hat strategy will answer correctly, then Bacon's Puzzle brings out an important limitation of standard ways of thinking about probability theory. That is why I think Bacon's Puzzle deserves a paradoxicality grade of 7. (I'll return to the problem of ill-defined probabilities when we talk about non-measurable sets, in Lecture 6.)</span><br /><br /><br /></p>
</div>
</div>
</div>
</div>
© All Rights Reserved