Fresco enigma que involucran vectores de enteros

Question

Deje $V$ $k$- dimensiones del vector ( $k$ ) de la forma $$V=[n_1, n_2, ..., n_k],$$

donde $n_1, n_2, ..., n_k$ son enteros positivos.

Su objetivo es determinar $V$ eligiendo $T$ vectores de su elección, y la recepción de sus productos de puntos con $V$ respectivamente.

por ejemplo, si el vector es $[1, 2]$, y la de los vectores de $[1, 1], [5, 3/2]$, obtendrá su punto poducts: $([1,1]*[1,2] =3, [5,3/2]*[1,2] = 8)$

¿Cuál es el número mínimo de vectores $T$ que usted necesita para elegir a determinar $V$? (bonus: añadir el requisito de que sus vectores debe consistir de enteros positivos)

(p.s. existe una solución de $T<k$, no es que obvio)

La solución a este acertijo(s) es increíble, y lo voy a publicar en un par de días.

Answer 1

Si alguno de los números reales están permitidos, a continuación,$ T=1 $: elegir el vector $(e, e^2,\ldots , e^n) $ y utilice el hecho de que $ e $ es trascendental. No es constructivo, pero usted sabe que los diferentes vectores de salida de productos de puntos.

Edit: si $(a_1,\ldots, a_n) $ $(b_1,\ldots, b_n) $ son dos vectores que de salida el mismo número, $ e $ es una raíz del polinomio con coeficientes enteros $$\sum (a_i -b_i) X^i$$, por tanto, todos los coeficientes son cero.

Answer 2

Si $V$ se limita a las entradas en la mayoría de los $b$, entonces la solución sería fácil: consulta $$ V \cdot [b^0, b^1, \dots, b^{k-1}]$$ El resultado, cuando se leen en la base-$b$, sería el vector $V$. Sin embargo, esto sería frustrado por cualquier elección constante de $b$ debido a que las entradas de $V$ puede ser arbitrariamente grande. (Cualquier esquema de "adivinar"$b$, por ejemplo, en varias ocasiones la duplicación, podría ser igual de engañados).

Sin embargo, es fácil obtener un $b$ lo suficientemente grande: $V \cdot [1, 1, \dots, 1]$ es la suma de las entradas en $V$. Puesto que todas las entradas en $V$ son estrictamente positivos, este producto escalar es estrictamente mayor que cualquier entrada en $V$ (como es la suma del elemento más grande y el resto de los elementos, que son, al menos, 1).

Por lo tanto, la primera consulta es $b = V \cdot [1, 1, 1, \dots, 1]$.

La segunda consulta es $v = V \cdot [b^0, b^1, b^2, \cdots, b^{k-1}]$.

A continuación, $V$ es el resultado de la lectura de los dígitos de $v$ base$b$, lo $t \leq 2$.

(Desde cualquier número de vectores tienen el mismo punto del producto, $t \geq 2$, por lo que esto da $t = 2$ exactamente)

---

Esto se basa en gran medida en la positividad de las entradas de $V$. Puede que el problema esté solucionado en menos de $k$ consultas cuando las entradas de $V$ están autorizados a ser negativo?

---

Recuerdo una muy similar problema, que las tareas con la determinación de los coeficientes de un polinomio $q$ con sólo entero no negativo como coeficientes con tan pocos entero consultas como sea posible. (El método que se ve sobre el mismo ya que este problema).

Un enlace a un post en el blog sobre este problema está aquí.

Answer 3

Aquí está mi respuesta:

Deje $I = [ln(2),ln(3),...,ln(p_k)]$ donde $p_k$ $k^{th}$ prime.

$V*I=n_1ln(2)+n_2ln(3)+...+n_kln(p_k) = ln(2^{n_1}*3^{n_2}*...*p_k^{n_k})$

Por lo tanto, teniendo el primer factorizations de $e^{V*I}$, y mirando a los exponentes, se puede deducir lo $V$ es.

Así que eligiendo $I$ y sólo el $I$ a ser nuestro vector, podemos deducir totalmente $V$ (e $minT=1$).

Answer 4

Yo elegiría $T = k$ vectores $a_1, a_2, \ldots, a_k$, que son linealmente independientes.

A continuación, me gustaría crear una matriz de $A$ sobre las filas que corresponde a cada vector $a_i$. Para la construcción, $A$ es invertible.

Por otra parte, dado $q_i$ como el producto escalar de a$V$$a_i$, puedo crear el vector de columna $q = [q_1 ~ q_2 ~ \ldots ~ q_k]^\top.$

Finalmente, puedo calcular el $V$ como sigue:

$$V = A^{-1}q.$$

Además, puede evitar la inversión de la matriz $A$ si elijo $a_i$ versors, es decir, $a_i$ sólo ha $0$ componentes, y el $i$-ésima es $1$. En este caso, $A$ es la matriz identidad, y puedo obtener que:

$$q_i = n_i.$$