<p>This answer continues Peter's.  It assumes Peter's interpretation of the problem and verifies that with that interpretation the function <span class="math-container">$f(S)=\min S$</span> is optimal, as Peter suggested.  Here's the problem statement:</p>
<blockquote>
<p><em>Fix integers <span class="math-container">$s\ge 1$</span> and <span class="math-container">$n\ge s$</span>.  Let <span class="math-container">$\mathcal S_s = \{S\subseteq [n] : |S| = s\}$</span> contain the size-<span class="math-container">$s$</span> subsets of <span class="math-container">$[n]$</span>.  The goal is to determine the minimum, over all functions <span class="math-container">$f:\mathcal S_s\to[n]$</span> such that <span class="math-container">$f(S)\in S$</span> for all <span class="math-container">$S\in\mathcal S_s$</span>, of the entropy of the distribution of the random variable <span class="math-container">$f(S)$</span> where <span class="math-container">$S$</span> is drawn uniformly at random from <span class="math-container">$\mathcal S_s$</span>.</em></p>
</blockquote>
<p>Before we begin, here's a formula for the entropy for an arbitrary <span class="math-container">$f$</span>.
For <span class="math-container">$i\in [n]$</span> let <span class="math-container">$f^{-1}(i) = \{S\in \mathcal S_s : f(S) = i\}$</span> contain the sets that <span class="math-container">$f$</span> maps to <span class="math-container">$i$</span>.  For the random choice of <span class="math-container">$S$</span> described above, for each <span class="math-container">$i$</span>, the entropy of <span class="math-container">$f(S)$</span> is
<span class="math-container">$$\begin{align}
{} \sum_{i=1}^n -\Pr[f(S) = i] \ln \Pr[f(S) = i]
&amp; {} =\sum_{i=1}^n -\frac{|f^{-1}(i)|}{n\choose s} \ln \frac{|f^{-1}(i)|}{n\choose s}
\\
&amp; {} =\ln {n\choose s} - {n\choose s}^{-1}\sum_{i=1}^n |f^{-1}(i)|\ln |f^{-1}(i)|.~~~~~~(1)
\end{align}
$$</span></p>
<p>Note that for the particular function <span class="math-container">$\hat f(S) = \min S$</span> we have <span class="math-container">$|\hat f^{-1}(i)| = {n-i\choose s-1}$</span> so for this <span class="math-container">$\hat f$</span> the entropy in question is
<span class="math-container">$$
\sum_{j=s-1}^{n-1} \frac{j\choose s-1}{n\choose s} \ln \frac{n\choose s}{j\choose s-1}
=
\ln {n\choose s} - {n\choose s}^{-1}\sum_{j=s}^{n-1} {j\choose s-1}\ln {j\choose s-1}.$$</span></p>
<p>For example, when <span class="math-container">$s=2$</span>, the entropy is <span class="math-container">$\ln {n\choose 2} - {n\choose 2}^{-1}\displaystyle\sum_{j=2}^{n-1} j \ln j = \ln(n/2)+1/2 \pm o(1)$</span>.</p>
<p>When <span class="math-container">$s=2$</span> and <span class="math-container">$n=3$</span>, the entropy is <span class="math-container">$\ln 3 - (2/3)\ln 2 = H(1/3)$</span>.</p>
<p><strong>Lemma 1.</strong> <em>The function <span class="math-container">$\hat f(S) = \min S$</span> is optimal.</em></p>
<p><em>Proof.</em></p>
<ol>
<li><p>Let <span class="math-container">$f$</span> be any optimal function.</p>
</li>
<li><p>By symmetry assume without loss of generality that <span class="math-container">$|f^{-1}(1)| \ge |f^{-1}(2)| \ge \cdots \ge |f^{-1}(n)|$</span>.</p>
</li>
<li><p>Assume for contradiction that <span class="math-container">$f\not\equiv \hat f$</span>.</p>
</li>
<li><p>Fix an <span class="math-container">$S'\in \mathcal S_s$</span> such that <span class="math-container">$f(S') \ne \min S'$</span>.</p>
</li>
<li><p>Let <span class="math-container">$m = \min S'$</span> and <span class="math-container">$p=f(S')$</span>.  Because <span class="math-container">$p\in S'\setminus\{m\}$</span> we have <span class="math-container">$p &gt; m$</span>.</p>
</li>
<li><p>Let <span class="math-container">$a = |f^{-1}(m)|$</span> and <span class="math-container">$b=|f^{-1}(p)|\ge 1$</span>.  By Steps 2 and 5 we have <span class="math-container">$a \ge b \ge 1$</span>.</p>
</li>
<li><p>Consider modifying <span class="math-container">$f$</span> by changing <span class="math-container">$f(S')$</span> to <span class="math-container">$i$</span>.</p>
</li>
<li><p>This changes <span class="math-container">$\sum_{i=1}^n |f^{-1}(i)|\ln |f^{-1}(i)|$</span> by an additive
<span class="math-container">$$[a \ln a + b\ln b] - [(a+1)\ln(a+1) + (b-1)\ln (b-1)].$$</span></p>
</li>
<li><p>Because <span class="math-container">$x \mapsto x\ln x$</span> is strictly convex and <span class="math-container">$a\ge b$</span>, this change is strictly positive.</p>
</li>
<li><p>So, by Equation (1) before the lemma, this change decreases the entropy.</p>
</li>
<li><p>This contradicts the optimality of <span class="math-container">$f$</span>.  <span class="math-container">$~~~~~\Box$</span></p>
</li>
</ol>

CC BY-SA 4.0
2022-11-18T15:35:35.253Z
2022-11-19T22:27:26.570Z
2022-11-19T22:27:26.570Z
Neal Young
<p>This is a request for clarification and a partial answer, but I'm posting it as an answer because there is no way for it to fit in a comment.</p>
<p>Is the OP asking for how much information you need to send, or the smallest number of possibilities that you need to use in order to answer? These are two distinct questions. His definition of <span class="math-container">$W$</span> would point to the second question, but the title of his question points to the first,</p>
<p>Suppose you have three numbers, and we want to specify a number chosen from a subset of two of them. How much information do we need?</p>
<p>Let's use the following strategy: the two players choose a random seed, and generate a pseudorandom permutation of the three numbers each time. The second player sends the first player &quot;<span class="math-container">$1$</span>&quot; if the first element of the permutation is in the subset, and &quot;<span class="math-container">$2$</span>&quot; otherwise.</p>
<p>The player is then sending &quot;<span class="math-container">$1$</span>&quot; two-thirds of the time, and &quot;<span class="math-container">$2$</span>&quot; one-third of the time. The amount of information needed for this is
<span class="math-container">$$H\left(\frac{1}{3}\right) = -\frac{1}{3} \log_2 \frac{1}{3} -\frac{2}{3} \log_2 \frac{2}{3} = .9183 \mathrm{\ bits},$$</span>
which is less than the log of the number <span class="math-container">$W$</span> of distinct responses you need to send (namely <span class="math-container">$1 = \log_2 2$</span>).</p>
<p>I believe this is the optimal strategy for accomplishing this task, although since I don't have a proof, I might easily be wrong.</p>
<p>This strategy is generalizable to a subset of <span class="math-container">$k$</span> chosen from a set of <span class="math-container">$n$</span>, although it may take some work to give a nice formula for how much information is needed.</p>

CC BY-SA 4.0
2022-11-17T23:19:58.427Z
Peter, can you clarify something I'm confused about?  Namely, what exactly does it mean to "specify a number chosen from a subset of two of them"?  There must be some underlying assumptions about how the subset and number are chosen, and what the people who are sending and receiving the communication know.   But I don't see this made explicit anywhere, so the question seems ambiguous.  Do you have a particular interpretation?
Neal Young
CC BY-SA 4.0
2022-11-18T00:17:18.173Z
@Neal: Here's my interpretation. We're playing a game. There are three numbers, $\{1, 2, 3\}$. The referee gives me a subset of two of them (which we might as well assume is random). I then send you a message, and you send the referee one of the three numbers. We win if the number you send is one of the two numbers I received. The question is: how much information must I transmit (on average) so that we win every time.
Peter Shor 
CC BY-SA 4.0
2022-11-18T03:10:42.010Z
Okay so for you a strategy is a function $f$ from $\{S\subseteq [n] : |S| =s\}$ to $[n]$ such that $f(S)\in S$ for all inputs $S$, and the goal is to minimize the entropy of the r.v. $f(S)$ where $S$ is an input selected uniformly at random?  For $s=2$ surely one can show this has value $\sum_{i=1}^{n-1} (i/{n\choose 2}) \ln ({n\choose 2}/{i})$, as attained by taking, say, $f(S) = \min S$?  For any other (non-isomorphic) strategy there is a local improvement that can be made, because of the concavity of the entropy function (I think ?).
Neal Young
CC BY-SA 4.0
2022-11-18T12:09:36.367Z
@NealYoung: That's right. It seems to me like this is a reasonable interpretation of the question in the title. And I'm pretty sure your proof works.
Peter Shor 
CC BY-SA 4.0
2022-11-17T21:37:32.677Z
2022-11-17T21:48:31.880Z
2022-11-17T21:48:31.880Z
Peter Shor 
<p>It takes exactly <span class="math-container">$\log_2 n := \lg n$</span> bits of information to specify a number from <span class="math-container">$\{1,2,\ldots,n\}.$</span> Likewise, it takes <span class="math-container">$\lg{n\choose s}$</span> bits of information to specify a subset of <span class="math-container">$s$</span> out of the <span class="math-container">$n$</span> numbers. Suppose instead we wished to specify not all <span class="math-container">$s$</span> numbers, but merely any one of them. How much information would this take?</p>
<p>Let's formalize this as a two-player game <span class="math-container">$\mathcal{G}(n,s,k).$</span> The first player chooses a function <span class="math-container">$f$</span> and shows it. The second player chooses a subset <span class="math-container">$S\subset\{1,2,\ldots,n\}$</span> with <span class="math-container">$s$</span> elements and shows it. The first player chooses a number <span class="math-container">$m\in\{1,2,\ldots,k\}$</span>. If <span class="math-container">$f(m)\in S$</span>, the first player wins</p>
<p>Define <span class="math-container">$W(n,s)$</span> as the smallest <span class="math-container">$k$</span> such that the first player has a winning strategy. What is <span class="math-container">$W(n,s)$</span>, that is, how much information is needed to specify at least one of the <span class="math-container">$s$</span> elements? Note that <span class="math-container">$W(n,1)=n$</span> and <span class="math-container">$W(n,s)=W(n,n-s).$</span></p>
<p>A trivial upper bound is <span class="math-container">$W(n,s) \le n-s+1$</span>, by noting that least one of the first <span class="math-container">$n-s+1$</span> numbers must be among the <span class="math-container">$s$</span>.</p>
<p>For a lower bound, you could break the <span class="math-container">$n$</span> numbers into groups of <span class="math-container">$s$</span> and note that the second player could choose <span class="math-container">$S$</span> as any of the <span class="math-container">$\lfloor n/s\rfloor$</span> groups and hence <span class="math-container">$W(n,s) \ge \lfloor n/s\rfloor$</span> if the first player is to distinguish between them.</p>

CC BY-SA 4.0
2022-11-15T20:27:58.957Z
What do you mean by specifying "any one of them"?  It sounds like you are just asking how many bits it takes to specify any one number in $\{1,\ldots, n\}$, but you've already answered that question in your first sentence.
Neal Young
CC BY-SA 4.0
2022-11-15T20:31:11.190Z
@NealYoung For example, with s = 2, you are given two out of the n points and must find a way to identify one of them with the minimal number of bits. A very simple solution (giving the trivial upper bound I mentioned) would be to output the smaller of the two, taking lg (n-1) bits rather than the lg(n) bits needed to output any one number. But perhaps there is a more clever alternative?
Charles
CC BY-SA 4.0
2022-11-15T21:46:43.573Z
If "information" refers to max-entropy (lg of number of possibilities) then it's lg(n-s+1), because specifying (n-s) elements will not cover the case when the remaining s elements form a subset. However if you want Shannon entropy, with uniformly random subset S of size s, I think the smallest entropy of any e(S) in S would be around lg(n/s).
Wei Zhan
CC BY-SA 4.0
2022-11-15T23:27:54.157Z
I'm still confused about what you mean by "identify".  Given $s$ numbers (that we both already know, and presumably for which we already both know the order relation), the number of bits that are needed to identify the minimum is zero, isn't it?
Neal Young
CC BY-SA 4.0
2022-11-16T02:04:56.167Z
Maybe you mean the following game?  You choose a prefix-free set of $n$ binary codewords.  I then choose a subset of $s$ of those codewords.  You pay me the length of the smallest codeword among those $s$.  (Your goal is to minimize the payment, mine is to maximize it.)  If that's what you mean, your optimal solution is a prefix-free set of codewords that minimizes the length of the $s$th largest codeword.  I think the answer for that is easy to determine.  (I think it is exactly $\lceil \log_2 (n-s+1)\rceil$.)
Neal Young
CC BY-SA 4.0
2022-11-16T02:13:13.030Z
@NealYoung That's essentially the right interpretation, though the information doesn't need to be in whole bits -- if the most you need to communicate is one out of 5 states, I want to show that as $\lg5$ not $\lceil\lg5\rceil=3.$
Charles
CC BY-SA 4.0
2022-11-16T13:33:33.183Z
I think it would be helpful to have a precise (perhaps combinatorial?) definition of the quantity you are asking about.  You say "that's essentially the right interpretation", but per your comment it's not right, and I'm not sure how you would amend it to make it correct.
Neal Young
CC BY-SA 4.0
2022-11-16T14:06:29.187Z
@NealYoung Done.
Charles
CC BY-SA 4.0
2022-11-16T21:01:47.357Z
I'm confused. Assuming the second player knows $f$, the game as described is trivial.  The first player loses iff $S\subseteq [n] \setminus f([k])$, so the first player should choose any $f$ such that $|f([k])\cap [n]| = k$, and then the second player has a winning strategy iff $s \le n - k$.  That is, the first player wins iff $k \ge n - s + 1$.  So $W(n, s) = n - s + 1$.  Am I misunderstanding the game?  Also, what does this have to do with "information required to identify..." anything?
Neal Young
CC BY-SA 4.0
2022-11-17T04:53:02.273Z
I think I agree with Neal Young at the moment, "the first player wins iff $k \geq n−s+1$". By picking $f$, the first player specifies a subset of size $k$. The second player can avoid all members of that subset if and only if there are at least $s$ elements not in it. Maybe there is another interesting variant of the game that formalizes the intuition you want to capture here.
usul
CC BY-SA 4.0
2022-11-17T22:50:20.180Z
The question is ambiguous. If we take the question of the title ("How much information does it take ...") you get a different answer the log of $W$ as specified in your third paragraph. (See my answer.) Which question do you want to know the answer to?
Peter Shor 
<reference-request><co.combinatorics><it.information-theory><combinatorial-game-theory><two-player-games>
How much information does it take to specify, not each member of a group, but any one member?
Charles
# How much information does it take to specify, not each member of a group, but any one member?

(Asked by: username_0 on 2022-11-15)

It takes exactly $\log\_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ numbers. Suppose instead we wished to specify not all $s$ numbers, but merely any one of them. How much information would this take?

Let's formalize this as a two-player game $\mathcal{G}(n,s,k).$ The first player chooses a function $f$ and shows it. The second player chooses a subset $S\subset\{1,2,\ldots,n\}$ with $s$ elements and shows it. The first player chooses a number $m\in\{1,2,\ldots,k\}$. If $f(m)\in S$, the first player wins

Define $W(n,s)$ as the smallest $k$ such that the first player has a winning strategy. What is $W(n,s)$, that is, how much information is needed to specify at least one of the $s$ elements? Note that $W(n,1)=n$ and $W(n,s)=W(n,n-s).$

A trivial upper bound is $W(n,s) \le n-s+1$, by noting that least one of the first $n-s+1$ numbers must be among the $s$.

For a lower bound, you could break the $n$ numbers into groups of $s$ and note that the second player could choose $S$ as any of the $\lfloor n/s\rfloor$ groups and hence $W(n,s) \ge \lfloor n/s\rfloor$ if the first player is to distinguish between them.

**Tags:** reference-request, co.combinatorics, it.information-theory, combinatorial-game-theory, two-player-games
> **Comments:**
> **username_1**: What do you mean by specifying "any one of them"?  It sounds like you are just asking how many bits it takes to specify any one number in $\{1,\ldots, n\}$, but you've already answered that question in your first sentence.  
> **username_0**: @NealYoung For example, with s = 2, you are given two out of the n points and must find a way to identify one of them with the minimal number of bits. A very simple solution (giving the trivial upper bound I mentioned) would be to output the smaller of the two, taking lg (n-1) bits rather than the lg(n) bits needed to output any one number. But perhaps there is a more clever alternative?  
> **username_2**: If "information" refers to max-entropy (lg of number of possibilities) then it's lg(n-s+1), because specifying (n-s) elements will not cover the case when the remaining s elements form a subset. However if you want Shannon entropy, with uniformly random subset S of size s, I think the smallest entropy of any e(S) in S would be around lg(n/s).  
> **username_1**: I'm still confused about what you mean by "identify".  Given $s$ numbers (that we both already know, and presumably for which we already both know the order relation), the number of bits that are needed to identify the minimum is zero, isn't it?  
> **username_1**: Maybe you mean the following game?  You choose a prefix-free set of $n$ binary codewords.  I then choose a subset of $s$ of those codewords.  You pay me the length of the smallest codeword among those $s$.  (Your goal is to minimize the payment, mine is to maximize it.)  If that's what you mean, your optimal solution is a prefix-free set of codewords that minimizes the length of the $s$th largest codeword.  I think the answer for that is easy to determine.  (I think it is exactly $\lceil \log_2 (n-s+1)\rceil$.)  
> **username_0**: @NealYoung That's essentially the right interpretation, though the information doesn't need to be in whole bits -- if the most you need to communicate is one out of 5 states, I want to show that as $\lg5$ not $\lceil\lg5\rceil=3.$  
> **username_1**: I think it would be helpful to have a precise (perhaps combinatorial?) definition of the quantity you are asking about.  You say "that's essentially the right interpretation", but per your comment it's not right, and I'm not sure how you would amend it to make it correct.  
> **username_0**: @NealYoung Done.  
> **username_1**: I'm confused. Assuming the second player knows $f$, the game as described is trivial.  The first player loses iff $S\subseteq [n] \setminus f([k])$, so the first player should choose any $f$ such that $|f([k])\cap [n]| = k$, and then the second player has a winning strategy iff $s \le n - k$.  That is, the first player wins iff $k \ge n - s + 1$.  So $W(n, s) = n - s + 1$.  Am I misunderstanding the game?  Also, what does this have to do with "information required to identify..." anything?  
> **username_3**: I think I agree with Neal Young at the moment, "the first player wins iff $k \geq n−s+1$". By picking $f$, the first player specifies a subset of size $k$. The second player can avoid all members of that subset if and only if there are at least $s$ elements not in it. Maybe there is another interesting variant of the game that formalizes the intuition you want to capture here.  
> **username_4**: The question is ambiguous. If we take the question of the title ("How much information does it take ...") you get a different answer the log of $W$ as specified in your third paragraph. (See my answer.) Which question do you want to know the answer to?  

---

## 2 answers

### Answer by username_1 on 2022-11-18. Score: 4

This answer continues Peter's. It assumes Peter's interpretation of the problem and verifies that with that interpretation the function $f(S)=\min S$ is optimal, as Peter suggested. Here's the problem statement:

> *Fix integers $s\ge 1$ and $n\ge s$. Let $\mathcal S\_s = \{S\subseteq [n] : |S| = s\}$ contain the size-$s$ subsets of $[n]$. The goal is to determine the minimum, over all functions $f:\mathcal S\_s\to[n]$ such that $f(S)\in S$ for all $S\in\mathcal S\_s$, of the entropy of the distribution of the random variable $f(S)$ where $S$ is drawn uniformly at random from $\mathcal S\_s$.*

Before we begin, here's a formula for the entropy for an arbitrary $f$.
For $i\in [n]$ let $f^{-1}(i) = \{S\in \mathcal S\_s : f(S) = i\}$ contain the sets that $f$ maps to $i$. For the random choice of $S$ described above, for each $i$, the entropy of $f(S)$ is
$$\begin{align}
{} \sum\_{i=1}^n -\Pr[f(S) = i] \ln \Pr[f(S) = i]
& {} =\sum\_{i=1}^n -\frac{|f^{-1}(i)|}{n\choose s} \ln \frac{|f^{-1}(i)|}{n\choose s}
\\
& {} =\ln {n\choose s} - {n\choose s}^{-1}\sum\_{i=1}^n |f^{-1}(i)|\ln |f^{-1}(i)|.~~~~~~(1)
\end{align}
$$

Note that for the particular function $\hat f(S) = \min S$ we have $|\hat f^{-1}(i)| = {n-i\choose s-1}$ so for this $\hat f$ the entropy in question is
$$
\sum\_{j=s-1}^{n-1} \frac{j\choose s-1}{n\choose s} \ln \frac{n\choose s}{j\choose s-1}
=
\ln {n\choose s} - {n\choose s}^{-1}\sum\_{j=s}^{n-1} {j\choose s-1}\ln {j\choose s-1}.$$

For example, when $s=2$, the entropy is $\ln {n\choose 2} - {n\choose 2}^{-1}\displaystyle\sum\_{j=2}^{n-1} j \ln j = \ln(n/2)+1/2 \pm o(1)$.

When $s=2$ and $n=3$, the entropy is $\ln 3 - (2/3)\ln 2 = H(1/3)$.

**Lemma 1.** *The function $\hat f(S) = \min S$ is optimal.*

*Proof.*

1. Let $f$ be any optimal function.
2. By symmetry assume without loss of generality that $|f^{-1}(1)| \ge |f^{-1}(2)| \ge \cdots \ge |f^{-1}(n)|$.
3. Assume for contradiction that $f\not\equiv \hat f$.
4. Fix an $S'\in \mathcal S\_s$ such that $f(S') \ne \min S'$.
5. Let $m = \min S'$ and $p=f(S')$. Because $p\in S'\setminus\{m\}$ we have $p > m$.
6. Let $a = |f^{-1}(m)|$ and $b=|f^{-1}(p)|\ge 1$. By Steps 2 and 5 we have $a \ge b \ge 1$.
7. Consider modifying $f$ by changing $f(S')$ to $i$.
8. This changes $\sum\_{i=1}^n |f^{-1}(i)|\ln |f^{-1}(i)|$ by an additive
   $$[a \ln a + b\ln b] - [(a+1)\ln(a+1) + (b-1)\ln (b-1)].$$
9. Because $x \mapsto x\ln x$ is strictly convex and $a\ge b$, this change is strictly positive.
10. So, by Equation (1) before the lemma, this change decreases the entropy.
11. This contradicts the optimality of $f$. $~~~~~\Box$


---

### Answer by username_4 on 2022-11-17. Score: 2

This is a request for clarification and a partial answer, but I'm posting it as an answer because there is no way for it to fit in a comment.

Is the OP asking for how much information you need to send, or the smallest number of possibilities that you need to use in order to answer? These are two distinct questions. His definition of $W$ would point to the second question, but the title of his question points to the first,

Suppose you have three numbers, and we want to specify a number chosen from a subset of two of them. How much information do we need?

Let's use the following strategy: the two players choose a random seed, and generate a pseudorandom permutation of the three numbers each time. The second player sends the first player "$1$" if the first element of the permutation is in the subset, and "$2$" otherwise.

The player is then sending "$1$" two-thirds of the time, and "$2$" one-third of the time. The amount of information needed for this is
$$H\left(\frac{1}{3}\right) = -\frac{1}{3} \log\_2 \frac{1}{3} -\frac{2}{3} \log\_2 \frac{2}{3} = .9183 \mathrm{\ bits},$$
which is less than the log of the number $W$ of distinct responses you need to send (namely $1 = \log\_2 2$).

I believe this is the optimal strategy for accomplishing this task, although since I don't have a proof, I might easily be wrong.

This strategy is generalizable to a subset of $k$ chosen from a set of $n$, although it may take some work to give a nice formula for how much information is needed.

> **Comments:**
> **username_1**: Peter, can you clarify something I'm confused about?  Namely, what exactly does it mean to "specify a number chosen from a subset of two of them"?  There must be some underlying assumptions about how the subset and number are chosen, and what the people who are sending and receiving the communication know.   But I don't see this made explicit anywhere, so the question seems ambiguous.  Do you have a particular interpretation?  
> **username_4**: @Neal: Here's my interpretation. We're playing a game. There are three numbers, $\{1, 2, 3\}$. The referee gives me a subset of two of them (which we might as well assume is random). I then send you a message, and you send the referee one of the three numbers. We win if the number you send is one of the two numbers I received. The question is: how much information must I transmit (on average) so that we win every time.  
> **username_1**: Okay so for you a strategy is a function $f$ from $\{S\subseteq [n] : |S| =s\}$ to $[n]$ such that $f(S)\in S$ for all inputs $S$, and the goal is to minimize the entropy of the r.v. $f(S)$ where $S$ is an input selected uniformly at random?  For $s=2$ surely one can show this has value $\sum_{i=1}^{n-1} (i/{n\choose 2}) \ln ({n\choose 2}/{i})$, as attained by taking, say, $f(S) = \min S$?  For any other (non-isomorphic) strategy there is a local improvement that can be made, because of the concavity of the entropy function (I think ?).  
> **username_4**: @NealYoung: That's right. It seems to me like this is a reasonable interpretation of the question in the title. And I'm pretty sure your proof works.  

---

