Geodesic
Determination of a Subset from Certain Combinatorial Properties
Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 42-48

Voir la notice de l'article provenant de la source Cambridge University Press

Let N be a finite set of n elements. A collection {S1, S2, ... , Sm} of subsets of N is called a determining collection if an arbitrary subset T of N is uniquely determined by the cardinalities of the intersections Si ⋂ T, 1 ≤ i ≤ m. The purpose of this paper is to study the minimum value D(n) of m for which a determining collection of m subsets exists.This problem can be expressed as a coin-weighing problem (1; 7).In a recent paper Cantor (1) showed that D(n) = O(n/log log n), thus proving a conjecture of N. J. Fine (3) that D(n) = o(n). More recently Erdös and Rényi (2), Söderberg and Shapiro (7), Berlekamp, Mills, and Leo Moser have independently found proofs that D(n) = O(n/log n). 
Cantor, David G.; Mills, W. H. Determination of a Subset from Certain Combinatorial Properties. Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 42-48. doi: 10.4153/CJM-1966-007-2
@article{10_4153_CJM_1966_007_2,
     author = {Cantor, David G. and Mills, W. H.},
     title = {Determination of a {Subset} from {Certain} {Combinatorial} {Properties}},
     journal = {Canadian journal of mathematics},
     pages = {42--48},
     year = {1966},
     volume = {18},
     number = {1},
     doi = {10.4153/CJM-1966-007-2},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-007-2/}
}
TY  - JOUR
AU  - Cantor, David G.
AU  - Mills, W. H.
TI  - Determination of a Subset from Certain Combinatorial Properties
JO  - Canadian journal of mathematics
PY  - 1966
SP  - 42
EP  - 48
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-007-2/
DO  - 10.4153/CJM-1966-007-2
ID  - 10_4153_CJM_1966_007_2
ER  - 
%0 Journal Article
%A Cantor, David G.
%A Mills, W. H.
%T Determination of a Subset from Certain Combinatorial Properties
%J Canadian journal of mathematics
%D 1966
%P 42-48
%V 18
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-007-2/
%R 10.4153/CJM-1966-007-2
%F 10_4153_CJM_1966_007_2

[1] 1. Cantor, David G., Determining a set from the cardinalities of its intersections with other sets, Can. J. Math., 16 (1964), 94–97. Google Scholar

[2] 2. Erdös, P. and Rényi, A., On two problems of information theory, Publ. Hung. Acad. Sci., 8 (1963), 241–254. Google Scholar

[3] 3. Fine, N. J., Solution E1399, Amer. Math. Monthly, 67 (1960), 697–698. Google Scholar

[4] 4. Lindström, B., On a combinatory detection problem, Publ. Hung. Acad. Sci., 9 (1964), 195–207. Google Scholar

[5] 5. Lindström, B., On a combinatorial problem in number theory, Can. Math. Bull., 4(1965), 477–490. Google Scholar

[6] 6. Ryser, H. J., Maximal determinants in combinatorial investigations, Can. J. Math., 8 (1956), 245–249. Google Scholar

[7] 7. Söderberg, Staffan and Shapiro, H. S., A combinatory detection problem, Amer. Math. Monthly, 70 (1963), 1066–1070. Google Scholar

Cité par Sources :