Calculating the Average Age in Secret
Oskar van Deventer is a designer of beautiful mechanical puzzles. For the recent mini-MOVES gathering at the MoMath, he asked people in his Zoom breakout room to calculate the average age in the room without revealing their actual ages. I know the following solution to this puzzle.
People agree on a large number N that is guaranteed to be greater than the sum of all the ages. The first person, say Alice, thinks of a uniformly random integer R between 0 and N. Alice adds her age to R modulo N and passes the result to the second person, say Bob. Bob adds his age modulo N and passes the result to the third person, and so on. When the result comes back to Alice, she subtracts R modulo N and announces the sum total of all the ages.
During this process, no one gets any information about other people’s ages. But two people can collude to figure out the sum of the ages of the people “sitting” between them.
I gave this problem to my grandson, and he suggested the following procedure. First, people choose two trusted handlers: Alice and Bob. Then, each person splits their age into the sum of two numbers (the splitting should be random and allow one of the numbers to be negative). They then give one number to Alice and another to Bob. Alice and Bob announce the sums of the numbers they receive. After that, the sum total of everyone’s ages is the sum of the two numbers that Alice and Bob announce.
The advantage of this method is that no two people, except Alice and Bob, can collude to get more information. The disadvantage is that if Alice and Bob collude, they would know everyone’s age. Which method would you prefer?
Share:
Lev Lipkin:
Can disadvantage of your grandson’s method be addressed by recursion? Instead of splitting in 2, split in 3 numbers. 1 number of those 3 stays with a person, the other2 are given to handlers, one to each.
30 March 2022, 2:19 pmRepeat procedure with remaining numbers left with each person and other 2 handlers until every person was handler.
It seems to me that to know age of other or others all have to collide. But then they could just share their ages.
tanyakh:
Lev, love your suggestion.
30 March 2022, 2:26 pmAlistair:
You can actually do better than both solutions with N people:
With no trusted third parties, you can calculate the ages such that (N-1) people must collude to reveal an actual age (which is logically the best you can do!).
This is a motivational puzzle in: https://en.m.wikipedia.org/wiki/Secure_multi-party_computation
The sillier answers:
They could also use the ‘recently’ discovered homomorphic encryption.
Of course anyone could lie, so they secretly know the average as long as no-one else does—and no amount of collusion will discover their true age!
1 April 2022, 3:33 amCarl Feynman:
Here’s a method that goes up to requiring N-1 people to collude.
1. Everyone chooses a set of N numbers that add up to their age, randomly over some large range.
8 April 2022, 11:42 am2. They privately communicate each number to a different person, including “communicating” one number to themselves.
3. Everyone announces the sum of the numbers they got.
4. The sum of the announced numbers is the sum of the ages.
Lazar Ilic:
Fantastic, interesting, fascinating post yet again Dr. Tanya Khovanova! What a great web log you have been composing here! What an eminent readership and commentariat! This is so exquisitely excellent I like to calculate the average age in secret! You know to the kids out there reading, quite a few of the so called “oldies” are rather sharp and can tell you about many many many intrigues and wisdoms. And so at the Gathering 4 Gardner conference ah the average age of me and Dr. Peter Winkler… he does not look a day over 40 but I happen to think I know the date of his birth… ah the puzzles can be terse and insightful… perhaps function to keep minds a little younger and sharper and happier for those who enjoy them! It is a shame I did not attend the 14th Edition but perhaps when the YouTube channel “G4G Celebration” posts footage I will take Notes or simply enjoy from my home <3
11 April 2022, 1:46 pmW:
Since ages are small integers, how about have a bucket with large integer N number of pennies. Everyone takes a cup and scoops some number of pennies that is greater than their age. Each count out their age in pennies and pour into a second bucket and return the rest to the first bucket. The sum of ages is number of pennies in second bucket.
16 June 2022, 6:20 pmSahyr:
A twist on the Grandson’s solution –
People stand in a circle. Start from any person & they tell the person on the right the previous sum (0 at the start) added to the unit digit of their Age OR the ten’s digit of their Age multiplied by 10 (E.g, If Alice is of age 45 & starts, she tells Bob either 40 or 5). Continue this circle twice & by the end, the starting person knows the sum of all the ages. Dividing this by the number of people will give the average age.
15 June 2023, 5:01 am