ESTA RESPUESTA FUE ESCRITA BAJO LA IMPRESIÓN DE QUE OP SE REFERÍA A UNA ESCALA COMO ESTA: ![enter image description here]()
EN LUGAR DE UNA ESCALA COMO ESTA: ![! enter image description here]()
. DESPUÉS DE ESCRIBIR LA RESPUESTA, OP AÑADIÓ LA ACLARACIÓN DE QUE SE REFERÍA AL REVÉS.
No, no es posible determinar si las etiquetas son correctas.
Al contrario de lo que podría parecer a primera vista, la prueba es breve; está contenida en el último párrafo que precede a la sección de conclusiones, Generalizaciones . El resto de este post está dedicado a formalizar lo que hay que probar (siendo la formalización resultante la frase resaltada al final de este post), a introducir la notación utilizada en la formalización y en la prueba, y a argumentar que la formalización concuerda con el problema que se describe informalmente en el puesto original .
Denotemos el conjunto de etiquetas por $L$ es decir $L := \{1, 2, \dots, 6\}$ . Denote por $\Pi$ el conjunto formado por todas las formas de etiquetar los cubos. Para cada $\pi \in \Pi$ y para cada $\ell \in L$ , $\pi(\ell)$ es el peso del cubo etiquetado $\ell$ según el esquema de etiquetado $\pi$ . En otras palabras, $\Pi$ es el conjunto de permutaciones de $L$ . Denotemos la permutación de identidad por $I$ y denotar el esquema de etiquetado dado por $\pi^*$ .
Para cada esquema de etiquetado $\pi \in \Pi$ , denótese por $w_\pi$ la función que asigna a cada subconjunto, $S \subseteq L$ de cubos, identificados por sus etiquetas, su peso por $\pi$ : $$ w_\pi(S) := \sum_{s \in S} \pi(s). $$
Cada subconjunto de etiquetas, $S \subseteq L$ induce una relación de equivalencia, $\cong_S$ , en $\Pi$ como sigue. Para cada $\pi_1, \pi_2 \in \Pi$ , $\pi_1 \cong_S \pi_2$ si $w_{\pi_1}(S) = w_{\pi_2}(S)$ . (¡Verifique que se trata efectivamente de una relación de equivalencia!) Denote por $E_S$ la familia de clases de equivalencia correspondiente a $\cong_S$ . Para cada esquema de etiquetado, $\pi \in \Pi$ , $\pi$ de la clase de equivalencia en $E_S$ se denotará por $[\pi]_S$ .
Con esta terminología, mostraremos que el problema se reduce a la siguiente pregunta ¿Existe algún par $S_1, S_2 \subseteq L$ , de tal manera que $$ [I]_{S_1} \cap [I]_{S_2} = \{I\}\tag{1}\label{Apple} $$
Para ver que esta formulación capta efectivamente el planteamiento del problema descrito en el post original, supongamos en primer lugar que hay unos $S_1,S_2 \subseteq L$ tal que \eqref{Apple} se mantiene. Utilizar la balanza para pesar los cubos, cuyo conjunto de etiquetas $S_1$ es, y luego utiliza la balanza una vez más para pesar los cubos, cuyo conjunto de etiquetas $S_2$ es. Denotemos las dos ponderaciones así obtenidas por $w_1, w_2$ respectivamente. Si $$ w_1 = w_I(S_1)\ \wedge\ w_2 = w_I(S_2), \tag{2}\label{Banana} $$ informan que $\pi^* = I$ ; en caso contrario, informe de que $\pi^* \neq I$ . Para verificar la corrección de este algoritmo, basta con observar que la condición \eqref{Banana} se cumple sif $\pi^* \in [I]_{S_1}\cap[I]_{S_2}$ .
A la inversa, supongamos que hay algún par $S_1,S_2\subseteq L$ de conjuntos de cubos (dados por sus etiquetas según el esquema de etiquetado $\pi^*$ ), para lo cual es posible, pesando consecutivamente $S_1$ y $S_2$ para saber si $\pi^* = I$ o $\pi^* \neq I$ . Cualquier algoritmo, $\mathfrak{A} = \mathfrak{A}_{S_1, S_2}$ que se puede utilizar para llegar a esta determinación, sólo puede tener acceso indirecto a $\pi^*$ en forma de $S_1$ y $S_2$ de los pesos. Para cada $\pi\in\Pi$ , $\mathfrak{A}$ toma $w_\pi(S_1)$ y $w_\pi(S_2)$ como argumentos de entrada, y se basa únicamente en estos argumentos (así como en $S_1$ y $S_2$ ) que $\mathfrak{A}$ debe calcular su salida: $$ \mathfrak{A}\big(w_\pi(S_1), w_\pi(S_2)\big) = \begin{cases} \mathrm{TRUE} &, \pi = I, \\ \mathrm{FALSE} &, \mathrm{otherwise}. \end{cases} $$ Para ver que \eqref{Apple} se mantiene, dejemos que $\pi \in [I]_{S_1}\cap[I]_{S_2}$ . Entonces $\mathfrak{A}\big(w_\pi(S_1), w_\pi(S_2)\big) = \mathfrak{A}\big(w_I(S_1), w_I(S_2)\big) = \mathrm{TRUE}$ para que $\pi = I$ .
Para cada par de etiquetas distintas, $a, b \in L$ , denótese por $\tau_{\{a,b\}}$ la transposición $(a\ b)$ es decir $\tau_{\{a, b\}}$ es la permutación $\pi \in \Pi$ que satisface $$ \begin{align} \pi(a) &= b, \\ \pi(b) &= a, \end{align} $$ y $\pi(\ell) = \ell$ por cada $\ell \in L\setminus\{a,b\}$ .
Ahora podemos demostrar finalmente que no hay $S_1, S_2 \subseteq L$ tal que \eqref{Apple} se mantiene. Equivalentemente, demostraremos lo siguiente.
El conjunto $T$ que se compone de todos los pares $(S_1, S_2) \in (\mathcal{P}L)^2$ para la que se cumple \eqref{Apple}, es vacía.
Supongamos lo contrario, y dejemos que $(S_1, S_2) \in T$ . Definir $$ S_1' := \begin{cases} S_1 &, |S_1| \geq 3, \\ L\setminus S_1 &, \mathrm{otherwise}. \end{cases} $$ Entonces $|S_1'| \geq 3$ y $(S_1', S_2) \in T$ . (¡Verifique!) Elija $B \subseteq L$ de la siguiente manera. Si $|S_1' \cap S_2| \geq 2$ , dejemos que $B \subseteq S_1'\cap S_2$ sea cualquier subconjunto de cardinalidad $2$ . De lo contrario, deja que $B \subseteq S_1' \setminus S_2$ sea cualquier subconjunto de cardinalidad $2$ . Entonces $\tau_B \in [I]_{S_1'} \cap [I]_{S_2}$ para que $\tau_B = I$ ¡una contradicción!
Generalizaciones
La prueba puede ajustarse fácilmente para tener en cuenta un conjunto inicial de $n \geq 5$ cubos equipados con un $n$ -tupla, $(r_1, r_2, \dots, r_n)$ de números reales distintos que representan los "pesos" de los cubos (si los "pesos" no son distintos, entonces es trivialmente imposible saber si el etiquetado es correcto simplemente pesando los cubos).
