Group Projects

Project 1: Cutting pancakes and ham sandwiches

Suppose you are given a plate of two perfectly cooked pancakes, which have even thickness but may not be perfectly stacked. How to cut both pancakes into even halves with a single cut? If the pancakes are not cooked evenly, can you still cut them into even halves by a single cut? If you are given more than two pancakes, how to cut them? Can you extend your cutting strategies for sharing a ham sandwich? A ham sandwich can be thought as a stack of bread, ham, bread. You want to make a single cut, such that the two pieces of bread and the ham are divided into equal halves.

Project 2: Amicable pairs

Two integers n and m are called an amicable pair if the sum of the proper divisors of n equals m and vice versa. For example, 220 and 284 form an amicable pair. The proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, and 110 and  284 = 1+ 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 Also, the proper divisors of 284 are 1, 2, 4, 71, and 142 and 220 = 1 + 2+ 4 + 71 + 142. What sorts of properties are known about amicable pairs? How many amicable pairs are there? Are there existing connections to cryptography? Your project should culminate in the creation or explanation of a cipher incorporating amicable numbers. 

Project 3: Pareto-Optimal division

We say a fair-division is Pareto-Optimal if and only if there are no possible exchanges or different allocations that will benefit at least one agent without degrading any other agent. Show that the cut and divide strategy for 2 agents in cake cutting is not Pareto-Optimal. Is the adjusted winner algorithm for envy-free division Pareto- optimal?
(There's a notion of Pareto-dominance in comparing two different divisions. Division A is Pareto dominated by division A', if every agent feels receiving no less portion of goods in division A' than in division A. Can you translate this notion into mathematics and use your translation to define Pareto - Optimality ?)

Project 4: Creating a cipher

Suppose you and your best friend have your own alphabet that you use to exchange messages securely. Furthermore, suppose you have a long message to send to your friend that is time sensitive! In this project, you will design your own alphabet and cipher, and determine how to use a computer program to help you translate between your original message and the encrypted message written in your alphabet. Note that this is not only an artistic and computational task: you must design your cipher so that it is difficult for unintended recipients to crack. How many layers of encryption can you incorporate? How strong is your cipher? In what ways is it vulnerable to attack? 

Project 5: Minimal number of cuts

A good cake sharing strategy in theory results in fair sharing among agents. However, in real life, these theoretically good strategies may not work out very well, because a cake may be cut into many heterogeneous portions and an agent may receive a plate of cake crumbles instead of a whole piece of cake. Therefore, we care about the number of cuts a cake cutting protocol requires for sharing a cake among n agents in the worst case scenario. In particular, what's the minimal number of cuts required by the last diminisher protocol and the divide and conquer protocol? Which one would you prefer to use in practice?

Project 6: Mersenne numbers

A Mersenne number is a positive integer of the form Mn=2n-1. When Mn is prime, we call Mn a Mersenne Prime. While we can certainly construct infinitely many Mersenne numbers (how?), does this mean there are infinitely Mersenne primes? How might one go about finding Mersenne primes? What is GIMPS? Are there existing connections to cryptography? Your project should culminate in the creation or explanation of a cipher which incorporates Mersenne primes.

Project 7: Rent division

Like cake division, splitting rent among roommates such that everyone is happy can be tricky. Unlike cake division, where everyone wants to get more value of the cake, nobody wants to pay more than her expectation of her room. To put it another way, if the total rent is split into three for a three bedroom apartment, and let each resident pick one room according to the rent split and her preference of the rooms, then a "fair" split shall end up with all rooms are being picked by exactly one resident. Therefore, everyone is happy because she is paying the best price according to her evaluation. It is known that such a split is possible and can be computed under some mild assumptions of the assessment room-rent splitting, based on Sperner's Lemma. There is a very interesting New York Times online article of this, where you can find interactive visualization and references to help you understand how this works. Can you simulate a rent division scenario with your teammate and apply Sperner's Lemma to solve the problem. Are you happy with the process and the result? What other division problem might be solved using the same procedure? Are there tricks or concerns ?

Project 8: RSA Cryptosystem

Many ciphers, including the Caesar cipher, affine cipher, and block ciphers make use of modular arithmetic. In 1977, R. Rivest, A. Shamir, and L. Adleman proposed a public key cryptosystem (RSA) which uses elementary ideas from number theory. Its security depends on the assumption that the factorization of composite numbers with large prime factors is time-consuming. How does RSA work? Exactly why is it so secure? To answer these questions, you will get to dive deeper into such topics as Fermat's Little Theorem and the Chinese Remainder Theorem. Supplemental reading and examples will be provided to help guide you in your understanding.