CSC 341: Homework discussion
From CSWiki
This page is for the discussion of homework problems. According to the class rules, homework problem solutions may only be discussed after everyone has submitted the homework set. However, we can use the Wiki to ask for clarifications on the problems not yet submitted. If you're not sure whether everyone has submitted the set, wait until after it has been returned.
Contents |
Set 1
This set may be freely discussed
Problem 1
Problem 2
Problem 3
Problem 4
The solution guide to this problem distributed in class states that Ormuzd will win no matter what strategy he follows, though the proof is fairly complicated if he doesn't always choose the highest number. Here is a sketch of that proof. Actually, I don't think it's much more complicated than the case where Ormuzd always chooses the maximum number.
Let n be the highest number inscribed by Ahriman on his first turn. Note that Ahriman can never in the game inscribe a number higher than n. The proof will be by induction on n.
In the base case, n=0, Ahriman never gets another turn, as Ormuzd must always choose a 0, so Ormuzd will win after a finite number of turns.
Now suppose inductively that Ormuzd wins with any strategy when n<=k, and let n=k+1. The inductive hypothesis tells us indirectly that if Ormuzd always chooses numbers less than or equal to k, Ormuzd will win the subgame involving only numbers less than or equal to k, that is, eventually all the numbers less than or equal to k will be depleted. At that point, Ormuzd will be forced to pick the number k+1, decreasing the number of k+1 spheres. On his next turn, Ahriman can produce an arbitrary number of spheres numbered k and lower, but the process will repeat itself. If Ormuzd insists on only choosing spheres numbered k and lower, he will eventually be get rid of all the spheres numbered k and lower, and be forced again to pick a sphere numbered k+1. Since Ahriman can never make new spheres numbered k+1, Ormuzd will eventually get rid of all the spheres numbered k+1, no matter what strategy he follows. Then we are only left with spheres numbered k and below, and Ormuzd wins by the inductive hypothesis.
Set 2
This set is eligible for discussion.
Problem 5
Problem 6
Problem 7
Set 3
This set is eligible for discussion
Problem 8
Problem 9
Problem 10
Problem 11
Problem 12
Set 4
This set is eligible for discussion.
Problem 13
Problem 14
This problem has been canceled, as it is more difficult than intended. However, the extra credit part is still open for extra credit.
Problem 15
Problem 16
Set 5
This set is eligible for discussion.
Problem 17
Problem 18
Problem 19
Problem 20
Problem 21
Problem 22
Set 6
This set is not yet eligible for discussion.
Problem 23
Problem 24
Problem 25
Problem 26
Problem 27
Set 7
This set is not yet eligible for discussion.
