How Many Peeks Without the Quantum Chip?

A Boolean function f on n bits comes with a promise: it is either constant (the same answer on all 2^n inputs) or balanced (answer 1 on exactly half of the inputs, 2^{n-1} of them, and 0 on the other half). A classical computer can only query f: ask for f(x) at one input x at a time. A quantum computer with the oracle needs one query. How much does a classical one need?

1. Certainty. A deterministic strategy picks each query from the answers so far (never at random), and after its last query names the kind, "constant" or "balanced". Let worst be the smallest number q for which some deterministic strategy names the kind correctly for every f that keeps the promise, never using more than q queries.
2. Random sampling. A sampler picks k distinct inputs uniformly at random (every set of k distinct inputs is equally likely), queries them, and says "constant" if all k answers are equal and "balanced" otherwise. It is never wrong on a constant f. Let err be the probability that it says "constant" when f is balanced (this is the same for every balanced f).

Write classical_peeks(n, k) that returns the pair (worst, err), with worst an integer and err a float.

Examples

Input:  n = 1, k = 1
Output: (2, 1.0)
Explanation: with one input there is nothing to compare, so the sampler always says "constant".

Input:  n = 3, k = 2
Output: (5, 0.42857142857142855)

Input:  n = 3, k = 5
Output: (5, 0.0)

Constraints

• 1 <= k <= 2**n; err is compared with a tolerance of 1e-6; a list [worst, err] is accepted in place of the tuple

Goals

• Find the worst-case number of classical queries needed to tell constant from balanced with certainty
• Compute the chance that random classical sampling is fooled by a balanced function