When one thinks of institutions and places that house some of the brightest mathematical minds on the planet, one tends to think of companies like Google and academic institutions like MIT and Cal Tech. But flying somewhat underneath the radar is the National Security Agency (NSA), the famed intelligence agency that was unwittingly thrust into the spotlight following Edward Snowden’s massive leak of classified NSA material.
The NSA likely houses the largest group of world-class cryptographers and mathematicians than any other place in the world. Suffice it to say, if you’re mathematically inclined and want to make it at the NSA, you don’t just need to be good at math, you need to uniquely excel at it.
While not exactly entrance exam caliber questions, Business Insider recently pointed out that the NSA every month posts a brand new employee-written brain teaser under a series called the Puzzle Periodicals.
To help give you an idea as to the skill level often housed in these brain teasers, BI compiled a list of the six most interesting problems that have appeared on the NSA’s website over the last few months.
To help kick things off and get those synapses in your head firing on all cylindars, here are two particularly challenging examples.
The first one from July 2015 was concocted by NSA Applied Research Mathematician Andy F
Mel has four weights. He weighs them two at a time in all possible pairs and finds that his pairs of weights total 6, 8, 10, 12, 14, and 16 pounds. How much do they each weigh individually?.
Note: There is not one unique answer to this problem, but there is a finite number of solutions.
The NSA’s solution to the problem reads as follows:
There are exactly two possible answers: Mel’s weights can be 1, 5, 7, and 9 pounds, or they can be 2, 4, 6, and 10 pounds. No other combinations are possible.
Let the weights be a, b, c, and d, sorted such that a < b < c < d. We can chain inequalities to get a + b < a + c < a + d, b + c < b + d < c + d. Thus, a + b = 6, a + c = 8, b + d = 14, and c + d = 16. But we don’t know if a + d = 10 and b + c = 12 or the other way around. This is how we get two solutions. If a + d = 10, we get 1, 5, 7, and 9; if b + c = 10, we get 2, 4, 6, and 10.
More on the Problem
Where this problem really gets weird is that the number of solutions depends on the number of weights. For example, if Mel has three weights and knows the weight of all possible pairs, then there is only one possible solution for the individual weights. The same is true if he has five weights.
But now suppose that Mel has eight weights, and the sums of pairs are 8, 10, 12, 14, 16, 16, 18, 18, 20, 20, 22, 22, 24, 24, 24, 24, 26, 26, 28, 28, 30, 30, 32, 32, 34, 36, 38, and 40. Now what are the individual weights?
This time, there are three solutions:
1, 7, 9, 11, 13, 15, 17, 23
2, 6, 8, 10, 14, 16, 18, 22
3, 5, 7, 11, 13, 17, 19, 21
Thirsty for more? Here’s another one, this time from NSA Applied Mathematician Robert B.
Following their latest trip, the 13 pirates of the ship, SIGINTIA, gather at their favorite tavern to discuss how to divvy up their plunder of gold coins. After much debate, Captain Code Breaker says, “Argggg, it must be evenly distributed amongst all of us. Argggg.” Hence, the captain begins to pass out the coins one by one as each pirate anxiously awaits her reward. However, when the captain gets close to the end of the pile, she realizes there are three extra coins.
After a brief silence, one of the pirates says, “I deserve an extra coin because I loaded the ship while the rest of you slept.” Another pirate states, “Well, I should have an extra coin because I did all the cooking.” Eventually, a brawl ensues over who should get the remaining three coins. The tavern keeper, annoyed by the chaos, kicks out a pirate who has broken a table and who is forced to return her coins. Then the tavern owner yells, “Keep the peace or all of you must go!”
The pirates return to their seats and the captain, left with only 12 total pirates, continues to distribute the coins – “one for you,” “one for you.” Now, as the pile is almost depleted, she realizes that there are five extra coins. Immediately, the pirates again argue over the five extra coins. The captain, fearing that they will be kicked out, grabs the angriest pirate and ushers her out of the tavern with no compensation. With only 11 pirates left, she resumes distribution. As the pile nears depletion, she sees that there won’t be any extra coins. The captain breathes a sigh of relief. No arguments occur and everyone goes to bed in peace.
If there were less than 1,000 coins, how many did the pirates have to divvy up?
The NSA’s solution reads:
There are actually infinite answers to the problem, but only one number if the answer is under 1,000. This puzzle is an example of modular arithmetic and the Chinese Remainder Theorem.
The smallest solution under 1,000 for this problem is 341 coins, and the answer is found by working backwards. To find it, we first note that with 11 pirates the coins divided evenly; hence, the number of coins is in the list:
11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143…
What happens if we take these numbers and divide them among 12 pirates? How many coins would be left over? Well, we want 5 coins to be left over after dividing by 12. Hence, we reduce the list above to:
77, 209, 341, 473…
These numbers divide by 11 evenly and have 5 left over when divided by 12. Now we take these remaining numbers and divide them by 13 until we find the number that gives 3 extra coins left over. Hence, 341 coins.
Make sure to hit the source link below for a list of what BI gauged to be a list of the six most interesting NSA-written brain teasers.