t*******8
发帖数: 172 | 1 There is a lock with the password between 000-999. But we could use only two
digits to open the lock. For example, if the password is 123, the lock is
open when you try 1*3, or *23, or 12*. questions: a) compose a strategy that
the try number of opening the lock is the smallest one under the worst
situation b) Prove that your strategy is optimal | C***m
发帖数: 120 | 2 one way is to try 090,190,290,...990, in total 10 tries. there is a similar
question in interview book(Green, Red, Heard on the street, don't remember
which one).
No idea how to prove this strategy is optimal... | A**u
发帖数: 2458 | 3 密码要是222， 你这个方法匹配不了.
similar
【在 C***m 的大作中提到】
: one way is to try 090,190,290,...990, in total 10 tries. there is a similar
: question in interview book(Green, Red, Heard on the street, don't remember
: which one).
: No idea how to prove this strategy is optimal...
| C***m
发帖数: 120 | 4 确实没说清楚，那个方法需要是圆形的保险柜锁。
第一次要拨090，从000开始，拨中间的那个环0,1,2，...9，相当于遍历了10个不同的
密码。
密码是222的话，要拨290。从200开始拨中间的环，0,1,2 然后保险柜就应该打开了，
实际上并没有拨到290.
如果是digital锁，上面方法不适用。
【在 A**u 的大作中提到】
: 密码要是222， 你这个方法匹配不了.
:
: similar
| w*******x
发帖数: 489 | 5 你这个描述一下就是固定末尾0，然后穷举前两位。
与什么琐没关系。设置密码，扭动一下能不能开算是试了一次。
也许最优了，如果固定最后一位，前两位怎么遍历都一样。而最后一位的转动并不能提
供额外信息或者增加概率。
？
【在 C***m 的大作中提到】
: 确实没说清楚，那个方法需要是圆形的保险柜锁。
: 第一次要拨090，从000开始，拨中间的那个环0,1,2，...9，相当于遍历了10个不同的
: 密码。
: 密码是222的话，要拨290。从200开始拨中间的环，0,1,2 然后保险柜就应该打开了，
: 实际上并没有拨到290.
: 如果是digital锁，上面方法不适用。
| q*********i
发帖数: 21 | 6 (made a mistake in last one, the following should be correct)
try the following 50 numbers
000 101 202 303 404
120 221 322 423 024
240 341 442 043 144
360 461 062 163 264
480 081 182 283 384
515 616 717 818 919
635 736 837 938 539
755 856 957 558 659
875 976 577 678 779
995 596 697 798 899
One can prove 50 is the lowest bound by contradiction.For a strategy with
less than 50 numbers, by the pigeon hole principle, there exists a X, such
that at most 4 numbers have the form *#X.For these four *#X, at most 4
different numbers appeared in the 1st digit, 4 appeared in the 2nd digit. So
you need at least 36 more numbers (X is not the last digit). The remaining
49-36=13 is not enough to cover 4*4*10 (use pigeon hole a couple more times).
two
that
【在 t*******8 的大作中提到】
: There is a lock with the password between 000-999. But we could use only two
: digits to open the lock. For example, if the password is 123, the lock is
: open when you try 1*3, or *23, or 12*. questions: a) compose a strategy that
: the try number of opening the lock is the smallest one under the worst
: situation b) Prove that your strategy is optimal
| s*****a
发帖数: 353 | 7 Theory:
let a and b be two combines, and define D(a,b) as the number of non-matching
digits between the two combines. One can see that (1) D is a legitimate
metric and (2) the lock is unlocked iff D<=1.
So set T as the combines that are tried, then every time you try a new
combine, you want it to be as far from T as possible, this will eliminate as
much new combines as possible.
Practice:
(1) Try 000,...999 (10 tries), and for each try the distance from the trial
to the tried set T is 3. If lock is not open, then we know the combine must
not have two same digits, leaving 10*9*8=720 combines
(2) Try 012,123,...901 and 210,321,...109 (20 tries) for each try, the
distance from the tried set T is 2. If not open, then we know that there are
no adjacent digits in the combine (take 0 and 9 as adjacent numbers). This
leaves 10*(4*5+3*4)=320 (Because for example 5 is chosen for the first digit
, then for second digit being 2,3,7 or 8, there are 5 choices for the 3rd
digit while for second being 9,0,1, there are 4 choices for 3rd digit).
(3) Try 024,...,913 and 086,...,975. After this we know no consecutive
digits are less than 2 away. This leaves 120 (from simulation. I do not know
how to derive this number)
(4) Try 037,...926 and 073,...962. After this 40 is left
(5) Try 041,152,...930. After this 10 is left
(6) Try what is left. They are 069,170,...968
Overall, if we divide the trials by groups of 10 numbers, then at most 90
combines are tried. The combines left after each group are
1000 (after 0 trial), 720 (after 10 trial), 500,320,200,120,70,40,10. It
decreases in a descending speed. The average trial is
28*(1+...+10)+22*(11+...+20)+18*(21+...+30)+12*(31+...+40)+8*(41+...+50)+5*(
51+...+60)+3*(61+...+70+71+...+80)+1*(81+...+90) divided by 1000, which is
25.3. | s*****a
发帖数: 353 | 8 I validated this set and after trying these numbers, 136 combines were left.
【在 q*********i 的大作中提到】
: (made a mistake in last one, the following should be correct)
: try the following 50 numbers
: 000 101 202 303 404
: 120 221 322 423 024
: 240 341 442 043 144
: 360 461 062 163 264
: 480 081 182 283 384
: 515 616 717 818 919
: 635 736 837 938 539
: 755 856 957 558 659
| f*******s
发帖数: 57 | 9 Here is a set of 50 numbers that seems to work (hope there is no flaw here),
don't know whether and how to prove it is optimal yet: Consider all the
triplet (x, y, z) such that
(x - y) % 2 == 0 and z = (x + y + x % 2) % 10.
By construction, there do not exist two triplets in the set that have more
than two identical numbers (in the same positions). This implies that for
any odd x, odd y and odd z, there is at least one triplet in the set that is
(x, *, z), and there is at least one triple in the set that is (*, y, z).
Similarly for any even x, even y and even z.
If the password (u,v,w) has the pattern of (odd,odd,*), (even,even,*),
clearly the above set will contain exact one number whose first two elements
are u and v.
If u is odd and v is even, depends on whether w is odd or even, we will have
match on u and w or on v and w.
two
that
【在 t*******8 的大作中提到】
: There is a lock with the password between 000-999. But we could use only two
: digits to open the lock. For example, if the password is 123, the lock is
: open when you try 1*3, or *23, or 12*. questions: a) compose a strategy that
: the try number of opening the lock is the smallest one under the worst
: situation b) Prove that your strategy is optimal
|
|
