Question

計算機內部都以二進制字符表示信息．若u=（a₁，a₂，…，a_n），其中a_i=0或1（i=1，2，…，n），則稱u是長度為n的字節；設u=（a₁，a₂，…，a_n），v=（b₁，b₂，…，b_n），用d（u，v）表示滿足a_i≠b_i（i=1，2，…，n）的i的個數．如u=（0，0，0，1），v=（1，0，0，1），則d（u，v）=1．現給出以下三個命題：
①若u=（a₁，a₂，…，a_n），v=（b₁，b₂，…，b_n），則0≤d（u，v）≤n；
②對于給定的長度為n的字節u，滿足d（u，v）=n-1的長度為n的字節v共有n-1個；
③對于任意的長度都為n的字節u，v，w，恒有d（u，v）≤d（w，u）+d（w，v）．
則其中真命題的序號是（　　）

A．①

B．①②

C．①③

D．②③

Answer 1

①我們知道：u=（a₁，a₂，…，a_n）與v=（b₁，b₂，…，b_n）中，a_i與b_i（1≤i≤n）可都不相同，亦可都相同，
故0≤d（u，v）≤n，因此①正確；
②設若u=（a₁，a₂，…，a_n），其中a_i=0或1（i=1，2，…，n），令v=（b₁，b₂，…，b_n），其中b_i=0或1（i=1，2，…，n），
我們知道：當|a_i-b_i|=0時，表示 a_i與b_i相同；而當|a_i-b_i|=1時，表示 a_i與b_i不相同．
已知v滿足d（u，v）=n-1，表示|a_i-b_i|=1中的i的個數為n-1，而|a_i-b_i|=0中i的個數為1，
故適合條件的v的個數為n，因此②不正確．
③設u=（a₁，a₂，…，a_n），v=（b₁，b₂，…，b_n），w=（c₁，c₂，…，c_n），
d（u，v）=h，d（w，u）=k，d（w，v）=m．
由d（w，u）=k表示|a_i-c_i|=1中i的個數為k；由d（w，v）=m表示|b_i-c_i|=1中i的個數為m；
由d（u，v）=h表示|a_i-b_i|=1中i的個數為h．
設t是使|a_i-c_i|=|b_i-c_i|=0成立的i的個數，可驗證無論c_i=0，還是c_i=1，
則都有||a_i-c_i|-|b_i-c_i||=|a_i-b_i|=0，
∴h=k+m-2t，∴h≤k+m．
因此對于任意的長度都為n的字節u，v，w，恒有d（u，v）≤d（w，u）+d（w，v）．所以③正確．
故選C．