This page collects challenge problems that have been posed in cs2102.
By solving a challenge problem, you earn the glory and admiration of your classmates and the course staff (and maybe even the whole Internet if your solution is clever enough!). If that’s not enough, you also are rewarded “bonus points” (the number varies at the discretion of the teacher, but typically a value from about ½ to a full problem set (or even more).
You can submit a candidate answer for a challenge problem by sending me a Direct Message in Slack, or sending an email with subject line “Challenge Solution”.
Challenge 8. From Class 20: Prove that the Huntington-Hill Method used to apportional seats in the US Congress satisfies the quota property when used for a sets of states where each state has population at least D (where D is defined as the total country population divided by the number of representatives). The quota property states that each state receives either the floor of its population / D or one more than that delegates.
Challenge 2. From Class 3: It is trivial to show that
numbers in Java or C are not we-ordered, but quite challenging to show
this for Python. Write a Python program that demonstrates the fact
that integers in Python are not well-ordered. (Note: although I’m
continuing to list this as a “open challenge”, I don’t think there
will be a satisfactory solution. It is not enough to show a Python
program running out of memory trying to represent a large number, or
to show that
math.inf is not really infinity (obviously), but a
satisfactory solution would need to show some well accepted arithmetic
property being violated by the way arithmetic works on integers in
import sys a = sys.float_info.max assert (a + 1 == a)
(Challenges are not ever really “closed”, in the sense that if you can come up with a substantially better solution than the one posted, it is possible to win a closed challenge. The meaning of a “closed” challenge is that I believe there has been a winning solution, and that it is unlikely for someone to find a substantially better one.)
Challenge 1. From Class 2: I wasn’t very satisfied with my proof of the “Odd-Even Lemma” in class. I hope a student will come up with a better proof. Come up with a proof that passes the “skeptical reader” test and would convince someone with no prior knowledge of odd and even numbers.
- John Fry’s solution using the well-ordering principle
- Paul Sander’s solution using a game proof (although most game-style proofs are not so entertaingly written as Pauls, using a game to prove something is a very common strategy, especially in security and cryptography proofs.)
- Avi Parikh’s solution using proof by contradiction
Challenge 3. (From Class 8) Apparently, people were not entirely convinced by my proof sketch in class that the egg came before the chicken. So, we’ll make it a challenge problem to write the best proof that answers the question of “which came first, the chicken or the egg?” (That is, you can either prove the egg came first, or prove the chicken came first). A convincing proof would need to include clear definitions of “chicken” and “egg”, and use inference rules, as well as axioms based on biological assumptions (clearly stated), to make an irrefutable argument supporting your position.
Challenge 4. (From Class 9) How many self-inverting relations, R: Nk → Nk, are there? (Where Nk is the set of all non-negative integers less than k, and a relation is self-inverting if R = R-1.)
Challenge 5. (From PS3 Solutions) Prove that the four-clause solution given for question 6 is the shortest possible equivalent 3CNF formula.
Challenge 6. (From PS3 Solutions) Provide a full and convincing proof for Problem 11.
Challenge 7. From Class19: Determine the carinality of the set of all Tree objects (as defined on PS8), and provide a convincing proof supporting your answer.