Submitted by Add Sugar on Mon, 04/29/2019 - 02:11
Thank you to everyone involved for their time and effort in making this resource.
I am asking for further help with 4.(v) of assignment 23 - the one about the blue eyed islanders. I don't fully understand the inductive step used in the solution sheet, but I'm not fully convinced by the argument in my own solution either.
There are two issues I'm not clear about in the given solution. The first is the line "No-one will have left on days 1,2,3,...,k". We require this to be true for the argument to work, but this doesn't seem to obviously follow from the inductive assumption made. The second is that although the argument makes a strong inductive assumption, it only appears to use a weak one (that the proposition is true for n=k).
It's likely the fact that I'm unable to see the strong assumption being used is also the reason I'm unconvinced of the first point.
My solution follows the same inductive argument but just uses the weak inductive assumption that the proposition holds for n=k. It also attempts to make the argument more solid that "No-one will have left on days 1,2,3,...,k".
I write out the parts where my solution differs below. If anyone could help me to flesh out the above two issues in the given solution or help me tighten my own very similar argument (I think strong induction is perhaps just what it could do with), I would really appreciate it.
So, after making the assumption that the proposition, "If there are n blue-eyed islanders then they will all leave on the nth day" holds for n=k, my argument continues:
(I use blue as an adjective and a noun to indicate 'islanders with blue eyes')
"Suppose n=k+1, then each blue knows n=k or k+1.
By the assumption, if n=k then all blues will leave on the kth day. Therefore, if on the k+1th day there are still blues on the island, then these blues can conclude that n≠k and so n=k+1 (and they will then leave that same day). That is to say, all k+1 blues will leave by the k+1th day. It still remains to be proven though that these k+1 blues will all leave on that final k+1th day i.e that all or some of them will not leave earlier.
We know it's true for n=2 (two blues cannot conclude on day 1 they are blue). And by the assumption, it is true for n=k. That is to say, each of the k blues only on reaching the kth day can conclude they are blue, and each of the 100-k browns only on day k+1 (after the blues have left) that they are brown.
Now consider the n=k+1 case. These k+1 blues each see k blues and 100-k-1 browns. These are exactly the same numbers of blues and browns as the 100-k browns see above. Therefore, these blues like the browns above cannot conclude they are blue or brown until the k+1th day, and will not leave before the k+1th day. So all k+1 blues leave on the k+1th day."
The remaining part is the same as the given solution.
Strong induction
The solution to the assignment is perhaps not set out quite as formally as one would expect a strong induction argument at university level to be set out. The "strong" part of the induction bit holds here: "Assume that the proposition is true for $n= 1,2,3,4,...,k$, so if there are $k$ islanders with blue eyes then they will all leave on the $k^{\text{th}}$ day (and if there are less than $k$ they will have left before the $k^{\text{th}}$ day)"
The bite where "If there are less that $k$ they will have left before the $k^{\text{th}}$ day" is the strong bit .
Perhaps a better way?
Proposition: If $n$ are blues, then they will all leave on the $n^{\text{th}}$ day, i.e. all of the $n$ blues will work out that they have blue eyes on the $n^{\text{th}}$ day.
We know the proposition is true when $n=1$.
Assume that the proposition is true for $n=1, 2, ..., k$.
Consider the case that no-one has left on the $k^{\text{th}}$ day. Then we know that there are more than $k$ blues (as we know that there is at least 1 blue, and if there were $1, 2, ..., k$ blues then they would have left on day $1, 2, ..., k$). If there are $k+1$ blues then they would each see $k$ other blues and know that there are $k+1$ blues in total and they would hence all leave. If there are more than $k+1$ blues then they would not know if they were a blue or not (as each would see at least $k+1$ blues) and so wouldn't leave.
Hence if the proposition is true for $n=1, 2, ..., k$ then it is true for $n=k+1$ and the result follows by (strong) induction.
Hi Hypatia, thank you for
Hi Hypatia, thank you for your prompt and helpful reply.
I mistakenly thought I had read somewhere when signing up that post updates would be notified by email. I didn't receive any so I had presumed there wasn't any activity yet. I only checked the forum and saw your response just now. Apologies for my tardiness.
Your rephrasing of the argument has helped to see more clearly where I was having a problem.
The rather perverse possibility that the blue eyed islanders could in some unidentifiable way deduce at a very early date they were blue eyed, is actually, I see now, very simple to prove impossible.
However, concerning my question about the strong inductive argument, I still think although the assumption is stated in the solution and in your reformulation, it isn't actually used or necessary to those arguments. They certainly seem to me to work equally well with just the weak inductive assumption.
Am I still missing something?
Updates
We don't have any email notifications for updates on this website, sorry!
I think you might be right, and that weak induction is all that is needed. From your first post:
"Suppose n=k+1, then each blue knows n=k or k+1.
By the assumption, if n=k then all blues will leave on the kth day. Therefore, if on the k+1th day there are still blues on the island, then these blues can conclude that n≠k and so n=k+1 (and they will then leave that same day). That is to say, all k+1 blues will leave by the k+1th day. It still remains to be proven though that these k+1 blues will all leave on that final k+1th day i.e that all or some of them will not leave earlier."
The only thing I might tighten up is the first line, and perhaps explain why each blue knows that $n=k$ or $n=k+1$ (which is fairly simple to do, but perhaps is necessary for complete clarity?).
Updates
We don't have an email update facility, sorry!
Reading back your first post, I think that your weak induction argument might be sufficient. I think the only thing I would tighten up is "Suppose n=k+1, then each blue knows n=k or k+1." - I would explain why you know this. It's fairly easy to do but would just make sure everything has been fully reasoned.