两次提问确定三个数

2 Equations & 3 Unknowns

专题: General / 综合
难度: L4
来源: Brainstellar

题目详情

我想了三个自然数 $x,y,z$ 。

你可以向我问两次问题：每次你给出整数系数 $(a,b,c)$ ，我会告诉你 $ax+by+cz$ 的值。

如何通过两次提问保证确定 $x,y,z$ ？

I guessed 3 natural numbers - $x, y, z$ . You can ask me 2 sums of these numbers with any integer coefficients - $(a, b, c)$ . That is, you give me a, b and c and I tell you the result of the expression $a*x+b*y+c*z$ . Seeing the answer, you then give me the 2nd triplet of $(a,b,c)$ & I will tell $a*x+b*y+c*z$ . Give me the algorithm to find $x$ , $y$ and $z$ .

Hint

If digits are small, we can solve any number of variables by asking $a=1, b=10^{100}, c=10^{200}$ etc. just by reading these numbers between the zeros of result.

解析

关键是先用一次提问估计出位数上界，再用“进位分隔”的方式把三个数编码进一次和里。

先问 $(1,1,1)$ 得到 $x+y+z$ ，从而得到三者的位数上界（例如 $d=\lceil\log_{10}(x+y+z+1)\rceil$ ）。
再问 $(1,10^d,10^{2d})$ 得到

S=x+10^d y+10^{2d} z.

由于 $10^d$ 足以分隔位数，可以从十进制展开中直接读出 $x,y,z$ 。

Original Explanation

Solution

Since they are natural numbers, if you knew the maximum number of digits any of them can have, say d, you could set a=1, b=10^d, c=10^2d, and you would be able to read the d-digit numbers directly. So, you use the first calculation to find the maximum number of digits, $(a,b,c)=(1,1,1)$ . let $d =$ digits of this result $(x+y+z)$ Then, set $(a,b,c) = (1, 10^d, 10^{2d})$ Let the sum be $S$ . Then $x =$ (first $d$ digits of $S$ ), $y = [d+1]$ to $2d$ -digits of S, $z$ = $[2d+1$ to $3d]$ digits of $S$

Thus, we note that its posssible to solve for n natural numbers $x_1,x_2,...x_n$ with just $2$ questions.