Let $ \mathbb {R} ^{n} $ be the $ n $-dimensional Euclidean space and $ [\mathrm {e} ^{1},\mathrm {e} ^{2}] $ be the inner product of vectors $ \mathrm {e} ^{1} $ and $ \mathrm {e} ^{2} $ from $ \mathbb {R} ^{n}. $ For vectors $ \mathrm {e} =(e_{1},\dots ,e_{n})\in \mathbb {R} ^{n} $ and subsets $ E=\{\mathrm {e} ^{j}\}\subseteq \mathbb {R} ^{n}, $ the operations $ (\cdot )^{*} $ and $ (\cdot )^{+} $ are defined, respectively, as $ \mathrm {e} ^{*}=(sign(e_{i}))_{i} $ ; $ E^{*}=\{(\mathrm {e} ^{j})^{*}\} $, $ \mathrm {e} ^{+}=(|sign(e_{i})|)_{i} $, $ E^{+}=\{(\mathrm {e} ^{j})^{+}\}. $ By $ I^{n} $ we shall denote the discrete [−1; 1]-cube in $ \mathbb {R} ^{n} $; i.e., the set of all sequences of length $ n $ over the alphabet $ I=\{-1,0,1\} $ The set $ I_{t}^{n}=\{\mathrm {x} \in I^{n}|w(\mathrm {x} )\leq t\}\subseteq I^{n} $ is the discrete ball of radius $ t $ (in the Hamming metric $ w() $ ) with centre at the point $ \mathrm {0} . $ Relative weights of $ n $ objects are given by a vector $ \mathrm {x} =(x_{1},\dots ,x_{n})\in I^{n}, $ which defines the configurations of weights of the objects: the $ i $th object has standard weight if $ x_{i}=0; $ the weight of the $ i $th object is greater (smaller) by a constant (unknown) value if $ x_{i}=1 $ (respectively, $ x_{i}=-1 $). The vector $ \mathrm {x} ^{+} $ characterizes the types of objects: the standard type, the non-standard type (i.e., configurations of types), and it does not contain information about relative weights of non-standard objects.
A weighing (a check) is given by a vector $ \mathrm {h} \in I^{n}; $ the result of a weighing for a situation $ \mathrm {x} \in I^{n} $ is $ s(\mathrm {x} ;\mathrm {h} )=sign([\mathrm {x} ;\mathrm {h} ]). $ The weighing given by a vector $ \mathrm {h} =(h_{1},\dots ,h_{n}) $ has the following interpretation: for a given check the $ i $th object participates in the weighing if $ h_{i}\neq 0 $; it is put on the left balance pan if $ h_{i}<0 $ and is put on the right pan if $ h_{i}>0. $ For each weighing $ \mathrm {h} $, both pans should contain the same number of objects: if on some pan the number of objects is smaller than as it should be, then it receives some $ r(\mathrm {h} )=[\mathrm {h} ;1,\dots ,1] $ reference objects. The result of a weighing $ s(\mathrm {x} ;\mathrm {h} ) $ describes the following cases: the balance if $ s(\mathrm {x} ;\mathrm {h} )=0 $, the left pan outweighs the right one if $ s(\mathrm {x} ;\mathrm {h} )=-1 $, and the right pan outweighs the left one if $ s(\mathrm {x} ;\mathrm {h} )=1. $ The incompleteness of initial information about the distribution of weights of a group of objects is characterized by the set of admissible distributions of weights of objects $ Z\subseteq I^{n}, $ which is also called the set of admissible situations, the elements of $ z\in Z $ are called admissible situations.
Each weighing $ \mathrm {h} $ induces the partition of the set $ I^{n} $ by the plane (hyperplane ) $ [\mathrm {x} ;\mathrm {h} ]=0 $ into three parts $ W(s|I^{n};\mathrm {h} )=\{\mathrm {x} \in I^{n}|s(\mathrm {x} ;\mathrm {h} )=s\} $, $ s\in I, $ and defines the corresponding partition of the set $ Z=W(0|Z,\mathrm {h} )+W(1|Z,\mathrm {h} )+W(-1|Z,\mathrm {h} ), $ where $ W(s|Z,\mathrm {h} )=W(s|I^{n},\mathrm {h} )\cap Z. $
Definition 1. A weighing algorithm (WA) $ {\mathcal {A}} $ of length $ m $ is a sequence $ {\mathcal {A}}=<\mathrm {A} _{1},\dots ,\mathrm {A} _{m}>, $ where $ \mathrm {A} _{j}:I^{j-1}\to I^{n} $ is the function determining the check $ \mathrm {h} ^{j}=\mathrm {A} _{j}(s^{j-1});\mathrm {h} ^{j}\in I^{n}, $ at each $ j $th step, $ j=1,2,\dots ,m, $ of the algorithm from the results of $ \mathrm {s} ^{j-1}=(s_{1},\dots ,s_{j-1})\in I^{j-1} $ weighings at the previous steps ( $ \mathrm {h} ^{1}=\mathrm {A} _{1}() $ is a given initial check).
Let $ S(Z,{\mathcal {A}}) $ be the set of all $ (Z,{\mathcal {A}}) $-syndromes and $ W(s|{\mathcal {A}})\subseteq I $ be the set of situations with the same syndrome $ s $; i.e., $ W(s|{\mathcal {A}})=\{\mathrm {z} \in I^{m}|s(z|{\mathcal {A}})=s\} $; $ W(s|Z;{\mathcal {A}})=W(s|{\mathcal {A}})\cap Z. $
Definition 2. A WA $ {\mathcal {A}} $ is said to: a) identify the situations in a set $ Z $ if the condition $ |W(s|Z,{\mathcal {A}})|=1 $ is satisfied for all $ s\in S(Z{\mathcal {A}}); $ b) identify the types of objects in a set $ Z $ if the condition $ |W^{+}(s|Z{\mathcal {A}})|=1 $ is satisfied for all $ s\in S(Z{\mathcal {A}}). $
It is proved in [4] that for so-called suitable sets $ Z $ an algorithm of identification the types identifies also the situations in $ Z. $
As an example the perfect dynamic (two-cascade) algorithms with parameters $ n=11,m=5,t=2 $ are constructed in [4] which correspond to the parameters of the perfect ternary Golay code (Virtakallio-Golay code). At the same time, it is established that a static WA (i.e. weighting code) with the same parameters does not exist.
Each of these algorithms using 5 weighings finds among 11 coins up to two counterfeit coins which could be heavier or lighter than real coins by the same value. In this case the uncertainty domain (the set of admissible situations) contains $ 1+2C_{11}^{1}+2^{2}C_{11}^{2}=3^{5} $ situations, i.e. the constructed WA lies on the Hamming bound for $ t=2 $ and in this sense is perfect.
To date it is not known whether there are other perfect WA that identify the situations in $ I_{t}^{n} $ for some values of $ n,t $. Moreover, it is not known whether for some $ t>2 $ there exist solutions for the equation $ \sum _{i=0}^{t}2^{i}C_{n}^{i}=3^{m} $ (corresponding to the Hamming bound for ternary codes) which is, obviously, necessary for the existence of a perfect WA. It is only known that for $ t=1 $ there are no perfect WA, and for $ t=2 $ this equation has the unique nontrivial solution $ n=11,m=5 $ which determines the parameters of the constructed perfect WA.
hbghlyj
发表于 2024-9-10 12:03
