In Judaism, many communal prayers require a minimum of ten people. This quorum is called a "minyan" which is often also used to mean a service in general. (In Orthodox Judaism, only Jewish adult males count for a minyam while in Conservative Judaism all Jewish adults count). However, certain liturgical elements on fast days (such as a Torah reading at the afternoon prayer) require not just ten present, but ten who are actually fasting.
However, people may not wish to advertise that they are not fasting even if they are willing to assist with the minyan. Moreover, even a very observant individual might have a reason not to fast and would not want people to know about it (such as a medical condition). This leads to the following problem: How do we determine how many people are fasting without requiring people to disclose whether or not they are fasting?
In a recent minyan I attended, this question was handled by the gabbai (the person in charge of running the minyan) asking everyone to close their eyes and hold up one hand if they were fasting. This is obviously unsatisfactory since the gabbai finds out who is fasting. One could suggest slips of paper or the like. but they could be easily connected to particular individuals. To make this problem interesting, it is helpful to assume that everyone knows the identity of the sender of any communication they receive. Is there a solution under which individuals' statuses remain private while the minyan is assured of 10 fasters?
Curiously the answer is yes albeit the solution is a bit cumbersome. Here's how: The gabbai picks a random integer (the distribution doesn't matter although in practice one might want a reasonable distribution that approximates a bell curve or an exponential distribution or something similar). The gabbai takes this integer and adds 1 to it if he is fasting. The gabbai whispers this number to another person. That person adds 1 to the total if he is fasting and similarly passes it on to another person. The last person gives his number to the gabbai. The gabbai now subtracts the random integer that they initially added. The total the gabbai has is the number of people fasting.
A few notes about this algorithm. First, it is important that, when the gabbai is picking a random integer, that every integer has some non-zero probability of being chosen. Consider, for example, what would happen if the gabbai was known to only pick positive integers. If the gabbai picks 1, the next person can tell if the gabbai is not fasting. Thus, the gabbai can never pick 1. But then, by the same logic, the gabbai won't be able to pick 2. Or 3. And so on. This problem is avoided if the gabbai can pick any integer whether or not it is positive.
There is also a degenerate case of if only the gabbia is fasting or only the gabbai is not fasting. In those cases, the exceptional individual can work out the status of everyone else.
The algorithm also assumes that people are not going out of their way to obtain information. If two people bracket a third and cooperate, they can figure out the middle person's status as a faster.
In fact, it turns out that it is possible to make a more sophisticated protocol that would prevent this and similar tricks. This would be a variation of an anonymous voting algorithm. However, these algorithms rely on clever cryptography with large prime numbers which is only believed to work rather than proven to work. Implementation also would require much more computation than can be done by hand.
Less intensive algorithms can be used to increase the number of people who must cooperate. It is, for example, an interesting exercise to construct a variation of the above such that finding out someone's status requires the cooperation of at least three people.
This algorithm in practice is cumbersome. Moreover, the goal it seeks to accomplish is minor since, if the fast day liturgy is used, those sections of the services actually need to be performed by people who are fasting. Thus, the gabbai will need to know the status of at least a few people. However, this algorithm has the slight advantage that, if there are not enough people to recite the fast day liturgy, then no one will know which people cause the deficiency.
Bakker: Buy My Crappy Food Because Muslims
3 hours ago