Encontrar monedas falsas

Question

Supongamos que tengo $N$ monedas raras, de las cuales $M \le N$ son falsificaciones. Soy ciego. Le pido a un oráculo que me cobra un céntimo que me diga en respuestas de sí/no si hay una falsificación en cualquier grupo que le muestre. ¿Existe una estrategia para identificar todas las $M$ monedas con un coste mínimo, preferiblemente algo mejor que $O(N)$ ?

Esto parece una variante del problema de las monedas falsas, pero no encuentro una buena solución.

EDIT: En el caso de $M=1$ una solución obvia es del orden de $\log_2(N)$ donde se numera cada moneda en orden, en base $2$ . Luego, comprueba cada grupo por dígitos donde la moneda tiene un 1 en ese dígito. Entonces la falsificación debe ser identificada por la lectura del oráculo por dígitos, en base $2$ .

Answer 1

Para $M=2$ puedes hacerlo en $2 \log_2 N$ mediante la misma búsqueda binaria que para $M=1$ . Divide las monedas en dos mitades y pregunta por una de ellas. Si obtienes una respuesta afirmativa, pregunta por la otra. Si vuelves a obtener un sí, tienes dos búsquedas binarias de una moneda cada una. Si obtienes un no, estás buscando dos monedas en $\frac N2$ . Te ahorras una pregunta si obtienes un no la primera vez mientras no has separado la pareja porque no tienes que preguntar por la segunda parte.

El enfoque teórico de la información sería tratar de mantener la probabilidad de cada respuesta cerca de $\frac 12$ . Si se pregunta por un grupo de $k$ monedas, la posibilidad de una respuesta negativa es $\left( 1-\frac MN\right)^k$ . $$\left( 1-\frac MN\right)^k=\frac 12\\ k \log \left( 1-\frac MN\right)=-\log 2\\ k=-\frac {\log 2}{\log \left(1-\frac MN\right)}$$ Esto no tiene en cuenta los efectos de que las monedas sean discretas, pero si tiene $10\%$ falsificaciones hay que preguntar por los grupos de $6$ o $7$

La estrategia que propongo para los grandes $N$ y al menos moderado $M$ que no he comprobado que sea óptima, sería calcular $k$ de lo anterior y preguntar por un grupo de $k$ monedas. Si obtienes un no, descarta las monedas, actualiza $N$ y continuar. Si obtienes un sí, resuelve el $k$ monedas y actualizar ambos $M,N$ para el siguiente grupo. Como el grupo será pequeño y no se sabe con certeza cuántos billetes falsos hay en él, probablemente sea óptimo pedir moneda por moneda. Hay una oportunidad de optimizar el final del juego donde $N$ no es grande.

Answer 2

Dejemos que $f(n, m)$ sea el coste óptimo en el peor de los casos, $0 \le m \le n$ . Ya lo tienes $f(n, 1) \sim \log_2(n)$ . Específicamente, $f(n, 1) = \lceil \log_2(n) \rceil$ . También $f(n, 0) = f(n, n) = 0$ ya que no será necesario adivinar para determinar las falsificaciones.

$f(n, n-1)$ : Como sólo hay una moneda real, la única manera de determinar la verdadera es pasar por todas las monedas (excepto posiblemente la última) - no tiene sentido dividir los montones. Por lo tanto, $f(n, n-1) = n-1$ .

$f(4, 2)$ : Puedes preguntar por una pila de tamaño $1$ o $2$ (no tiene sentido preguntar por un montón de tamaño $3$ ya que está garantizada su falsificación). Si pregunta por un montón de $1$ , entonces eso se reduce a $1+\max(f(3, 1), f(3, 2)) = 1+\max(2, 2) = 3$ . Si preguntas por un grupo de tamaño $2$ y obtienes un "no" como respuesta, has terminado. Si la respuesta es "sí", tendrá que preguntar $2$ más preguntas, así que $f(4, 2) = 3$ .

$f(n, 2)$ : Preguntemos sobre $k$ monedas, $1 \le k < n$ . Si la respuesta es "no", entonces se convierte en $1+f(n-k, 2)$ . Para el caso de que la respuesta sea "sí", definiré una función de ayuda, $g(a, b)$ que representa el coste óptimo en el peor de los casos cuando hay $2$ total de falsificaciones, $a$ es el tamaño del grupo de monedas que se garantiza que tiene al menos $1$ falsificación, $b$ es el tamaño del grupo con un número desconocido de falsificaciones (ya sea $1$ o $0$ ). Entonces $f(n, 2) = \min(\max(1+f(n-k, 2), 1+g(k, n-k)) \forall k, 1 \le k < n)$ .

$g(a, b)$ : $g(a, 0) = f(a, 2)$ , $g(1, b) = f(b, 1)$ . Tenemos dos opciones: o bien preguntar por $k_1 (1 \le k_1 < a)$ del grupo $a$ o $k_2 (1 \le k_2 \le b)$ del grupo $b$ . Si preguntamos por $k_1$ y obtener una respuesta afirmativa, que se convierte en $1+g(k_1, a+b-k_1)$ . Si obtenemos un "no" como respuesta, eso se convierte en $1+g(a-k_1, b)$ . Si preguntamos $k_2$ y obtener un "sí", que se convierte en $1+f(a, 1)+f(k_2, 1)$ . Si obtenemos un "no", eso se convierte en $1+g(a,b-k_2)$ . Por lo tanto, $g(a, b) = \min(\max(1+g(k_1, a+b-k_1), 1+g(a-k_1, b)) \forall k_1, 1 \le k_1 < a, \max(1+f(a, 1)+f(k_2, 1), 1+g(a,b-k_2)) \forall k_2, 1 \le k_2 \le b)$

Usando esto, me las arreglé para encontrar A200311 en la OEIS. Obsérvese que la entrada de la OEIS está desplazada por dos (es decir, A200311(n+2) = f(n, 2)) y la primera entrada es diferente. A partir de ahí, he descubierto que $$f(n, 2) = \left\lfloor 2\log_2(n-1) + 2\log_2 \left(\frac{7}{6} \right) \right\rfloor +_? 1$$

(No he podido encontrar la notación de " $x$ o $x+1$ ", así que me inventé algo - espero que quede claro)

Lo que noté fue que para el primer grupo, se podía tomar cualquier cosa de $\approx n/4$ a $ \approx n/3$ . Por ejemplo, para $n = 400$ , cualquier cosa desde $96 \approx \frac{400}{4}$ a $128 \approx \frac{400}{3}$ estaba bien para el tamaño de la primera suposición. Todo lo demás no era óptimo. En este rango, el coste del peor caso era el mismo tanto si el oráculo respondía "sí" como "no" a esa consulta.

Editar para f(n, m) :

Voy a definir una función de ayuda, $g(p_1;p_2;...;p_k, b, c)$ para el coste óptimo en el peor de los casos, donde $p_i$ representa el número de pilas de tamaño $i$ garantiza tener al menos una moneda, $b$ monedas no examinadas, y $c$ total de falsificaciones en la configuración.

La primera consulta equivale a $g$ , $$f(n, m) = g(\lbrack \rbrack, n, m)$$

Echemos un vistazo a $g$ ahora. Los casos base son $g(p_1;p_2;...;p_k, b, 1\cdot p_1 + 2\cdot p_2 + ... + k\cdot p_k + b) = 0$ y $g(p_1;p_2;...;p_k, b, p_1+p_2+...+p_k) = \sum_{i=1}^{k} p_i \cdot f(i, 1)$ .

Para cualquier otro momento, tenemos varias opciones: desde un montón de tamaño $t$ con una falsificación conocida, podemos hacer cualquier consulta hasta el tamaño $m_1, 1 \le m_1 < t$ . Digamos que elegimos $m_1$ de $t$ . Entonces, con una respuesta afirmativa, eso hace que $p_t$ bajar $1$ , $p_{m_1}$ subir $1$ y $b$ subir $t-m_1$ . Con una respuesta "no", eso hace que $p_t$ bajar $1$ y $p_{t-m_1}$ subir $1$ .

De la " $b$ ", podemos hacer una consulta hasta el tamaño $m_2, 1 \le m_2 \le \min(b, b-c+\sum_{i=1}^{k} k\cdot p_k)$ . Con una respuesta afirmativa, $p_{m_2}$ sube $1$ y $b$ baja $m_2$ . Con una respuesta negativa, $b$ baja $m_2$ .

Utilizando un programa de Python, obtuve el coste óptimo correcto en el peor de los casos (código en la parte inferior). Lo que noté fue que $$f(n, n-k) = n-1$$ para un fijo $k$ después de $n$ es lo suficientemente alto. Por ejemplo, para $k = 7$ , $f(n, n-7) \not = n-1$ sólo para $ n \le 10$ . En general, los resultados numéricos sugieren que $f(n, n-k) = n-1$ si $$n \ge \left\lfloor \frac{3k+1}{2} \right\rfloor$$

Equivalentemente, $f(n, m) = n-1$ para $$m \ge \left\lceil \frac{n}{3} \right\rceil$$

El código de Python es bastante lento: fuerza bruta todas las ramas posibles. No implementé la poda alfa-beta como podría haberlo hecho.

def f(n, m, dic1 = {}, dic2 = {}):
    T = (n, m)
    if T in dic1:
        return dic1[T]
    if m == 0:
        dic1[T] = 0
        return 0
    if m == 1:
        dic1[T] = math.ceil(math.log2(n))
        return dic1[T]
    if n == m:
        dic1[T] = 0
        return 0
    elif n == m+1:
        dic1[T] = m
        return m

    dic1[T] = g((), n, m, dic1, dic2)

    return dic1[T]

def g(P, b, c, dic1, dic2):
    #precondition: P[-1] != 0
    #would also speed up computation since more memoization possibility
    T = (P, b, c)
    #T = (tuple, int, int)

    numPiles = sum(P)
    totalCoins = sum((i+1)*P[i] for i in range(len(P)))+b

    if T in dic2:
        return dic2[T]
    if c == numPiles:
        #one coin in each pile
        dic2[T] = sum(P[i]*f(i+1, 1, dic1, dic2) for i in range(len(P)))
        return dic2[T]

    if c == totalCoins:
        #all the remaining coins are counterfeits
        dic2[T] = 0
        return 0

    worstCase = math.inf
    for index in range(len(P)):
        if P[index] != 0:
            #can only ask if there is a pile with that many coins
            t = index+1 #to adjust for 0-based indexing
            for m1 in range(1, min(t-1, totalCoins-c)+1):
                tmpP = P[:t-1]+(P[t-1]-1,)+P[t:]

                firstNewP = tmpP[:m1-1]+(tmpP[m1-1]+1,)+tmpP[m1:]
                secondNewP = tmpP[:t-m1-1]+(tmpP[t-m1-1]+1,)+tmpP[t-m1:]

                while len(firstNewP) > 0 and firstNewP[-1] == 0:
                    #to make sure that the last element is not zero
                    firstNewP = firstNewP[:-1]

                while len(secondNewP) > 0 and secondNewP[-1] == 0:
                    #to make sure that the last element is not zero
                    secondNewP = secondNewP[:-1]

                comp = 1+max(g(firstNewP, b+t-m1, c, dic1, dic2), g(secondNewP, b, c, dic1, dic2))
                if comp < worstCase:
                    worstCase = comp

    for m2 in range(1, min(b, totalCoins-c)+1):
        if len(P) < m2:
            firstNewP = P+(0,)*(m2-len(P))
        else:
            firstNewP = P
        firstNewP = firstNewP[:m2-1]+(firstNewP[m2-1]+1,)+firstNewP[m2:]
        comp = 1+max(g(firstNewP, b-m2, c, dic1, dic2), g(P, b-m2, c, dic1, dic2))
        if comp < worstCase:
            worstCase = comp

    dic2[T] = worstCase
    return worstCase