9
$\begingroup$

I'm trying to design a problem that should be as close as possible to the following setup, while meeting some requirements about its solutions.

Initial setup

There is a group of more than 2 people in a room. We know that exactly 2 people are candidates for a prize, and the others are watching. The prize will be given to the oldest of the two old persons.

However, because they are quite old, and because they have their pride, they

  • do not want to disclose their age
  • do not want to give out any information that could let anyone infer their actual age if they are not the same age
  • do not mind however if they are the only ones to know their age in case they are the same age, they just don't want the rest of the group to know.

The goal is then to find out which one of the two is the oldest while keeping their actual age unknown. Note that they could also be the same age.

Constraints on the solutions

The goal is to design a problem that should be close to the initial one above, such that it has at least two solutions:

  • one that seems straightforward but contains a hidden logical flaw (think of the "hidden division by zero" flaw of 3x = 2x => 3 = 2, or a failure to address the age equality case [see Paul Evans' answer])
  • an other one that seems counter-intuitive at first but actually works.

Additional guidelines

I'd like to keep the fact that we want to determine who is older while having very limited knowledge about their actual age.

Using other people or some message-passing is allowed.

Ideally the solution could borrow from number theory, information theory, or other mathematical fields (probabilities?). I know the initial setup is very simple, but I always get amazed at how subtle the solution to problems that are simple to state can be, and this is what I'm looking for.

$\endgroup$
  • $\begingroup$ Are you asking for a solution to the problem, or help designing the problem? $\endgroup$ – f'' Mar 23 '16 at 22:57
  • $\begingroup$ Help designing the problem so that there are two non-trivial solutions, one that seems obvious but is flawed, the other one that seems counter-intuitive but is true. $\endgroup$ – Flavian Hautbois Mar 23 '16 at 23:08
  • $\begingroup$ A correct solution to this problem is actually surprisingly complex; see the millionaire problem. $\endgroup$ – 2012rcampion Mar 24 '16 at 1:36
  • 1
    $\begingroup$ Can you trust those two people? Can you just ask them to whisper their ages to each other and then tell the group who is eldest? $\endgroup$ – Greenstone Walker Mar 24 '16 at 2:05
  • $\begingroup$ I'll have a look at the millionnaire problem thanks! Well, if they whisper their ages to each other it contradicts the fact that they won't disclose their age - even to each other $\endgroup$ – Flavian Hautbois Mar 24 '16 at 7:00
9
$\begingroup$

This solution has the advantage that no-one learns how old the two people are.

Give each of the two people an opaque bag and a box of of weights. Each of them, in private, fills the bag with one weight for each year old they are. Place the two bags on a balance scale. The heavier bag indicates the elder person. If the bags are the same weight, the people are the same age.

Extending the solution to more than two people.

Compare the weights of the 1st and second bags. Take the heaviest (i.e. oldest person) and compare that to the third bag. Take the heaviest of that and compare it to the fourth, and so on.

$\endgroup$
  • $\begingroup$ I like it! Is there a more simple setup that could be done with fewer or no accessories? $\endgroup$ – Flavian Hautbois Mar 24 '16 at 7:03
  • 1
    $\begingroup$ I don't think there is a way to do it without accessories and satisfy the "no-one knows their ages" requirement. $\endgroup$ – Greenstone Walker Mar 24 '16 at 10:15
  • $\begingroup$ I can't think of any either, but can we find a more day-to-day device? Phone? Coins? Something that you may have on you every day $\endgroup$ – Flavian Hautbois Mar 24 '16 at 19:26
  • $\begingroup$ You could try binary: assume their ages are less than some maximum (say 256) then test one binary digit at a time, from most to least significant. The downside is that observers learn an upper bound on the difference between their ages. $\endgroup$ – 2012rcampion Mar 24 '16 at 21:18
4
$\begingroup$

A way for $n$ people that's flawed:

You sit them all in a circle with a starting chair.
You come up with a large random number like 47207.
Secretly whisper it to the person in chair 1.
They secretly add their age, and secretly whisper that sum to the person in the next chair.
And so on around the circle till the last person whispers their sum back to you.
You subtract your secret number and divide by the number of people coming up with the average.
You whisper the average to them all one by one and ask all people younger than that to leave the circle.
Repeat this process until nobody leaves.
Those left will all be the oldest and the same age.
This is flawed because people can figure other people's ages, especially for 2 people.
In that case they simply double the average and subtract their own age to get the other person's age.

$\endgroup$
  • $\begingroup$ I like the way you're thinking. However note that we are only testing two old people's age, and there is actually one case where you could actually infer their actual age, thus contradicting one of the requirements of the setup. This is the case where those two people are exactly the same age. However, this one is a very good candidate for the "flawed" solution, since it seems quite straightforward but fails in a particular case. $\endgroup$ – Flavian Hautbois Mar 23 '16 at 23:12
  • $\begingroup$ @FlavianHautbois Sorry missed the part about there only being two people, OK, so this is possibly a flawed answer. Edited answer accordingly. $\endgroup$ – Paul Evans Mar 23 '16 at 23:16
  • $\begingroup$ Don't delete it, I think it's very good because it points in the right direction. I edited my question, let me know if something's still unclear. $\endgroup$ – Flavian Hautbois Mar 23 '16 at 23:20
  • $\begingroup$ Also, if they're exactly the same age they'll know that when they both win, won't they? Or are the winners not known? In this case they can figure out the other person's age anyway since they have the average and know their own age. They just double the average and subtract their own age. $\endgroup$ – Paul Evans Mar 23 '16 at 23:24
  • $\begingroup$ @FlavianHautbois If the two people are exactly the same age, there's no way for any solution to work, because the resulting tie will allow them to deduce each others' ages. $\endgroup$ – f'' Mar 23 '16 at 23:39
3
$\begingroup$

Here's a solution that seems too simple:

Person A:

Whispers a number, chosen at random, to person B.

Then they both:

Secretly add the two numbers to their age.

After that:

They whisper the results to a third party. The third party indicates which person had the higher number.

Because:

They used a secret number, the third party has no way of finding out their ages. But because they added their ages to the same number, the larger number will belong to the older person.

If the same age:

The third party will still not know their age (since they don't know the secret number), but can indicate that they both had the same number. Then they'll both know they have the same age, but no-one but them will know their age.

$\endgroup$
  • $\begingroup$ It does seem too simple, so what's the catch? $\endgroup$ – Flavian Hautbois Mar 24 '16 at 22:41
  • $\begingroup$ Sorry, by "seems too simple" I didn't mean that it fell into the category of "seems straightforward, but has a logical flaw", I meant that it's a valid solution (I think) that is also pretty simple. If you wanted a solution that involved a bit more insight, you'd need to impose some restriction on the problem that avoided this relatively simple solution. $\endgroup$ – Duncan Mar 24 '16 at 22:43
  • $\begingroup$ This is really elegant, I think. It's worth noting that this solution is functioning by revealing information - in particular, the third party knows the difference of the ages - but the question didn't forbid this. (This could too be hidden by introducing a multiplication step with a suitably chosen number, but the fact that the referee and a candidate could conspire to determine the other's age is inevitable in the setup) $\endgroup$ – Milo Brandt Mar 25 '16 at 0:51
3
$\begingroup$

Both sit at a table, eyes closed, with a token in hand. They count, very slowly, from 1 to 150. Each person, when their age is reached, opens their eyes and places their token on the table, then closes their eyes again.

If they see a token already there, they know they are the elder. If they see no token, they are the younger. If they see the other person with their eyes open, they know they are the same age.

Obviously the counting must continue, even after both tokens are placed, to avoid revealing the age of the elder person.

To avoid anyone else learning their ages, the rest of the group turns their back during the procedure.

$\endgroup$
0
$\begingroup$

There would be a lot of answers to this problem unless worded carefully, which is a big deal on this site. For instance you can ask someone older than them which was born first, you can ask if one remembers when the other was born, there could be math aspects involved which could result in many issues of multiple answers, etc. Information theory would likely be the way to go as a math problem would likely result in it being a math problem than a math puzzle... which is also an important thing to differentiate between.

$\endgroup$
  • $\begingroup$ I completely agree. What I'm looking for is a way to (minimally) extend this problem so that there is no "obvious" solution, while constraining two of the simplest solutions to this problem to behave in a certain way. Does it make sense to you and do you have more suggestions? $\endgroup$ – Flavian Hautbois Mar 23 '16 at 22:45
  • $\begingroup$ Make it to where you can't ask the elders or their elders any questions. Can you figure out a way to make that work? $\endgroup$ – Z. Dailey Mar 23 '16 at 22:47
  • $\begingroup$ Well, let's say we know for sure that those two people are the elders among a group, that's an hypothesis we can add $\endgroup$ – Flavian Hautbois Mar 23 '16 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.