Guess my number! Pay for the answer!

Question

Alice and Bob play the following number guessing game.

• In the beginning, Alice picks a secret number from the range $1,2,3,\ldots,144$.

• Then Bob is allowed to ask a sequence of questions. In every question, Bob chooses some subset from the range $1,2,3,\ldots,144$ and asks Alice whether her secret number lies in this subset.

• Alice answers Bob's question truthfully. If her answer is YES, then Bob must pay 2 Euro to Alice. If her answer is NO, then Bob must pay 1 Euro to Alice.

• The game ends, once Bob chooses a one-element subset to which Alice answers YES.
  Bob then receives $x$ Euro from Alice.

How should the value $x$ be chosen, so that these rules do yield a fair game? (As usual, we assume that Alice and Bob both use optimal strategies in their play.)

Answer 1

The answer is that only x=11 yields a fair game.

I solved this using a recurrence. Let $f[N]$ be optimal expected amount of money that Bob has to pay Alice to find the best answer. Clearly, $f[1] = 2$ since he can ask a single question.

Now we can find a recurrence for $N$. Bob can choose to ask for a subset of size $i$. Since Alice is not cheating, with probability $i/N$, he receives the answer yes. So the expected value Bob has to pay in total including that for the current question is $$\frac{i*(2+f[i])+(N-i)*(1+f[N-i])}{N}$$ (The first $f[i]$ should be avoided when $i=1$). Minimising this quantity over all values of $1<=i<=N-1$ gives the optimum strategy for Bob. That is, $$f[N]=min_i \frac{i*(2+f[i])+(N-i)*(1+f[N-i])}{N}$$

Building this recurrence bottom up gives $f[144]=11$. For the game to be fair, Alice should pay 11 euros back to Bob.

Answer 2

I think crazyiman has it right, but I just wanted to add a bit that is too much to fit in a comment. So feel free to upvote this answer, but also upvote his.

Lets say that you have 2 numbers left. If you guess one and are right, you are done, but if you are wrong, you still need to guess the other number.

So lets define two recurrence relations, $f_r(N)$ and $f_w(N)$. $f_r(N)$ is the expected value your previous guess was right for the set $N$, and $f_w(N)$ is the expected value if your previous guess was wrong leaving you with set $N$.

Notice that these relations only differ when you are talking about sets with single elements because if you guessed right on a single number you are done, but if you guessed wrong and are left with a single number, you must still guess it.

Thus we know the following:

$$f_r(1)=0$$ $$f_w(1)=2$$ $$f(n)=f_r(i)=f_w(i), \forall i \mid i>1$$

So, for $i>1$, we know the following from @craziman:

$$f(n)=\frac{i∗(2+f_r(i))+(n−i)∗(1+f_w(n−i))}{n}$$

And again, just to show the work, we will work up from 1. The whole number results are indeed the Fibonacci sequence. For eacn $n$, the best choice for $i$ is also recorded.

f(002)=02.500, i=1
f(003)=03.000, i=1   <-- Fibonacci
f(004)=03.500, i=1
f(005)=04.000, i=1   <-- Fibonacci
f(006)=04.500, i=1     f(007)=04.714, i=3
f(008)=05.000, i=3   <-- Fibonacci
f(009)=05.222, i=4     f(010)=05.500, i=3     f(011)=05.636, i=4
f(012)=05.833, i=4
f(013)=06.000, i=4   <-- Fibonacci
f(014)=06.143, i=5     f(015)=06.333, i=4     f(016)=06.438, i=5
f(017)=06.588, i=5     f(018)=06.667, i=7     f(019)=06.789, i=7
f(020)=06.900, i=7
f(021)=07.000, i=7   <-- Fibonacci
f(022)=07.091, i=8     f(023)=07.174, i=9     f(024)=07.292, i=8
f(025)=07.360, i=9     f(026)=07.462, i=8     f(027)=07.519, i=9
f(028)=07.607, i=9     f(029)=07.655, i=11    f(030)=07.733, i=11
f(031)=07.806, i=11    f(032)=07.875, i=11    f(033)=07.939, i=11
f(034)=08.000, i=11  <-- Fibonacci
f(035)=08.057, i=12    f(036)=08.111, i=13    f(037)=08.162, i=14
f(038)=08.237, i=14    f(039)=08.282, i=14    f(040)=08.350, i=13
f(041)=08.390, i=14    f(042)=08.452, i=18    f(043)=08.488, i=14
f(044)=08.545, i=14    f(045)=08.578, i=16    f(046)=08.630, i=16
f(047)=08.660, i=18    f(048)=08.708, i=18    f(049)=08.755, i=18
f(050)=08.800, i=18    f(051)=08.843, i=18    f(052)=08.885, i=18
f(053)=08.925, i=18    f(054)=08.963, i=18
f(055)=09.000, i=18  <-- Fibonacci
f(056)=09.036, i=19    f(057)=09.070, i=20    f(058)=09.103, i=21
f(059)=09.136, i=22    f(060)=09.167, i=23    f(061)=09.213, i=22
f(062)=09.242, i=23    f(063)=09.286, i=22    f(064)=09.312, i=23
f(065)=09.354, i=22    f(066)=09.379, i=23    f(067)=09.418, i=22
f(068)=09.441, i=23    f(069)=09.478, i=22    f(070)=09.500, i=23
f(071)=09.535, i=23    f(072)=09.556, i=25    f(073)=09.589, i=25
f(074)=09.608, i=27    f(075)=09.640, i=27    f(076)=09.658, i=29
f(077)=09.688, i=29    f(078)=09.718, i=29    f(079)=09.747, i=29
f(080)=09.775, i=29    f(081)=09.802, i=29    f(082)=09.829, i=29
f(083)=09.855, i=29    f(084)=09.881, i=29    f(085)=09.906, i=29
f(086)=09.930, i=29    f(087)=09.954, i=29    f(088)=09.977, i=29
f(089)=10.000, i=29  <-- Fibonacci
f(090)=10.022, i=30    f(091)=10.044, i=31    f(092)=10.065, i=32
f(093)=10.086, i=33    f(094)=10.106, i=34    f(095)=10.126, i=35
f(096)=10.146, i=36    f(097)=10.165, i=37    f(098)=10.194, i=36
f(099)=10.212, i=37    f(100)=10.240, i=36    f(101)=10.257, i=37
f(102)=10.284, i=36    f(103)=10.301, i=37    f(104)=10.327, i=36
f(105)=10.343, i=37    f(106)=10.368, i=36    f(107)=10.383, i=37
f(108)=10.407, i=36    f(109)=10.422, i=37    f(110)=10.445, i=36
f(111)=10.459, i=37    f(112)=10.482, i=36    f(113)=10.496, i=37
f(114)=10.518, i=37    f(115)=10.530, i=39    f(116)=10.552, i=39
f(117)=10.564, i=41    f(118)=10.585, i=41    f(119)=10.597, i=43
f(120)=10.617, i=43    f(121)=10.628, i=45    f(122)=10.648, i=45
f(123)=10.659, i=47    f(124)=10.677, i=47    f(125)=10.696, i=47
f(126)=10.714, i=47    f(127)=10.732, i=47    f(128)=10.750, i=47
f(129)=10.767, i=47    f(130)=10.785, i=47    f(131)=10.802, i=47
f(132)=10.818, i=47    f(133)=10.835, i=47    f(134)=10.851, i=47
f(135)=10.867, i=47    f(136)=10.882, i=47    f(137)=10.898, i=47
f(138)=10.913, i=47    f(139)=10.928, i=47    f(140)=10.943, i=47
f(141)=10.957, i=47    f(142)=10.972, i=47    f(143)=10.986, i=47
f(144)=11.000, i=47  <-- Fibonacci

Answer 3

Following on Crazyman's answer: it appears that if $N = F_n$ is the $n^{th}$ Fibonacci number, then following the optimal strategy, the expected value is $f[F_n] = n-1$ for all $n \geq 4$. Given $N = F_n$ for some $n\geq 4$, a concrete strategy that achieves this expectation is to ask: "Is the desired number less than or equal to $F_{n-2}$?"

Proof: by induction. This strategy gives expectation $4-1 = 3$ for $N = F_4 = 3$, and $5-1 = 4$ for $N = F_5 = 5$, as may be verified by hand.

Now assume that the expectation using this strategy satisfies $f[F_{n-2}] = n-3$, and $f[F_{n-1}] = n-2$, and consider what happens when we apply this strategy to $N = F_n$. With probability $F_{n-2} / F_n$, the answer will be yes, we'll have to pay $2$ Euro, and we'll have narrowed the possibilities down to a set of size $F_{n-2}$. On the other hand, with probability $(F_n - F_{n-2})/F_n = F_{n-1} / F_n$, the answer will be no, in which case we pay $1$ Euro and we have it narrowed down to a set of size $F_{n-1}$. Thus our expected payout is: $$ f[F_n] = \frac{F_{n-2}(2 + f[F_{n-2}]) + F_{n-1}(1 + f[F_{n-1}])}{F_n} $$ By the induction hypothesis, $f[F_{n-2}] = (n-2) -1$, and $f[F_{n-1}] = (n-1) - 1$, which means that the above formula simplifies: $$ f[F_n] = \frac{F_{n-2}(2 + n-3) + F_{n-1}(1 + n-2)}{F_n} = \frac{(F_{n-2} + F_{n-1})(n-1)}{F_n} = n-1, $$ proving the induction step.

This does not explain why this strategy is optimal, but it does at least demonstrate an explicit strategy that would give $f[144] = 11$.

Edit:

At every point during the game, Bob's strategy is to split a set of $N$ elements into two smaller sets. Then based on Alice's answer, Bob knows which of these two sets includes Alice's number. Let's say $A$ and $B$ are the sizes of these two sets.

In this game, two "no" answers cost the same as one "yes" answer, so intuitively they should yield the same amount of information. Let's let $r$ be the percentage (or proportion) of the $N$ values that lie in the set of size $A$ (so in other words, $r = A/N$). Then $1-r$ is the proportion of the $N$ values that lie in the other set, so $B/N = 1-r$.

If we use the same proportion $r$ each time, then two "no" answers will leave us with $r^2N$ values left, while one "yes" answer will leave us with $(1-r)N$ values left. Since they cost the same, they should yield the same amount of information. That is, we should have $$ r^2 = 1- r $$ Solving this for $r$, we see that $r = 1/ \phi$ where $\phi$ is the Golden Ratio. If $N = F_n$ is a Fibonacci number, then $(1/ \phi)F_n$ is very close to $F_{n-1}$, which starts to explain why this solution makes sense if $N$ is a Fibonacci number.

Perhaps the optimal solution is always to split $N$ into two numbers that are as close as possible to $(1/ \phi)N$ and $(1 - 1/\phi ) N$, in which case it just so happens that with Fibonacci numbers you'll always split it into the next two smaller Fibonacci numbers.

http://en.wikipedia.org/wiki/Golden_ratio

Answer 4

Starting with an assumption that the binary search algorithm might be the optimal way to do this, even though half of the answers would cost 2 Euro, and the other half 1 Euro, I brute-forced the question. Each round Bob asks if the answer is between "middle" and "top".

The average cost for an answer is 10.6875 Euro, meaning that Alice should give Bob 10.6875 Euro and things will average out to be even.

However, I then tested what would happen if we used a weighted value as the center value, instead of just using the number midway between high and low. When I examined the weighted results, I found that a factor of .375 resulted in the lowest average cost at 10.4028 Euros.

I have included my code below.

public void BinSearch()
{
    Debug.Print("Binary Search = " + GetSearchResult(null).ToString());
    Debug.Print("Binary Offset Search = " + GetSearchResult((a, b) => Convert.ToInt32((b - a) * .375 + a)).ToString());

    nums.ForEach(v =>
        {
            var offset = v / 144m;
            Debug.Print("Offset by " + v.ToString() + " = " + GetSearchResult((a, b) => Convert.ToInt32((b - a) * offset + a)).ToString());
        });
}

private List<int> nums = Enumerable.Range(1, 144).ToList();

// return the average price to find a value with this formula
public double GetSearchResult(Func<int, int, int> formula)
{
    var costs = new Dictionary<int, int>();

    foreach (var num in nums)
    {
        var result = BinarySearch(nums, num, formula);
        costs.Add(num, result);
    }

    return costs.Select(v => v.Value).Average();
}

// return the price to find value using formula
public static int BinarySearch(List<int> arrayList, int value, Func<int, int, int> formula)
{
    formula = formula ?? ((low, high) => (low + high) / 2);

    int lo = 0;
    int hi = arrayList.Count - 1;
    int price = 0;

    while (lo <= hi)
    {
        price++;

        int i = formula(lo, hi);
        int c = arrayList[i].CompareTo(value);

        if (c == 0 && lo == hi) return price + 1;

        if (c < 0)
        {
            lo = i + 1;
        }
        else
        {
            price++;
            hi = i - 1;
        }
    }

    return price;
}

Alice should give Bob 10.4028 Euros.

Answer 5

This is a partial answer showing the intuitive fact, which is used in other answers but not mentioned explicitly, that there is a Nash equilibrium where Alice's strategy is the uniform distribution. Thus the question reduces to finding Bob's optimal strategy against the uniform distribution.

If distribution $X$ is Alice's strategy in a Nash equilibrium with payoff $a$ to Alice, then, because the game is the same if the numbers are permuted, so are all distributions $X_1,\dots,X_{144!}$ obtained from $X$ by all permutations of the numbers. Let Alice choose a strategy uniformly from those strategies, giving a uniform distribution. Let Bob's optimal strategy against that be $S$. Now Alice's payoff is $$ \sum_{i=1}^{144!} \frac{1}{144!} f(X_i,S), $$ where $f(X,Y)$ is Alice's payoff when the players have strategies $X$ and $Y$. Alice's payoff can't be worse than $$ \min_i f(X_i,S), $$ that is, the payoff she would get by choosing the worst possible of the strategies $X_i$ to counter $S$. But because each $X_i$ is a strategy in a Nash equilibrium with payoff $a$, we know that $f(X_i,S)\geq a$ no matter what $S$ is.

Therefore, Alice gets at least payoff $a$ if she uses the uniform distribution. Since this is at least as large as the payoff in a Nash equilibrium, the uniform distribution has to be one of the optimal strategies.

Answer 6

[TL/DR Answer is 11]

Considering the optimum cost:

• For, the base case, a set of magnitude $1$ then the cost is $C_1 =2$
• For a set $X$ (of size $x$) then this can be split into sub-sets $Y$ (of size $y$) and $X\backslash Y$ then
  • $X\backslash Y$ has size $z=x-y$;
  • The probability $P_{y}$ of the answer being in $Y$ is $\frac{y}{x}$;
  • The probability $P_{z}$ of the answer being in $X\backslash Y$ is $\frac{x-y}{x}$;
  • The cost $C_{(x,y)}$ for this combination of set and sub-set sizes is given by: $\begin{split} C_{(x,y)} & = \begin{cases} P_{y} \cdot 2 + P_{z} \cdot (1+C_{z}) & \text{if } y=1\\ P_{y} \cdot (2+C_{y}) + P_{z} \cdot (1+C_{z}) & \text{if } y>1\end{cases} \\ &= \begin{cases} \frac{2 + (x-1) \cdot (1+C_{z})}{x} & \text{if } y=1\\ \frac{y \cdot (2+C_{y}) + (x-y) \cdot (1+C_{z})}{x} & \text{if } y>1\end{cases} \end{split}$
  • The optimum cost $C_x = \text{min} \left( \forall_{y=1 \ldots \lfloor \frac{x}{2} \rfloor } C_{(x,y)} \right)$

This can then be used iteratively to generate costs for successively increasing sized sets.

The following Java code does this:

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;

public class Coins {

    static final int SIZE = 200;
    static final BigDecimal TWO = new BigDecimal( "2" );

    public static void main(String[] args) {
        final ArrayList<BigDecimal> costs = new ArrayList<BigDecimal>( SIZE + 1 );
        final ArrayList<Integer> values   = new ArrayList<Integer>();

        costs.add( BigDecimal.ZERO );
        costs.add( TWO );

        for ( int size = 2; size <= SIZE; ++size )
        {
            costs.add( new BigDecimal( SIZE ) );
            values.clear();
            BigDecimal setSize = new BigDecimal( size );
            for ( int firstSubSetSize = 1; firstSubSetSize <= size / 2; ++firstSubSetSize )
            {
                int secondSubSetSize = size - firstSubSetSize;
                BigDecimal setSize1 = new BigDecimal( firstSubSetSize );
                BigDecimal setSize2 = new BigDecimal( secondSubSetSize );
                BigDecimal cost1 = firstSubSetSize == 1 ? TWO : TWO.add( costs.get( firstSubSetSize ) );
                BigDecimal cost2 = BigDecimal.ONE.add( costs.get( secondSubSetSize ) );
                BigDecimal cost = cost1.multiply( setSize1 ).add( cost2.multiply( setSize2 ) ).setScale( 50, RoundingMode.HALF_UP ).divide( setSize, RoundingMode.HALF_UP );
                if ( costs.get( size ) == null )
                {
                    costs.set( size, cost );
                    values.add( firstSubSetSize );
                }
                else
                {
                    switch( cost.compareTo( costs.get( size ) ) )
                    {
                    case -1: values.clear();
                    case 0:  values.add( firstSubSetSize );
                             costs.set( size, cost );
                             break;
                    default: break;
                    }
                }
            }
            System.out.println( size + " : " + costs.get( size ).toPlainString() + " : " + values.toString() );
        }
    }
}

And gives the output (first column is the starting set size, second column is the optimum cost and third column is the list of sub-set sizes which Bob can pick that will give that optimum cost):

2 : 2.50000000000000000000000000000000000000000000000000 : [1]
3 : 3.00000000000000000000000000000000000000000000000000 : [1]
4 : 3.50000000000000000000000000000000000000000000000000 : [1]
5 : 4.00000000000000000000000000000000000000000000000000 : [1]
6 : 4.50000000000000000000000000000000000000000000000000 : [1, 2, 3]
7 : 4.71428571428571428571428571428571428571428571428571 : [3]
8 : 5.00000000000000000000000000000000000000000000000000 : [3, 4]
9 : 5.22222222222222222222222222222222222222222222222222 : [4]
10 : 5.50000000000000000000000000000000000000000000000000 : [3, 4, 5]
11 : 5.63636363636363636363636363636363636363636363636363 : [4]
12 : 5.83333333333333333333333333333333333333333333333333 : [4, 5]
13 : 6.00000000000000000000000000000000000000000000000000 : [4, 5]
14 : 6.14285714285714285714285714285714285714285714285714 : [5]
15 : 6.33333333333333333333333333333333333333333333333333 : [4, 5, 6, 7]
16 : 6.43750000000000000000000000000000000000000000000000 : [5, 7]
17 : 6.58823529411764705882352941176470588235294117647058 : [6]
18 : 6.66666666666666666666666666666666666666666666666666 : [7]
19 : 6.78947368421052631578947368421052631578947368421052 : [7, 8]
20 : 6.90000000000000000000000000000000000000000000000000 : [7, 8, 9]
21 : 7.00000000000000000000000000000000000000000000000000 : [7, 8, 9]
22 : 7.09090909090909090909090909090909090909090909090909 : [8, 9]
23 : 7.17391304347826086956521739130434782608695652173913 : [9]
24 : 7.29166666666666666666666666666666666666666666666666 : [9, 11]
25 : 7.36000000000000000000000000000000000000000000000000 : [9, 11]
26 : 7.46153846153846153846153846153846153846153846153846 : [8, 9, 10, 11, 12]
27 : 7.51851851851851851851851851851851851851851851851851 : [9]
28 : 7.60714285714285714285714285714285714285714285714285 : [9, 10, 11]
29 : 7.65517241379310344827586206896551724137931034482758 : [11]
30 : 7.73333333333333333333333333333333333333333333333333 : [11, 12]
31 : 7.80645161290322580645161290322580645161290322580645 : [11, 12, 13]
32 : 7.87500000000000000000000000000000000000000000000000 : [11, 12, 13, 14]
33 : 7.93939393939393939393939393939393939393939393939393 : [14]
34 : 8.00000000000000000000000000000000000000000000000000 : [11, 12, 13, 14]
35 : 8.05714285714285714285714285714285714285714285714286 : [12, 13, 14]
36 : 8.11111111111111111111111111111111111111111111111111 : [13, 14]
37 : 8.16216216216216216216216216216216216216216216216216 : [14]
38 : 8.23684210526315789473684210526315789473684210526315 : [14]
39 : 8.28205128205128205128205128205128205128205128205128 : [14, 16]
40 : 8.34999999999999999999999999999999999999999999999999 : [13]
41 : 8.39024390243902439024390243902439024390243902439024 : [14, 16, 18]
42 : 8.45238095238095238095238095238095238095238095238095 : [13, 14, 15, 16, 17, 18, 19]
43 : 8.48837209302325581395348837209302325581395348837209 : [14, 16, 18]
44 : 8.54545454545454545454545454545454545454545454545454 : [14, 15, 16, 17, 18, 19]
45 : 8.57777777777777777777777777777777777777777777777777 : [16, 18]
46 : 8.63043478260869565217391304347826086956521739130434 : [17, 18, 19]
47 : 8.65957446808510638297872340425531914893617021276595 : [18]
48 : 8.70833333333333333333333333333333333333333333333333 : [18, 19]
49 : 8.75510204081632653061224489795918367346938775510204 : [18, 19, 20]
50 : 8.80000000000000000000000000000000000000000000000000 : [18, 19, 20, 21]
51 : 8.84313725490196078431372549019607843137254901960783 : [18]
52 : 8.88461538461538461538461538461538461538461538461538 : [18, 19, 20, 21, 22, 23]
53 : 8.92452830188679245283018867924528301886792452830188 : [19, 20, 23]
54 : 8.96296296296296296296296296296296296296296296296296 : [18, 19, 20, 21, 22, 23]
55 : 8.99999999999999999999999999999999999999999999999999 : [22]
56 : 9.03571428571428571428571428571428571428571428571428 : [19, 23]
57 : 9.07017543859649122807017543859649122807017543859649 : [20, 21, 22, 23]
58 : 9.10344827586206896551724137931034482758620689655172 : [21, 22]
59 : 9.13559322033898305084745762711864406779661016949152 : [22, 23]
60 : 9.16666666666666666666666666666666666666666666666667 : [23]
61 : 9.21311475409836065573770491803278688524590163934426 : [22, 23, 24, 25]
62 : 9.24193548387096774193548387096774193548387096774193 : [23, 25]
63 : 9.28571428571428571428571428571428571428571428571428 : [22, 23, 24, 25, 26, 27]
64 : 9.31250000000000000000000000000000000000000000000000 : [23, 25, 27]
65 : 9.35384615384615384615384615384615384615384615384615 : [22, 23, 24, 25, 26, 27, 28, 29]
66 : 9.37878787878787878787878787878787878787878787878787 : [27, 29]
67 : 9.41791044776119402985074626865671641791044776119402 : [22, 27, 29]
68 : 9.44117647058823529411764705882352941176470588235294 : [23, 25, 27, 29]
69 : 9.47826086956521739130434782608695652173913043478260 : [22, 23, 24, 27, 28, 29]
70 : 9.49999999999999999999999999999999999999999999999999 : [23, 27]
71 : 9.53521126760563380281690140845070422535211267605633 : [24, 25, 26, 27, 28, 29, 30]
72 : 9.55555555555555555555555555555555555555555555555555 : [25, 27, 29]
73 : 9.58904109589041095890410958904109589041095890410958 : [26, 27, 28, 29]
74 : 9.60810810810810810810810810810810810810810810810810 : [27, 29]
75 : 9.63999999999999999999999999999999999999999999999999 : [27, 28, 29, 30]
76 : 9.65789473684210526315789473684210526315789473684210 : [29]
77 : 9.68831168831168831168831168831168831168831168831168 : [29, 30]
78 : 9.71794871794871794871794871794871794871794871794871 : [30, 31]
79 : 9.74683544303797468354430379746835443037974683544303 : [32]
80 : 9.77499999999999999999999999999999999999999999999999 : [29, 33]
81 : 9.80246913580246913580246913580246913580246913580246 : [29, 30, 33, 34]
82 : 9.82926829268292682926829268292682926829268292682926 : [29, 30, 31, 33]
83 : 9.85542168674698795180722891566265060240963855421686 : [29, 30, 31, 32, 33, 36]
84 : 9.88095238095238095238095238095238095238095238095237 : [29, 33]
85 : 9.90588235294117647058823529411764705882352941176470 : [29, 30, 31, 32, 33, 34, 36, 37]
86 : 9.93023255813953488372093023255813953488372093023255 : [30, 31, 33, 35]
87 : 9.95402298850574712643678160919540229885057471264367 : [29, 31, 32, 33, 34, 36]
88 : 9.97727272727272727272727272727272727272727272727272 : [29, 30, 32, 33, 35, 36, 37]
89 : 9.99999999999999999999999999999999999999999999999999 : [33, 34]
90 : 10.02222222222222222222222222222222222222222222222222 : [30, 31, 32, 33, 34, 35, 36, 37]
91 : 10.04395604395604395604395604395604395604395604395604 : [32, 33, 34, 35, 36, 37]
92 : 10.06521739130434782608695652173913043478260869565217 : [33, 34, 35, 36, 37]
93 : 10.08602150537634408602150537634408602150537634408602 : [33, 34, 35, 36, 37]
94 : 10.10638297872340425531914893617021276595744680851064 : [34, 35, 36, 37]
95 : 10.12631578947368421052631578947368421052631578947368 : [36, 37]
96 : 10.14583333333333333333333333333333333333333333333333 : [37]
97 : 10.16494845360824742268041237113402061855670103092784 : [37]
98 : 10.19387755102040816326530612244897959183673469387755 : [36, 37, 38, 39]
99 : 10.21212121212121212121212121212121212121212121212121 : [37, 39]
100 : 10.23999999999999999999999999999999999999999999999999 : [38]
101 : 10.25742574257425742574257425742574257425742574257425 : [39]
102 : 10.28431372549019607843137254901960784313725490196078 : [36, 37, 38, 39, 40, 41, 43]
103 : 10.30097087378640776699029126213592233009708737864077 : [37, 41]
104 : 10.32692307692307692307692307692307692307692307692307 : [37, 38, 39, 40, 41, 42, 43, 45]
105 : 10.34285714285714285714285714285714285714285714285714 : [37, 39, 41, 43, 45]
106 : 10.36792452830188679245283018867924528301886792452829 : [36, 39, 40]
107 : 10.38317757009345794392523364485981308411214953271027 : [37, 41, 45]
108 : 10.40740740740740740740740740740740740740740740740740 : [36, 37, 38, 39, 40, 41, 42, 43, 45, 46, 47]
109 : 10.42201834862385321100917431192660550458715596330275 : [37, 39, 41, 43, 45, 47]
110 : 10.44545454545454545454545454545454545454545454545454 : [36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48]
111 : 10.45945945945945945945945945945945945945945945945945 : [37, 41, 45]
112 : 10.48214285714285714285714285714285714285714285714285 : [36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47]
113 : 10.49557522123893805309734513274336283185840707964601 : [37, 39, 41, 43, 45, 47]
114 : 10.51754385964912280701754385964912280701754385964911 : [40, 44, 45, 47]
115 : 10.53043478260869565217391304347826086956521739130434 : [39, 41, 43, 45, 47]
116 : 10.55172413793103448275862068965517241379310344827585 : [41, 45, 46, 47]
117 : 10.56410256410256410256410256410256410256410256410256 : [41, 43, 45, 47]
118 : 10.58474576271186440677966101694915254237288135593219 : [45]
119 : 10.59663865546218487394957983193277310924369747899159 : [43, 45, 47]
120 : 10.61666666666666666666666666666666666666666666666666 : [43, 44, 45, 46, 47, 48]
121 : 10.62809917355371900826446280991735537190082644628098 : [47]
122 : 10.64754098360655737704918032786885245901639344262294 : [45, 46, 47, 48]
123 : 10.65853658536585365853658536585365853658536585365853 : [47]
124 : 10.67741935483870967741935483870967741935483870967741 : [47, 48]
125 : 10.69599999999999999999999999999999999999999999999999 : [47, 48]
126 : 10.71428571428571428571428571428571428571428571428571 : [47, 48, 49, 50]
127 : 10.73228346456692913385826771653543307086614173228346 : [47, 48, 49, 50, 51]
128 : 10.74999999999999999999999999999999999999999999999999 : [47, 48, 49, 51]
129 : 10.76744186046511627906976744186046511627906976744185 : [47, 48, 49, 51, 52, 53]
130 : 10.78461538461538461538461538461538461538461538461537 : [51]
131 : 10.80152671755725190839694656488549618320610687022900 : [47, 48, 49, 50, 51, 52, 53, 54, 55]
132 : 10.81818181818181818181818181818181818181818181818181 : [47, 48, 49, 50, 51, 52, 53, 54, 55, 56]
133 : 10.83458646616541353383458646616541353383458646616540 : [51, 53, 55]
134 : 10.85074626865671641791044776119402985074626865671641 : [47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58]
135 : 10.86666666666666666666666666666666666666666666666665 : [51]
136 : 10.88235294117647058823529411764705882352941176470587 : [47, 51, 52, 55, 56]
137 : 10.89781021897810218978102189781021897810218978102189 : [47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
138 : 10.91304347826086956521739130434782608695652173913042 : [51]
139 : 10.92805755395683453237410071942446043165467625899280 : [47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
140 : 10.94285714285714285714285714285714285714285714285713 : [51, 56]
141 : 10.95744680851063829787234042553191489361702127659574 : [47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
142 : 10.97183098591549295774647887323943661971830985915492 : [47, 51, 53, 54, 55, 56, 58, 59]
143 : 10.98601398601398601398601398601398601398601398601398 : [47, 48, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
144 : 10.99999999999999999999999999999999999999999999999999 : [51, 55, 56, 57, 58, 59]
145 : 11.01379310344827586206896551724137931034482758620689 : [49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
146 : 11.02739726027397260273972602739726027397260273972602 : [51, 53, 54, 55, 56, 57, 58, 59, 60]
147 : 11.04081632653061224489795918367346938775510204081632 : [51, 52, 54, 55, 56, 57, 58, 59, 60]
148 : 11.05405405405405405405405405405405405405405405405405 : [51, 52, 53, 54, 55, 56, 57, 58, 59, 60]
149 : 11.06711409395973154362416107382550335570469798657718 : [52, 53, 54, 55, 56, 57, 58, 59, 60]
150 : 11.07999999999999999999999999999999999999999999999999 : [55]
151 : 11.09271523178807947019867549668874172185430463576158 : [55, 56, 59]
152 : 11.10526315789473684210526315789473684210526315789473 : [56, 57, 59]
153 : 11.11764705882352941176470588235294117647058823529411 : [58]
154 : 11.12987012987012987012987012987012987012987012987013 : [57, 58, 59, 60]
155 : 11.14193548387096774193548387096774193548387096774193 : [59, 60]
156 : 11.15384615384615384615384615384615384615384615384615 : [59, 60]
157 : 11.16560509554140127388535031847133757961783439490446 : [60]
158 : 11.18354430379746835443037974683544303797468354430379 : [59, 62]
159 : 11.19496855345911949685534591194968553459119496855346 : [60, 62]
160 : 11.21249999999999999999999999999999999999999999999999 : [59]
161 : 11.22360248447204968944099378881987577639751552795031 : [60, 62, 64]
162 : 11.24074074074074074074074074074074074074074074074073 : [59, 62]
163 : 11.25153374233128834355828220858895705521472392638036 : [62]
164 : 11.26829268292682926829268292682926829268292682926829 : [59, 60, 61, 62, 63, 64, 65, 66, 67, 68]
165 : 11.27878787878787878787878787878787878787878787878787 : [62, 64, 66]
166 : 11.29518072289156626506024096385542168674698795180722 : [59, 60, 62, 63, 65, 66, 67, 70]
167 : 11.30538922155688622754491017964071856287425149700598 : [60, 62, 64, 66]
168 : 11.32142857142857142857142857142857142857142857142856 : [61, 62, 67]
169 : 11.33136094674556213017751479289940828402366863905325 : [60, 62, 64, 66, 68, 70, 72]
170 : 11.34705882352941176470588235294117647058823529411764 : [59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74]
171 : 11.35672514619883040935672514619883040935672514619882 : [64, 70]
172 : 11.37209302325581395348837209302325581395348837209301 : [66]
173 : 11.38150289017341040462427745664739884393063583815028 : [62, 66, 70, 72, 74]
174 : 11.39655172413793103448275862068965517241379310344827 : [59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77]
175 : 11.40571428571428571428571428571428571428571428571428 : [60, 62, 64, 66, 68, 70, 72, 74, 76]
176 : 11.42045454545454545454545454545454545454545454545453 : [70]
177 : 11.42937853107344632768361581920903954802259887005649 : [62, 64, 66, 70, 72, 74, 76]
178 : 11.44382022471910112359550561797752808988764044943819 : [60, 62, 64, 66, 67, 70, 71, 72, 74, 75, 77]
179 : 11.45251396648044692737430167597765363128491620111731 : [62, 64, 66, 68, 70, 72, 74, 76]
180 : 11.46666666666666666666666666666666666666666666666666 : [59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77]
181 : 11.47513812154696132596685082872928176795580110497237 : [60, 62, 64, 66, 68, 70, 72, 74, 76]
182 : 11.48901098901098901098901098901098901098901098901098 : [59, 60, 61, 62, 63, 64, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77]
183 : 11.49726775956284153005464480874316939890710382513660 : [62, 70, 72, 76]
184 : 11.51086956521739130434782608695652173913043478260868 : [66, 70]
185 : 11.51891891891891891891891891891891891891891891891891 : [62, 64, 66, 70, 72, 74]
186 : 11.53225806451612903225806451612903225806451612903225 : [62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77]
187 : 11.54010695187165775401069518716577540106951871657753 : [66, 70, 72, 74, 76]
188 : 11.55319148936170212765957446808510638297872340425531 : [64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77]
189 : 11.56084656084656084656084656084656084656084656084655 : [66, 68, 70, 74, 76]
190 : 11.57368421052631578947368421052631578947368421052631 : [66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77]
191 : 11.58115183246073298429319371727748691099476439790575 : [68, 70, 72, 74, 76]
192 : 11.59374999999999999999999999999999999999999999999999 : [68, 69, 70, 71, 72, 73, 74, 75, 76, 77]
193 : 11.60103626943005181347150259067357512953367875647667 : [72]
194 : 11.61340206185567010309278350515463917525773195876288 : [70, 71, 72, 73, 74, 75, 76, 77]
195 : 11.62051282051282051282051282051282051282051282051281 : [72, 74, 76]
196 : 11.63265306122448979591836734693877551020408163265305 : [72, 73, 74, 75, 77]
197 : 11.63959390862944162436548223350253807106598984771573 : [74, 76]
198 : 11.65151515151515151515151515151515151515151515151514 : [74, 75, 76, 77]
199 : 11.65829145728643216080402010050251256281407035175879 : [76]
200 : 11.66999999999999999999999999999999999999999999999999 : [76, 77]

As a side note: If you plot the set size against the (multiple) optimal sub-set sizes then you get an interesting pattern.