6
$\begingroup$

Let $V$ be a $k$-dimensional vector ($k$ is given) of the form $$V=[n_1, n_2, ..., n_k],$$

where $n_1, n_2, ..., n_k$ are positive integers.

Your objective is to determine $V$ by choosing $T$ vectors of your choice, and receiving their dot products with $V$ respectively.

for example, if my vector is $[1, 2]$, and your vectors are $[1, 1], [5, 3/2]$, you will get their dot poducts: $([1,1]*[1,2] =3, [5,3/2]*[1,2] = 8)$

What is the minimum number of vectors $T$ that you need to choose to determine $V$? (bonus: add the requirement that your vectors must consist of positive integers as well)

(p.s. there exists a solution $T<k$, it's not that obvious)

The solution to this riddle(s) is amazing, and i'll post it in a couple of days.

$\endgroup$
  • $\begingroup$ The number of vectors $T$ is meant to be minimum in a absolute sense (i.e. given any vector $V$ of positive integer, you can figure out it using exactly $t$ vectors $T$), or minimum in average (i.e. in the average of a lot of possible vectors $V$, which is the minimum number of vectors $T$)? $\endgroup$ – the_candyman Feb 19 '18 at 22:58
  • 2
    $\begingroup$ Your "riddle" needs some clarification. Does this game involve rounds where I submit a vector and you respond with a dot product or do I have to send you all my vectors at once? $\endgroup$ – Rob Arthan Feb 19 '18 at 22:58
  • $\begingroup$ the first option (minimum T in an absolute sense) $\endgroup$ – user532929 Feb 19 '18 at 23:00
  • $\begingroup$ you know what dot product was produced by each vector you gave me, so it's as if you send me them one by one. $\endgroup$ – user532929 Feb 19 '18 at 23:08
  • 2
    $\begingroup$ @IdoFraenkel: Your comment doesn't answer my question. In a game of questions, it makes a great deal of difference if I have to design all my questions in advance or whether I can use the answers to earlier questions to help me design the next question. $\endgroup$ – Rob Arthan Feb 19 '18 at 23:13
11
$\begingroup$

If any real numbers are allowed then $ T=1 $: choose the vector $(e, e^2,\ldots , e^n) $ and use the fact that $ e $ is transcendental. It is not constructive but you know that different vectors will output different dot products.

Edit: if $(a_1,\ldots, a_n) $ and $(b_1,\ldots, b_n) $ are two vectors that output the same number, then $ e $ is a root of the polynomial with integer coefficients $$\sum (a_i -b_i) X^i$$ therefore all its coefficients are zero.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice answer: I wonder whether it will be the right one when the OP eventually gives all the necessary information. $\endgroup$ – Rob Arthan Feb 19 '18 at 23:01
  • $\begingroup$ it's not that answer i had in mind but it is still correct. i think my solution is a bit better so stick around! meanwhile you can solve the bonus question, and maybe explain why your answer is correct in further detail. $\endgroup$ – user532929 Feb 19 '18 at 23:03
  • $\begingroup$ Thanks. I wonder too if one could find a constructivist solution with $ T=1 $. $\endgroup$ – Arnaud Mortier Feb 19 '18 at 23:04
  • $\begingroup$ i don't exactly know what you mean by 'constructive', but if it is what i think it is then my answer is a constructive solution. $\endgroup$ – user532929 Feb 19 '18 at 23:11
  • $\begingroup$ You don't even need transcendental numbers, just any numbers that are linearly independent over $\mathbb Q$, e.g. square roots of distinct primes. $\endgroup$ – Carmeister Feb 20 '18 at 8:09
6
$\begingroup$

If $V$ were limited to entries at most $b$, then the solution would be easy: query $$ V \cdot [b^0, b^1, \dots, b^{k-1}]$$ The result, when read in base-$b$, would be the vector $V$. However, this would be foiled for any constant choice of $b$ because the entries of $V$ could be arbitrarily large. (Any scheme to "guess" such a $b$, for example, by repeatedly doubling, could be similarly fooled).

However, it's easy to get a $b$ large enough: $V \cdot [1, 1, \dots, 1]$ is the sum of the entries in $V$. Since all of the entries in $V$ are strictly positive, this dot product is strictly bigger than any entry in $V$ (as it's the sum of the largest element and the rest of the elements, which are at least 1).

Thus, the first query is $b = V \cdot [1, 1, 1, \dots, 1]$.

The second query is $v = V \cdot [b^0, b^1, b^2, \cdots, b^{k-1}]$.

Then $V$ is the result from reading the digits of $v$ in base-$b$, so $t \leq 2$.

(Since any number of vectors have the same dot product, $t \geq 2$ so this does give $t = 2$ exactly)


This relies heavily on the positiveness of the entries of $V$. Can the problem be solved in fewer than $k$ queries when the entries of $V$ are allowed to be negative?


I remember a very similar problem, that tasks you with determining the coefficients of a polynomial $q$ with only non-negative integer as coefficients with as few integer queries as possible. (The method looks about the same as this problem).

A link to a blog post concerning this problem is here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is exactly my solution $\endgroup$ – user532929 Feb 20 '18 at 5:57
  • 1
    $\begingroup$ Cross-site polynomial version link: A secret polynomial $\endgroup$ – boboquack Feb 20 '18 at 6:38
  • $\begingroup$ I think that the second query must be: $$v = V \cdot [(b+1)^0, (b+1)^1, (b+1)^2, \cdots, (b+1)^{k-1}].$$ If the maximum number is $b$, then you want to represent the hidden vector in base $b+1$... $\endgroup$ – the_candyman Feb 20 '18 at 16:16
  • $\begingroup$ Since the entries of $V$ are strictly positive (and I'm assuming there are at least two, otherwise this is trivial), $b$ will be at least one more than the largest element, so $b+1$ is not necessary. However, my explanation there was lacking, I'll update it. $\endgroup$ – Curtis F Feb 20 '18 at 22:00
3
$\begingroup$

Here is my answer:

Let $I = [ln(2),ln(3),...,ln(p_k)]$ where $p_k$ is the $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})$

Therefore, by taking the prime factorizations of $e^{V*I}$, and looking at the exponents, we can deduce what $V$ is.

So by choosing $I$ and only $I$ to be our vector, we can fully deduce $V$ (and $minT=1$).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I would choose $T = k$ vectors $a_1, a_2, \ldots, a_k$, which are linearly independent.

Then, I would create a matrix $A$ which rows corresponds to each vector $a_i$. For construction, $A$ is invertible.

Moreover, given $q_i$ as the dot product of $V$ with $a_i$, I create the column vector $q = [q_1 ~ q_2 ~ \ldots ~ q_k]^\top.$

Finally, I can calculate $V$ as follows:

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

Additionally, I can avoid the inversion of matrix $A$ if I choose $a_i$ as versors, i.e. $a_i$ has only $0$ components, and the $i$-th entry is $1$. In this case, $A$ is the identity matrix, and I obtain that:

$$q_i = n_i.$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice, but you did 't use the fact that v consists of positive integers. There is a better solution with t<k $\endgroup$ – user532929 Feb 19 '18 at 22:38
  • 1
    $\begingroup$ @IdoFraenkel when $k=2$, I would say that you can't do better than $2$, right? So maybe you mean $t$ vectors such that $t \leq k$? $\endgroup$ – the_candyman Feb 19 '18 at 22:50
  • 1
    $\begingroup$ as @ArnaudMortier has shown below, it is possible using T = 1 $\endgroup$ – user532929 Feb 19 '18 at 23:05
  • $\begingroup$ but for the bonus question you are correct $\endgroup$ – user532929 Feb 19 '18 at 23:06
  • 1
    $\begingroup$ if you choose $k$ vectors anyway, wouldn 't you take the $k$ unit vectors to obtain $V$ componentwise? $\endgroup$ – collapsar Feb 20 '18 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy