Challenge Problems

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”.

Open Challenges

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 Python.)

There has been a partial solution to this submitted that shows how floating point numbers in Python are not well-ordered, but, although I didn’t specify it in the question, I really want a program that demonstrates that integers in Python3 are not well-ordered (and won’t close the challenge until getting one). For floating point numbers, the solution Karan Dhillon came up with is essentially:

   import sys
   a = sys.float_info.max
   assert (a + 1 == a)

Closed Challenges

(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.

There are 3 winning solutions:

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.

There’s no real closure on this one, but some interesting submissions.

Challenge 4. (From Class 9) How many self-inverting relations, R: N_k → N_k, are there? (Where N_k is the set of all non-negative integers less than k, and a relation is self-inverting if R = R^-1.)

Winning solution by Henry Spece!

Challenge 5. (From PS3 Solutions) Prove that the four-clause solution given for question 6 is the shortest possible equivalent 3CNF formula.

Winning response by Henry Spece! (Turns out that it wasn’t the actual shortest equivalent 3CNF formula!)

Challenge 6. (From PS3 Solutions) Provide a full and convincing proof for Problem 11.

Winning proof by Henry Spece! (PDF)

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.

Winning proof by Henry Spece!