$1$ or $-1$ is written in $50$ letters. These letters are put into $50$ envelopes. If you ask, you can learn the product of numbers written into any three letters. At least, how many questions are required to find the product of all of the $50$ numbers?
Problem
Source:
Tags:
admin25
19.01.2013 05:41
I claim that it takes a minimum of $ 18 $ questions.
First, a construction for $ 18 $ questions. Take $ 16 $ disjoint groups of $ 3 $ numbers each, and find the product of the numbers in each group. That gives you the product of $ 3\cdot16=48 $ of the numbers. To find the product of the last two numbers (say $ x $ and $ y $), take two groups, $ \{a_1,a_2,x\} $ and $ \{a_1,a_2,y\} $ and find their product. If the product is the same, then $ x=y $, and $ xy=1 $. If the products are different, then $ x=-y $, and $ xy=-1 $. Therefore, the product of $ 16 $ disjoint groups of $ 3 $ numbers are found, and also the product of the last two numbers, so the total product is found by multiplying all of these products.
Now to show that $ 18 $ is indeed a minimum. Say a number is "evidenced" if there exists a set with a known product that contains that number, that is, one of the questioned products contains that number. Since all of the numbers are independent, every number needs to be evidenced at least once to find the total product. Clearly there needs to be more than $ 16 $ questions, since per question we can only evidence a maximum of $ 3 $ numbers. Thus it remains to show that $ 17 $ questions cannot determine the total product.
Suppose, on the contrary, that there exist $ 17 $ questions that give the total product. Since there are only $ 50 $ elements, at least one element must be evidenced more than once. If more than one element is evidenced more than once, then there would be less than $ 50 $ total numbers evidenced. By similar logic, that one element must be evidenced exactly twice.
Therefore, if such $ 17 $ questions exist, there must be $ 16 $ subsets with $ 3 $ elements questioned, along with one more subset that has exactly one element in common with one of the $ 16 $ subsets. Let the two nondisjoint subsets be $ \{a_1,a_2,x \} $ and $ \{a_3,a_4,x\} $. Since the total product is determined, and the other subsets are disjoint so that their product is determined, the product of the union of these two sets must be determined. Therefore, we must be able to determine the product of these two sets, that is, the value of $ a_1a_2a_3a_4x $ must be determined from the products $ a_1a_2x $ and $ a_3a_4x $. However, if $ x=1 $, then the product of the union is equal to the product of the two subsets, but if $ x=-1 $, then the product of the union is equal to the negative product of the two subsets, and since the value of $ x $ clearly cannot be determined from the given products, it must be impossible to find the product of all of the elements with only $ 17 $ questions.
Therefore, there is a minimum of $ 18 $ questions that need to be asked to find the product of all of the elements.
Milana
12.05.2020 23:52
admin25 wrote:
I claim that it takes a minimum of $ 18 $ questions.
First, a construction for $ 18 $ questions. Take $ 16 $ disjoint groups of $ 3 $ numbers each, and find the product of the numbers in each group. That gives you the product of $ 3\cdot16=48 $ of the numbers. To find the product of the last two numbers (say $ x $ and $ y $), take two groups, $ \{a_1,a_2,x\} $ and $ \{a_1,a_2,y\} $ and find their product. If the product is the same, then $ x=y $, and $ xy=1 $. If the products are different, then $ x=-y $, and $ xy=-1 $. Therefore, the product of $ 16 $ disjoint groups of $ 3 $ numbers are found, and also the product of the last two numbers, so the total product is found by multiplying all of these products.
Now to show that $ 18 $ is indeed a minimum. Say a number is "evidenced" if there exists a set with a known product that contains that number, that is, one of the questioned products contains that number. Since all of the numbers are independent, every number needs to be evidenced at least once to find the total product. Clearly there needs to be more than $ 16 $ questions, since per question we can only evidence a maximum of $ 3 $ numbers. Thus it remains to show that $ 17 $ questions cannot determine the total product.
Suppose, on the contrary, that there exist $ 17 $ questions that give the total product. Since there are only $ 50 $ elements, at least one element must be evidenced more than once. If more than one element is evidenced more than once, then there would be less than $ 50 $ total numbers evidenced. By similar logic, that one element must be evidenced exactly twice.
Therefore, if such $ 17 $ questions exist, there must be $ 16 $ subsets with $ 3 $ elements questioned, along with one more subset that has exactly one element in common with one of the $ 16 $ subsets. Let the two nondisjoint subsets be $ \{a_1,a_2,x \} $ and $ \{a_3,a_4,x\} $. Since the total product is determined, and the other subsets are disjoint so that their product is determined, the product of the union of these two sets must be determined. Therefore, we must be able to determine the product of these two sets, that is, the value of $ a_1a_2a_3a_4x $ must be determined from the products $ a_1a_2x $ and $ a_3a_4x $. However, if $ x=1 $, then the product of the union is equal to the product of the two subsets, but if $ x=-1 $, then the product of the union is equal to the negative product of the two subsets, and since the value of $ x $ clearly cannot be determined from the given products, it must be impossible to find the product of all of the elements with only $ 17 $ questions.
Therefore, there is a minimum of $ 18 $ questions that need to be asked to find the product of all of the elements.
It's probably a stupid question, but how do you find the product of $ a_1a_2 $ by knowing that $xy = 1$ (or that $xy = -1$) ?
benstein
23.05.2020 20:19
You don't need to as you already have the product of the $48$ numbers which are neither $x$ nor $y$.