Dunkin' Donuts Math Problem: Subset Sum Divisible by N

Dunkin' Donuts Super Bowl Commercial

• 🍩 The Dunkin' Donuts Super Bowl commercial featured a "Good Will Dunkin'" theme, referencing the movie "Good Will Hunting" and mathematical concepts.
• 💡 The commercial included a visual of Munchkins arranged in a Fibonacci spiral and Ben Affleck's character scribbling equations, specifically mentioning Binet's formula.

The Dunkin' Donuts Math Challenge

• 🏆 Dunkin' Donuts partnered with John Urschel, an MIT professor and former NFL player, to create a math challenge.
• ☕ The winner of the contest receives free Dunkin' coffee for a year and signed merchandise.
• 📝 The challenge involves finding a non-empty subset of natural numbers whose sum is divisible by n.

Proof of the Subset Sum Problem

• 🧠 The problem states: Given n natural numbers (a1, a2, ..., an), can you always find a non-empty subset whose sum is divisible by n?
• 💡 A proof uses the concept of prefix sums (S1=a1, S2=a1+a2, ..., Sn=a1+...+an).
• ⚠️ If any prefix sum is divisible by n, we have found our subset. If not, consider the remainders of these sums when divided by n.
• 📊 By the pigeonhole principle, with n sums and n-1 possible non-zero remainders (1 to n-1), at least two sums (Sj and Sk, with j < k) must have the same remainder.
• ✅ The difference between these two sums, Sk - Sj, which equals a(j+1) + ... + a(k), will be divisible by n, thus providing the required subset.

Example Application of the Proof

• 🔢 For n=6 and numbers {11, 32, 19, 21, 3, 50}, we calculate prefix sums and their remainders modulo 6.
• 🔍 The sums are S1=11, S2=43, S3=62, S4=83, S5=86, S6=136.
• 🎯 Remainders modulo 6 are: S1≡5, S2≡1, S3≡2, S4≡5, S5≡2, S6≡4.
• 🧩 Since S1 and S4 have the same remainder (5), the subset {a2, a3, a4} = {32, 19, 21} sums to 72, which is divisible by 6.