a***n 发帖数: 423 | 1 There is a list with 40 numbers from 1 to 40. If allowing only addition and
subtraction, what's the smallest subset which can represent all the numbers
in list? For example, 40 = 1+39. | t****a 发帖数: 3544 | 2 can it be 40 = 1 + 1 + 。。。。 + 1 ?
and
numbers
【在 a***n 的大作中提到】 : There is a list with 40 numbers from 1 to 40. If allowing only addition and : subtraction, what's the smallest subset which can represent all the numbers : in list? For example, 40 = 1+39.
| t****a 发帖数: 3544 | 3 If you have 2 numbers, you will generate another two number by add and sub,
thus you will get 4 number, i.e. 2+ C_{2}^(2)*2;
Similarly, with 3 numbers, it will represent 3+C_{3}^{2}*2 = 9;
with 4 numbers, 4 + C_{4}^{2}*2 = 16;
with 5 numbers, 5 + C_{5}^{2}*2 = 25;
with 6 numbers, 6 + C_{6}^{2}*2 = 36;
with 7 numbers, 7 + C_{7}^{2}*2 = 49.
So 7 numbers should be OK.
And we need to find it.
and
numbers
【在 a***n 的大作中提到】 : There is a list with 40 numbers from 1 to 40. If allowing only addition and : subtraction, what's the smallest subset which can represent all the numbers : in list? For example, 40 = 1+39.
| z****g 发帖数: 1978 | 4 This formulate a inter-changeable group because + and - are allowed at the
same time. So it is equal to the following algebra question:
find smallest subset A in X such that
A+A=X, where A+A := {a+b} for any a, b in A.
I can't remember the exact theory in algebra to decompose X, but I am sure
there is one. And it has something to do with prime number. Seems the basic
component is decided by 40 = 2 * 2 * 2 * 5 | D**u 发帖数: 204 | 5 1,3,9,27 will do.
You can treat it as a 天平 question. And generally a 天平 question is
related to
三进制.
and
numbers
【在 a***n 的大作中提到】 : There is a list with 40 numbers from 1 to 40. If allowing only addition and : subtraction, what's the smallest subset which can represent all the numbers : in list? For example, 40 = 1+39.
| c**********e 发帖数: 2007 | 6 正解。
【在 D**u 的大作中提到】 : 1,3,9,27 will do. : You can treat it as a 天平 question. And generally a 天平 question is : related to : 三进制. : : and : numbers
| a***n 发帖数: 423 | 7 no duplication. only addition and subtraction are allowed.
and
numbers
【在 a***n 的大作中提到】 : There is a list with 40 numbers from 1 to 40. If allowing only addition and : subtraction, what's the smallest subset which can represent all the numbers : in list? For example, 40 = 1+39.
| a*****h 发帖数: 484 | 8 Nice! What is a typical 天平 question like?
【在 D**u 的大作中提到】 : 1,3,9,27 will do. : You can treat it as a 天平 question. And generally a 天平 question is : related to : 三进制. : : and : numbers
| D**u 发帖数: 204 | 9 In this question, you can treat 1,3,9,27 as 4 砝码,
and the number you want to measure as the unknown 砝码.
Put the unknown 砝码 you want to measure on the left side of 天平.
Each other 砝码 has "3" possible positions to put it:
on the left of 天平;
on the right of 天平;
or not on either side.
The relation to 三进制 comes from the "3" above.
Generally when you have n 砝码, you can measure
at most 3^n different numbers, and only (3^n-1)/2
of them are positive. This says that
3 砝码 is not enough to measure 1-40, so we have
to use at least 4 砝码.
【在 a*****h 的大作中提到】 : Nice! What is a typical 天平 question like?
| a*****h 发帖数: 484 | 10 Thanks. What a beautiful analysis!
【在 D**u 的大作中提到】 : In this question, you can treat 1,3,9,27 as 4 砝码, : and the number you want to measure as the unknown 砝码. : Put the unknown 砝码 you want to measure on the left side of 天平. : Each other 砝码 has "3" possible positions to put it: : on the left of 天平; : on the right of 天平; : or not on either side. : The relation to 三进制 comes from the "3" above. : Generally when you have n 砝码, you can measure : at most 3^n different numbers, and only (3^n-1)/2
| M********t 发帖数: 163 | 11 火工头陀强啊,尤其喜欢你的expression方式。
我发现虽然有些人老喜欢回答问题,但是似乎从来没有回答到点子上过。
【在 D**u 的大作中提到】 : In this question, you can treat 1,3,9,27 as 4 砝码, : and the number you want to measure as the unknown 砝码. : Put the unknown 砝码 you want to measure on the left side of 天平. : Each other 砝码 has "3" possible positions to put it: : on the left of 天平; : on the right of 天平; : or not on either side. : The relation to 三进制 comes from the "3" above. : Generally when you have n 砝码, you can measure : at most 3^n different numbers, and only (3^n-1)/2
| t*******g 发帖数: 373 | 12 这条评论也很强...
【在 M********t 的大作中提到】 : 火工头陀强啊,尤其喜欢你的expression方式。 : 我发现虽然有些人老喜欢回答问题,但是似乎从来没有回答到点子上过。
|
|