A small charity runs the "Lucky Fives" lottery every week. The rules are simple: pick 5 distinct numbers from 1 to 30 (order does not matter). A ticket costs $2. The guaranteed jackpot is $500,000 — the charity always pays it out if someone wins, no splitting. You and your friends realize that if you could buy every possible ticket, you would be guaranteed to win. The question is whether the math works out in your favor.
How many unique lottery tickets exist? Identify whether this is a permutation or combination problem, state the formula you are using, and compute the answer.
At $2 per ticket, what is the total cost to buy every possible ticket? Is it profitable to buy them all? Show the comparison between total cost and the $500,000 jackpot.
The charity catches on and adds a "Mega Number" — an additional number picked independently from 1 to 10 — to each ticket. How many unique tickets exist now? Identify the counting rule you are using to combine the original picks with the Mega Number.
With the Mega Number in play, is buying every ticket still profitable? If not, what is the minimum jackpot (in whole dollars) the charity would need to offer to make buying every ticket profitable again?
Worried about syndicates, the charity changes the rules: now the 5 main numbers are ordered (like a PIN — picking 1-2-3-4-5 is different from 5-4-3-2-1). The Mega Number stays. How many unique tickets exist under this new system?
Comparing your answer from Q1a (unordered, no Mega Number) to Q1e (ordered, with Mega Number), by what factor did the total number of tickets increase? Express this factor using factorial notation and explain, in one sentence, why switching from unordered to ordered selections creates so many more possibilities.
A class of 120 computer science students is surveyed about their club memberships. The results are as follows:
How many students are in at least one of the three clubs? Write out the full Inclusion-Exclusion formula for three sets, substitute the values, and compute the answer.
How many students are in none of the three clubs?
The department wants to send a special survey to students who are in exactly one club (not two, not three — just one). How many surveys need to be sent? Show your reasoning for how you remove the students who are in multiple clubs from each club's total.
You are working as an apprentice at a lock repair shop. Your boss sells refurbished locks with a guarantee: every repaired lock retains at least 50% of its original valid sequences, or the customer gets a full refund.
Your boss keeps calling them "combination locks," but you know from LN17 that the standard padlock with rotating cylinders is technically a permutation lock. Explain why the typical lock is a permutation lock and not a combination lock. Then, describe what a mathematically accurate "combination" lock would look like — what would be different about how it opens?
A customer brings in a defective lock. It has 4 cylinders, each with digits 0 through 7 (octagonal design). The defect: cylinder 2 is loose and cannot be set to the digit 3. All other cylinders and digits work fine.
Your boss storms in asking: "What kind of defect would cause us to lose exactly half the sequences?" Investigate: would you need to lose half the cylinders? Half the choices on one cylinder? Something else entirely? Show the math for at least two scenarios on the same 4-cylinder, 0-7 lock, and identify which scenario results in exactly 50% of the original sequences remaining.
Construct Pascal's Triangle out to row 7 (where row 0 is just the single entry 1). Using your triangle, verify the symmetry identity by circling the entries for
Using Pascal's Rule, show that
Double counting: Show that the sum of all entries in row 5 of Pascal's Triangle equals
Vandermonde's Identity states that for non-negative integers
Here is an intuitive way to read it: a pet shelter has
Using
Compute the right-hand side by expanding the sum term by term for
Draw Pascal's Triangle out to row 7. Circle the entry for
In your own words, explain why the right-hand side of Vandermonde's Identity counts the same thing as the left-hand side. Use the dog/cat framing: why does summing "choose
In LN19, we learned that constructing a bijection between two sets proves they have the same cardinality — the function IS the proof. Georg Cantor used this technique to make revolutionary claims about infinite sets. The following questions investigate this.
Prove that the set of all integers
Q6a1: Give a function
Q6a2: Prove your function is injective by showing that
Q6a3: Prove your function is surjective by showing that for every even integer
Explain why having constructed this bijection proves that
Now consider the integers
Q6c1: Give an injective function from
Q6c2: Give a surjective function from
A computer science department has 53 students. Using the pigeonhole principle, explain why at least two students must have been born in the same week of the year. Clearly state what the "items" and "slots" are.
A server receives 500 user registrations. Each username is hashed into one of 128 buckets. Using the generalized pigeonhole principle, what is the minimum number of usernames that must end up in the same bucket? Show your work using
The birthday paradox tells us that collisions arrive much sooner than our intuition expects. If a system uses hash values with 365 possible outputs, approximately how many items must be inserted before a collision is more likely than not? The answer is roughly
In LN19, we studied the 2011 Python hash-flooding attack. In 2-3 sentences, explain: (1) how the pigeonhole principle guaranteed that hash collisions existed in Python's dict, and (2) why the birthday paradox made the attack even more devastating than pigeonhole alone would suggest.
Your repository will contain the following files:
CMSI-2820-HW5/
├── .gitignore
├── README.md
├── court.py
├── test_court.py
└── proceedings.py
As a refresher, here is the helper video that goes from complete start to finish for the process of receiving, setting up, and turning in your programming portion of the HW:
Functions are a bit too general as it stands right now to make a small creative project out of. Since they can be used to understand/define/simulate anything there is a distinct issue with applying them, in that they apply themselves everywhere. So instead of trying to "decode" something you enjoy into a bunch of tiny interactions, I'd rather use this optional assignment for reflection and sharing.
Functions can be understood as a map from inputs to outputs. When you put something in, you get something out. So I would like you to do the same but for your hobby. Why do you enjoy your hobbies? When you put your effort into your personal projects, what do you get out of them? It is just the satisfaction of getting better? Do you like to make works an sell them for extra spending cash? I would like you to take this optional to give a brief reflection on why you keeping "using the same function" over an over again (That function being your hobby!).
Once you've reflected on your hobby, then we will represent the other crucial part of a function, their "bodies". To reflect functions as ordered instructions, I would like you to put together a small guide/introduction of how to get into, and what someone might get out of, your hobby! After all, its hard to know whether you should be running a function or not unless you have some documentation!
For instance, if I were to complete this optional, I would choose to reflect on my hobby of rock climbing. I would begin by reflecting on what I personally get out of it. This includes a number of things, but in short it keeps me active, its difficulty means I am always faced with a challenge to improve, and the focus required to follow a difficult beta (a set of move by move instructions for how you climb from the start to finish of a climb, usually used for difficult climbs where certain techniques may be required to reach the top) is a good way to clear my mind of distractions that are bothering me (like a meditation of sorts). Once I finished reflecting on what I get out of rock climbing, I would then make a guide to help introduce people to climbing. This could take the form of a cool flyer, a blog, a fake advertisement for a company, or a video. This is where you can get creative as for many hobbies there might be preferred or cool introductions to them that are personalized. Since rock climbing is so specific, I might create a montage of really mind bending moves you wouldn't expect to get people drawn in!
Due to the open ended, and mostly personal, nature of this optional, I will be grading it purely on participation with the two major components:
Once you have completed your reflection and guide/intro, you can turn it in via brightspace! If you have any questions about this optional feel free to ask me!
This optional project can be submitted until one week after the homework due date.
| Component | Points | Description |
|---|---|---|
| Q1 | 15 | Breaking the Lottery (enumeration) |
| Q2 | 10 | Inclusion-Exclusion (3-set scenario) |
| Q3 | 7 | The Locksmith's Apprentice |
| Q4 | 10 | Pascal's Triangle and Double Counting |
| Q5 | 15 | Vandermonde's Identity |
| Q6 | 15 | Bijective Proofs and the Sizes of Infinity |
| Q7 | 8 | Pigeonhole Principle and Collisions |
| Programming | 20 | Court proceedings implementation in Python |
| Optional Section | 20 | Hobby reflection and guide (Points For S4 Only) |
| Total | 100 |