Privacy And Counterfeit Coins

In 2007 Alexander Shapovalov suggested an unusual coin-weighing problem for the sixth international Kolmogorov math tournament [5].

A judge is presented with 80 coins that all look the same, knowing that there are either two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones. A lawyer knows that there are exactly three fake coins and which ones they are. The lawyer must use a balance scale to convince the judge that there are exactly three fake coins and that it is impossible for there to be only two fake coins. She is bound by her contract not to reveal any information about any particular coin. How should she proceed?

Why is this problem so unusual? Let’s take a look back at history. The first coin-weighing problems appeared around 1945 [6, 7]. In all of them, the goal was simply to find a single fake coin among many real coins. After that, many generalizations followed: newer versions of the counterfeit coin problem included finding multiple fake coins, differentiating between coins of arbitrary weights, and so on. All of them, however, had the additional goal of minimizing the number of weighings necessary to locate the fake coin(s)[2]. Shapovalov’s puzzle is the first problem to switch the attention to maintaining the privacy of coins rather than eliminating it. This puzzle is very important and modern; like many other “coin-weighing” problems, it is not about coins—rather, it uses coins to model ideas and to create a simplified version of real-life privacy problems and their potential solutions. A Simplified Version Let us consider a simpler version of Shapovalov’s puzzle to get our feet wet: EXAMPLE 1. In a similar situation as before, the lawyer would like to show the judge that the number of fake coins is exactly two rather than one. STRATEGY 1. The lawyer divides the coins into two piles of 40 so that each pile contains exactly one fake coin. She then puts the piles in the different pans of the scale. The scale balances, which means that the number of fake coins is the same in both of the pans. Therefore, the total number of fake coins is even, and in this case, it is exactly 2. For any particular coin, the judge can’t definitively say whether it is real or fake; we have thus succeeded in our task. Let us introduce some notation before we move forward. We will denote the total number of coins by t, the actual number of fake coins by ƒ, and the number of fake coins that we are trying to disprove by d. We would also like to give a name to a strategy or a series of weighings after which the judge knows nothing about the authenticity of any specific coin. Knop [4] suggests that such strategies be called “shapovalov” in honor of the puzzle’s designer. One of the authors [3] uses the name “unrevealing”. We do not like the name “unrevealing,” as we plan to show that all strategies do reveal some information. We like the name “shapovalov,” but we also want to have a descriptive name. DEFINITION 1. We will call a set of weighings or a strategy where no information about any particular coin is revealed “discreet”. Otherwise, we call the set of weighings “indiscreet”. For the time being, we are only concerned with discreet (shapovalov) strategies. Strategy 1 can be generalized if ƒ and t have a common divisor m that doesn’t divide d: STRATEGY 1*. The lawyer divides the coins into m equal groups with ƒ/m fake coins in each and shows that all of them are equal in weight. Now we can come back to the original puzzle and discuss its solution. Solutions to the Original Problem Motivated by the strategy used in the previous example, the lawyer can try to divide 80 coins into three groups, each containing one fake coin. Clearly, 80 is not divisible by 3, so she makes the three largest possible groups of the same size: each of 26 elements with one fake coin. The lawyer uses two weighings on the scale to demonstrate to the judge that all three groups of 26 have the same weight. What can the judge conclude? He can conclude that either there are 3 fake coins—one in each group, or there are 2 fake coins and they are in the leftover group of 2 coins. Unfortunately, this strategy is not good enough to prove to the judge that there are exactly 3 fake coins. The lawyer decides not to give up and adjusts the strategy in the following manner: STRATEGY 2. The lawyer starts by showing that the three groups of 26 coins, containing one fake coin each, have the same weight. She continues by comparing one of the coins in the leftover group to a real coin, not in the leftover group. This strategy proves that the number of fake coins must be 3 as opposed to 2. However, this strategy is indiscreet—we leave it to the reader to verify these two assertions. In general, coming up with solutions to this problem has proven to be pretty tricky. Most proposed strategies contain some subtle flaw, either failing to rule out 2 fake coins as a possibility or revealing at least one coin’s identity. Now we will present the official (discreet) solution from the competition and again ask our readers to perform the analysis of it. STRATEGY 3. The lawyer divides all coins into 5 piles: A and B with 10 coins each, and C, D, and E with 20 coins each, so that the three fake coins are in piles A, D, and E. The lawyer then conducts three weighings. In the first, she compares A + C against B + D, and the scale balances. In the second weighing, she compares A + B against E, and the scale balances again. In the last weighing, she compares C + D against A + B + E, and shows that the second pan is lighter. We now offer one more discreet strategy for this problem. STRATEGY 4. The lawyer divides all the coins into nine piles: A1, B1, C1, A2, B2, C2, A3, B3, and C3 of sizes 24, 1, 2, 24, 1, 2, 23, 2, and 1, respectively. The lawyer demonstrates that A1 + B1, A2 + B 2, and A3 + B3 balance each other on the scale. Additionally, she shows that B1 + C1, B 2 + C2, and B3 + C3 all have the same weight. Once again, we leave it to the reader to show that there are three different ways for the fake coins to be distributed:

one fake coin in one of each: A1, A 2, A3 (sizes 24, 24, 23) one fake coin in one of each: B1, B 2, B3 (sizes 1, 1, 2) one fake coin in one of each: C1, C 2, C3 (sizes 2, 2, 1).

In each case we have ruled out the possibility of there being two fake coins, and no coin in particular has its identity revealed. See more examples of both insufficient and correct solutions in Knop’s article 4 (in Russian). Discreet Coin Weighings The original puzzle is tricky, but we’ve already managed to demonstrate two solutions. Is it always possible to find a solution that respects the privacy of each individual coin? Or, in our new definition, is it always possible to find a discreet set of weighings? Let us point out the trivial fact that if ƒ = 0 or ƒ = t (and thus the lawyer has to prove to the judge that all coins are real/fake), the privacy of every coin is guaranteed to be violated as a result of the statement being proven. To prevent the identity of any given coin from being revealed, we will only consider the cases for which 0 < ƒ < t, and thus the statement that we are trying to prove is itself discreet. However, as the following lemma proves, it is not always possible to have a discreet set of weighings in this case. LEMMA 1. For t > 1 and ƒ = 1 it is impossible to have a discreet strategy. PROOF. Suppose such a strategy exists and the lawyer convinces the judge that the total number of fake coins is 1. Now consider any weighing that is performed. If it is balanced, then the coins on both pans are all necessarily real. If it is not balanced, then we know that the heavier pan has only real coins. In either case some of the coins are revealed to be genuine, and thus the strategy is indiscreet. We leave it to our readers to show that for the following parameters it is also impossible to have a discreet strategy. • t > 1 and ƒ = t − 1 • ƒ = 2 and d = 0. The Revealing Factor and Coefficient Consider Strategy 1, the simplified case, in which the lawyer splits the coins into two groups of 40. Suppose the judge knows that there are 2 fake coins. What are his chances of guessing the location of a single fake coin before the weighing? They are simply 2 in 80. After the weighing, the judge knows that there is a fake coin in each group of 40, so his chance of finding one coin is 1 in 40—the same as before. Although it may not seem as though any information has been revealed, the opposite turns out to be true. Before the weighings, the two counterfeits can be any of the 80 coins, and the number of equally likely distributions of these fake coins is (802) = 3160. After the weighings, there is one fake in each pile of 40, and the number of possibilities is reduced to (401)2 = 1600. The general challenge of trying to guess the location of a single fake coin after a successful strategy is discussed in [1]. We would like to introduce the notions of a revealing factor and a revealing coefficient to quantify this observation. Before the weighings, if the judge knows that the number of fake coins is exactly ƒ, then any set of ƒ coins might be the set of fake coins. The number of equally likely possibilities is (tƒ), and we call this value ‘‘old possibilities’’. After the weighings, the set of possibilities decreases so that not any arbitrary group of ƒ coins could be the set of fake coins. We call the number of sets of ƒ coins, which could be fake after the weighings are done, the ‘‘new possibilities’’. DEFINITION 2. We call the ratio of the number of old possibilities to the new possibilities, after a successful strategy, the revealing factor. We denote it by X:

We would also like to introduce the notion of a ‘‘revealing coefficient’’, as used in [3]. The revealing coefficient is the portion of information that is revealed in the process of proving that there are exactly ƒ fake coins: DEFINITION 3. The revealing coefficient, denoted by R, is defined as 1 − 1/X :

A strategy that reveals little about the exact locations of the fake coins corresponds to a higher number of new possibilities. It follows that we would like both the revealing coefficient and the revealing factor to be as small as possible to minimize the transfer of information. In Strategy 1, the revealing factor X is 3160/1600 = 1:98. The revealing coefficient R is ( 3160 − 1600 ) / 3160 ≈ 0:494, slightly less than one half. The computation of the revealing factors for Strategy 3 and Strategy 4 are more involved and are left to the reader. The answers are approximately 10.27 and 6.20, respectively. Different Strategies Reveal Different Amounts of Information Suppose we have 80 coins and we want to prove that 4 are fake as opposed to 3; that is, t = 80, ƒ = 4, and d = 3. We can use Strategy 1* to do proceed: Divide all coins into four piles of 20 with each pile containing one fake coin. Showing that all piles weigh the same tells the judge the number of fake coins must be a multiple of 4, and we are done. We can, however, produce another discreet strategy: divide the coins into two piles of 40 and put two fake coins in each pile. After comparing the two piles, the judge knows that the number of fake coins is even. Both strategies are discreet, but the revealing factor and coefficient are different, which we leave for the reader to check. The second strategy is significantly less revealing; dividing all the coins into fewer equivalent piles is clearly preferable in this case. The revealing factor/coefficient can be defined for both discreet and indiscreet strategies. Surprisingly, we often see that indiscreet strategies reveal less information than discreet strategies do. Let’s go back to the original problem and its ‘‘wrong,’’ or rather indiscreet solution described in Strategy 2. The judge knows the locations of 3 real coins after the weighings. The other coins are divided into 3 groups of 26, 26, and 25 coins, containing one fake coin each. We leave it to the reader to check that the revealing factor is X ≈ 4:86. Although this strategy is indiscreet and the privacy of 3 real coins is violated, it is less revealing than the discreet Strategies 3 and 4 with revealing factors of 10.27 and 6.20, respectively. In a way, the three coins that were exposed as being real effectively ‘‘sacrificed’’ their privacy to make the other coins more secure in their wish to remain hidden. An Optimality Proof Here we would like to show a proof of optimality for a discreet strategy for certain parameters. Namely, we consider the case when t = 2k, ƒ = 2, and d = 1, for some positive integer k > 1. We’ve already discussed the strategy (see Strategy 1*) using one weighing: divide all the coins into two piles of size k, put fake coins into the separate piles, and compare the piles. It might seem obvious that this is a “least revealing,” or optimal, strategy, but still we need a proof. First, we introduce more definitions and notation. During any weighing, a coin’s presence on the left pan is denoted by L, a coin’s presence on the right pan is denoted by R, and a coin not participating (one that is left outside of the outside of the weighing) is denoted by O. After all the weighings, every coin’s path can be described as a string of L’s, R’s, and O’s. DEFINITION 4. The string of L’s, R’s, and O’s corresponding to the location of a given coin in every weighing is called the coin’s ‘‘itinerary’’. Given an itinerary ∂, we denote the set of all coins with this itinerary as ∂, and the size of this set as ∂. We will introduce an involutive operation on itineraries called conjugation: DEFINITION 5. Given an itinerary ∂, ‘‘conjugate itinerary’’, denoted by ∂, is the unique itinerary in which all R’s are replaced by L’s, and all L’s are replaced by R’s. Notice that this is an involution as =∂ = ∂. In addition, the only self-conjugate itinerary is a string of O’s. After the weighings we can partition all the coins into groups by their itineraries. In the following preliminary lemma it is not necessary that t be even. LEMMA 2. If ƒ = 2 and d = 1 ,then the set of itineraries of a discreet strategy has the following properties: If there are coins with itinerary ∂, then there are coins with itinerary −∂. In addition, there are no coins with a self-conjugate itinerary. Also, all weighings are balanced. PROOF. All weighings must be balanced, otherwise the heavier pan must contain only real coins and the strategy is indiscreet. It follows that the two fake coins can’t be in the same pan at any point. Moreover, if a fake coin is in one of the pans during a weighing, the other fake coin must be in the other pan to balance it. This means that the fake coins have conjugate itineraries. Because of the aforementioned condition, if there exists a coin with an itinerary ∂ and there are no coins with itinerary −∂, then all the coins in ∂ are necessarily real. If one coin did not partake in any of the measurements and all the weighings were balanced, then we have not disproven the possibility of only one fake coin. Thus there cannot be any coins with a self-conjugate itinerary. Now we are ready to prove the optimality theorem for an even number of coins. THEOREM 3. If t is even, ƒ = 2 and d = 1 , then Strategy 1 is the least revealing of any possible strategy. PROOF. All the coins are partitioned into groups with the same itineraries and all the itineraries are paired up by conjugation. The set of itineraries is ( ∂j ∂j) = 1, 2, 3….If one fake coin belongs to ∂j, then the other fake coin must belong to ∂j. This means the total number of new possibilities is

Standard algebra arguments show that the number of new possibilities is maximized when there is exactly one itinerary pair with two itineraries of equal size. An Oddity: The Case of Odd t We would like to discuss optimality in a more complicated case: when the total number of coins is odd, ƒ = 2, and d = 1. A proof of the following lemma can be found in [1]. LEMMA 4. A discreet strategy for the given parameters must generate at least 6 different itineraries. Among the itineraries will be at least 3 conjugate pairs; additionally, the number of coins in the two groups in each pair must be of different parity. Now we will provide more examples for which a discreet strategy does not exist, again outsourcing the proof to [1]. COROLLARY 5. For ƒ = 2 and d = 1, it is impossible to have a discreet strategy when t = 3, t = 5 or t = 7. What happens when t > 7? By modifying Strategy 4 we can create a discreet strategy that works for odd t > 7. STRATEGY 4*. Consider piles A and of sizes ⌊ t / 2 ⌋ − 2 and ⌊ t / 2 ⌋ − 3, respectively. Piles B and B have sizes 1 and 2, respectively. Piles C and C have sizes 2 and 1. The lawyer distributes the two fake coins into piles A and A, B and B, or C and C. This strategy has two weighings. In the first, the lawyer compares ⌊ t / 2 ⌋ − 1 coins belonging to A and B against ⌊ t / 2 ⌋ − 1 coins belonging to A and B. In the second weighing she compares three coins belonging to B and C against the same number of coins in B and C. LEMMA 6. For ƒ = 2 and d = 1, Strategy 4* is discreet when t is odd and t > 7. PROOF. All coins were on the scale and all the weighings were balanced. This means that there are necessarily two fake coins. No information about any particular coin is revealed as the fake coins can belong to any pair of groups with conjugate itineraries. LEMMA 7. If t is odd, ƒ = 2 and d = 1 , then Strategy 4* is least revealing. The proof is similar to that of Theorem 3 and can be found in [1]. Conclusion Do fake coins really need a lawyer’s protection in the courtroom? Most likely not. But mathematicians make a living by reducing difficult problems to easier, more manageable ones. In short, our discussion demonstrates that collecting aggregated information from databases reveals some additional information in the process; this paper is our attempt to quantify by how much. References [1] N. Diaco, T. Khovanova, Weighing Coins and Keeping Secrets, arXiv:1508.05052, (2015). [2] R. K. Guy and R. J. Nowakowski, Coin-weighing problems, Amer. Math. Monthly, 102 (1995), 164–167. [3] T. Khovanova, Unrevealing Coin Weighings, available at http:// blog.tanyakhovanova.com/2009/08/unrevealing-coin-weighings/. [4] K. Knop, The mystery of fake coins, Matematika, N8 (2008), 29–31 (in Russian). [5] Kolmogorov Math Tournaments, http://cdoosh.ru/kolm/kolm.html. [6] E. V. Newbery, The penny problem, Note 2342, Math. Gaz., 37 (1953) 130. [7] B. L. Schwartz, Letter: Truth about false coins, Math. Mag., 51 (1978) 254. [8] Y. Zhang, Coins and Low-Knowledge Proofs, Concrete Nonsense blog, available at https://concretenonsense.wordpress.com/2009/ 12/17/m-3-coins-and-low-knowledge-proofs/.

In 2007 Alexander Shapovalov suggested an unusual coin-weighing problem for the sixth international Kolmogorov math tournament [5].

A lawyer knows that there are exactly three fake coins and which ones they are. The lawyer must use a balance scale to convince the judge that there are exactly three fake coins and that it is impossible for there to be only two fake coins. She is bound by her contract not to reveal any information about any particular coin. How should she proceed?

Shapovalov’s puzzle is the first problem to switch the attention to maintaining the privacy of coins rather than eliminating it. This puzzle is very important and modern; like many other “coin-weighing” problems, it is not about coins—rather, it uses coins to model ideas and to create a simplified version of real-life privacy problems and their potential solutions.

A Simplified Version

Let us consider a simpler version of Shapovalov’s puzzle to get our feet wet:

EXAMPLE 1. In a similar situation as before, the lawyer would like to show the judge that the number of fake coins is exactly two rather than one.

STRATEGY 1. The lawyer divides the coins into two piles of 40 so that each pile contains exactly one fake coin. She then puts the piles in the different pans of the scale.

The scale balances, which means that the number of fake coins is the same in both of the pans. Therefore, the total number of fake coins is even, and in this case, it is exactly 2. For any particular coin, the judge can’t definitively say whether it is real or fake; we have thus succeeded in our task.

Let us introduce some notation before we move forward. We will denote the total number of coins by t, the actual number of fake coins by ƒ, and the number of fake coins that we are trying to disprove by d.

We would also like to give a name to a strategy or a series of weighings after which the judge knows nothing about the authenticity of any specific coin. Knop [4] suggests that such strategies be called “shapovalov” in honor of the puzzle’s designer. One of the authors [3] uses the name “unrevealing”. We do not like the name “unrevealing,” as we plan to show that all strategies do reveal some information. We like the name “shapovalov,” but we also want to have a descriptive name.

DEFINITION 1. We will call a set of weighings or a strategy where no information about any particular coin is revealed “discreet”. Otherwise, we call the set of weighings “indiscreet”.

For the time being, we are only concerned with discreet (shapovalov) strategies. Strategy 1 can be generalized if ƒ and t have a common divisor m that doesn’t divide d:

STRATEGY 1*. The lawyer divides the coins into m equal groups with ƒ/m fake coins in each and shows that all of them are equal in weight.

Now we can come back to the original puzzle and discuss its solution.

Solutions to the Original Problem

Motivated by the strategy used in the previous example, the lawyer can try to divide 80 coins into three groups, each containing one fake coin. Clearly, 80 is not divisible by 3, so she makes the three largest possible groups of the same size: each of 26 elements with one fake coin. The lawyer uses two weighings on the scale to demonstrate to the judge that all three groups of 26 have the same weight. What can the judge conclude? He can conclude that either there are 3 fake coins—one in each group, or there are 2 fake coins and they are in the leftover group of 2 coins. Unfortunately, this strategy is not good enough to prove to the judge that there are exactly 3 fake coins. The lawyer decides not to give up and adjusts the strategy in the following manner:

STRATEGY 2. The lawyer starts by showing that the three groups of 26 coins, containing one fake coin each, have the same weight. She continues by comparing one of the coins in the leftover group to a real coin, not in the leftover group.

This strategy proves that the number of fake coins must be 3 as opposed to 2. However, this strategy is indiscreet—we leave it to the reader to verify these two assertions. In general, coming up with solutions to this problem has proven to be pretty tricky. Most proposed strategies contain some subtle flaw, either failing to rule out 2 fake coins as a possibility or revealing at least one coin’s identity.

Now we will present the official (discreet) solution from the competition and again ask our readers to perform the analysis of it.

STRATEGY 3. The lawyer divides all coins into 5 piles: A and B with 10 coins each, and C, D, and E with 20 coins each, so that the three fake coins are in piles A, D, and E. The lawyer then conducts three weighings. In the first, she compares A + C against B + D, and the scale balances. In the second weighing, she compares A + B against E, and the scale balances again. In the last weighing, she compares C + D against A + B + E, and shows that the second pan is lighter.

We now offer one more discreet strategy for this problem.

STRATEGY 4. The lawyer divides all the coins into nine piles: A1, B1, C1, A2, B2, C2, A3, B3, and C3 of sizes 24, 1, 2, 24, 1, 2, 23, 2, and 1, respectively. The lawyer demonstrates that A1 + B1, A2 + B 2, and A3 + B3 balance each other on the scale. Additionally, she shows that B1 + C1, B 2 + C2, and B3 + C3 all have the same weight.

Once again, we leave it to the reader to show that there are three different ways for the fake coins to be distributed:

one fake coin in one of each: A1, A 2, A3 (sizes 24, 24, 23)
one fake coin in one of each: B1, B 2, B3 (sizes 1, 1, 2)
one fake coin in one of each: C1, C 2, C3 (sizes 2, 2, 1).

In each case we have ruled out the possibility of there being two fake coins, and no coin in particular has its identity revealed.

See more examples of both insufficient and correct solutions in Knop’s article 4 (in Russian).

Discreet Coin Weighings

The original puzzle is tricky, but we’ve already managed to demonstrate two solutions. Is it always possible to find a solution that respects the privacy of each individual coin? Or, in our new definition, is it always possible to find a discreet set of weighings?

Let us point out the trivial fact that if ƒ = 0 or ƒ = t (and thus the lawyer has to prove to the judge that all coins are real/fake), the privacy of every coin is guaranteed to be violated as a result of the statement being proven.

To prevent the identity of any given coin from being revealed, we will only consider the cases for which 0 < ƒ < t, and thus the statement that we are trying to prove is itself discreet. However, as the following lemma proves, it is not always possible to have a discreet set of weighings in this case.

LEMMA 1. For t > 1 and ƒ = 1 it is impossible to have a discreet strategy.

PROOF. Suppose such a strategy exists and the lawyer convinces the judge that the total number of fake coins is 1. Now consider any weighing that is performed. If it is balanced, then the coins on both pans are all necessarily real. If it is not balanced, then we know that the heavier pan has only real coins. In either case some of the coins are revealed to be genuine, and thus the strategy is indiscreet.

We leave it to our readers to show that for the following parameters it is also impossible to have a discreet strategy.

• t > 1 and ƒ = t − 1

• ƒ = 2 and d = 0.

The Revealing Factor and Coefficient

Consider Strategy 1, the simplified case, in which the lawyer splits the coins into two groups of 40. Suppose the judge knows that there are 2 fake coins. What are his chances of guessing the location of a single fake coin before the weighing? They are simply 2 in 80. After the weighing, the judge knows that there is a fake coin in each group of 40, so his chance of finding one coin is 1 in 40—the same as before.

Although it may not seem as though any information has been revealed, the opposite turns out to be true. Before the weighings, the two counterfeits can be any of the 80 coins, and the number of equally likely distributions of these fake coins is (802) = 3160. After the weighings, there is one fake in each pile of 40, and the number of possibilities is reduced to (401)2 = 1600. The general challenge of trying to guess the location of a single fake coin after a successful strategy is discussed in [1].

We would like to introduce the notions of a revealing factor and a revealing coefficient to quantify this observation. Before the weighings, if the judge knows that the number of fake coins is exactly ƒ, then any set of ƒ coins might be the set of fake coins. The number of equally likely possibilities is (tƒ), and we call this value ‘‘old possibilities’’. After the weighings, the set of possibilities decreases so that not any arbitrary group of ƒ coins could be the set of fake coins. We call the number of sets of ƒ coins, which could be fake after the weighings are done, the ‘‘new possibilities’’.

DEFINITION 2. We call the ratio of the number of old possibilities to the new possibilities, after a successful strategy, the revealing factor. We denote it by X:

DEFINITION 3. The revealing coefficient, denoted by R, is defined as 1 − 1/X :

In Strategy 1, the revealing factor X is 3160/1600 = 1:98. The revealing coefficient R is ( 3160 − 1600 ) / 3160 ≈ 0:494, slightly less than one half. The computation of the revealing factors for Strategy 3 and Strategy 4 are more involved and are left to the reader. The answers are approximately 10.27 and 6.20, respectively.

Different Strategies Reveal Different Amounts of Information

Suppose we have 80 coins and we want to prove that 4 are fake as opposed to 3; that is, t = 80, ƒ = 4, and d = 3. We can use Strategy 1* to do proceed: Divide all coins into four piles of 20 with each pile containing one fake coin. Showing that all piles weigh the same tells the judge the number of fake coins must be a multiple of 4, and we are done. We can, however, produce another discreet strategy: divide the coins into two piles of 40 and put two fake coins in each pile. After comparing the two piles, the judge knows that the number of fake coins is even. Both strategies are discreet, but the revealing factor and coefficient are different, which we leave for the reader to check.

The second strategy is significantly less revealing; dividing all the coins into fewer equivalent piles is clearly preferable in this case.

The revealing factor/coefficient can be defined for both discreet and indiscreet strategies. Surprisingly, we often see that indiscreet strategies reveal less information than discreet strategies do. Let’s go back to the original problem and its ‘‘wrong,’’ or rather indiscreet solution described in Strategy 2. The judge knows the locations of 3 real coins after the weighings. The other coins are divided into 3 groups of 26, 26, and 25 coins, containing one fake coin each. We leave it to the reader to check that the revealing factor is X ≈ 4:86. Although this strategy is indiscreet and the privacy of 3 real coins is violated, it is less revealing than the discreet Strategies 3 and 4 with revealing factors of 10.27 and 6.20, respectively. In a way, the three coins that were exposed as being real effectively ‘‘sacrificed’’ their privacy to make the other coins more secure in their wish to remain hidden.

An Optimality Proof

Here we would like to show a proof of optimality for a discreet strategy for certain parameters. Namely, we consider the case when t = 2k, ƒ = 2, and d = 1, for some positive integer k > 1. We’ve already discussed the strategy (see Strategy 1*) using one weighing: divide all the coins into two piles of size k, put fake coins into the separate piles, and compare the piles.

It might seem obvious that this is a “least revealing,” or optimal, strategy, but still we need a proof. First, we introduce more definitions and notation. During any weighing, a coin’s presence on the left pan is denoted by L, a coin’s presence on the right pan is denoted by R, and a coin not participating (one that is left outside of the outside of the weighing) is denoted by O.

After all the weighings, every coin’s path can be described as a string of L’s, R’s, and O’s.

DEFINITION 4. The string of L’s, R’s, and O’s corresponding to the location of a given coin in every weighing is called the coin’s ‘‘itinerary’’.

Given an itinerary ∂, we denote the set of all coins with this itinerary as ∂, and the size of this set as ∂. We will introduce an involutive operation on itineraries called conjugation:

DEFINITION 5. Given an itinerary ∂, ‘‘conjugate itinerary’’, denoted by ∂, is the unique itinerary in which all R’s are replaced by L’s, and all L’s are replaced by R’s.

Notice that this is an involution as =∂ = ∂. In addition, the only self-conjugate itinerary is a string of O’s. After the weighings we can partition all the coins into groups by their itineraries.

In the following preliminary lemma it is not necessary that t be even.

LEMMA 2. If ƒ = 2 and d = 1 ,then the set of itineraries of a discreet strategy has the following properties: If there are coins with itinerary ∂, then there are coins with itinerary −∂. In addition, there are no coins with a self-conjugate itinerary. Also, all weighings are balanced.

PROOF. All weighings must be balanced, otherwise the heavier pan must contain only real coins and the strategy is indiscreet. It follows that the two fake coins can’t be in the same pan at any point. Moreover, if a fake coin is in one of the pans during a weighing, the other fake coin must be in the other pan to balance it. This means that the fake coins have conjugate itineraries.

Because of the aforementioned condition, if there exists a coin with an itinerary ∂ and there are no coins with itinerary −∂, then all the coins in ∂ are necessarily real.

If one coin did not partake in any of the measurements and all the weighings were balanced, then we have not disproven the possibility of only one fake coin. Thus there cannot be any coins with a self-conjugate itinerary.

Now we are ready to prove the optimality theorem for an even number of coins.

THEOREM 3. If t is even, ƒ = 2 and d = 1 , then Strategy 1 is the least revealing of any possible strategy.

PROOF. All the coins are partitioned into groups with the same itineraries and all the itineraries are paired up by conjugation. The set of itineraries is ( ∂j ∂j) = 1, 2, 3….If one fake coin belongs to ∂j, then the other fake coin must belong to ∂j. This means the total number of new possibilities is

Standard algebra arguments show that the number of new possibilities is maximized when there is exactly one itinerary pair with two itineraries of equal size.

An Oddity: The Case of Odd t

We would like to discuss optimality in a more complicated case: when the total number of coins is odd, ƒ = 2, and d = 1. A proof of the following lemma can be found in [1].

LEMMA 4. A discreet strategy for the given parameters must generate at least 6 different itineraries. Among the itineraries will be at least 3 conjugate pairs; additionally, the number of coins in the two groups in each pair must be of different parity.

Now we will provide more examples for which a discreet strategy does not exist, again outsourcing the proof to [1].

COROLLARY 5. For ƒ = 2 and d = 1, it is impossible to have a discreet strategy when t = 3, t = 5 or t = 7.

What happens when t > 7? By modifying Strategy 4 we can create a discreet strategy that works for odd t > 7.

STRATEGY 4*. Consider piles A and of sizes ⌊ t / 2 ⌋ − 2 and ⌊ t / 2 ⌋ − 3, respectively. Piles B and B have sizes 1 and 2, respectively. Piles C and C have sizes 2 and 1. The lawyer distributes the two fake coins into piles A and A, B and B, or C and C.

This strategy has two weighings. In the first, the lawyer compares ⌊ t / 2 ⌋ − 1 coins belonging to A and B against ⌊ t / 2 ⌋ − 1 coins belonging to A and B. In the second weighing she compares three coins belonging to B and C against the same number of coins in B and C.

LEMMA 6. For ƒ = 2 and d = 1, Strategy 4* is discreet when t is odd and t > 7.

PROOF. All coins were on the scale and all the weighings were balanced. This means that there are necessarily two fake coins.

No information about any particular coin is revealed as the fake coins can belong to any pair of groups with conjugate itineraries.

LEMMA 7. If t is odd, ƒ = 2 and d = 1 , then Strategy 4* is least revealing.

The proof is similar to that of Theorem 3 and can be found in [1].

Conclusion

Do fake coins really need a lawyer’s protection in the courtroom? Most likely not. But mathematicians make a living by reducing difficult problems to easier, more manageable ones. In short, our discussion demonstrates that collecting aggregated information from databases reveals some additional information in the process; this paper is our attempt to quantify by how much.

References

[1] N. Diaco, T. Khovanova, Weighing Coins and Keeping Secrets, arXiv:1508.05052, (2015).

[2] R. K. Guy and R. J. Nowakowski, Coin-weighing problems, Amer. Math. Monthly, 102 (1995), 164–167.

[3] T. Khovanova, Unrevealing Coin Weighings, available at http:// blog.tanyakhovanova.com/2009/08/unrevealing-coin-weighings/.

[4] K. Knop, The mystery of fake coins, Matematika, N8 (2008), 29–31 (in Russian).

[5] Kolmogorov Math Tournaments, http://cdoosh.ru/kolm/kolm.html.

[6] E. V. Newbery, The penny problem, Note 2342, Math. Gaz., 37 (1953) 130.

[7] B. L. Schwartz, Letter: Truth about false coins, Math. Mag., 51 (1978) 254.

[8] Y. Zhang, Coins and Low-Knowledge Proofs, Concrete Nonsense blog, available at https://concretenonsense.wordpress.com/2009/ 12/17/m-3-coins-and-low-knowledge-proofs/.

A Simplified Version#

Solutions to the Original Problem#

Discreet Coin Weighings#

The Revealing Factor and Coefficient#

Different Strategies Reveal Different Amounts of Information#

An Optimality Proof#

An Oddity: The Case of Odd t#

Conclusion#

References#