**Reference**:- Stelian Ciurea, Erik D. Demaine, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu, “Finding a Divisible Pair”,
*ACM SIGSAM Bulletin*, volume 38, number 3, September 2004, pages 98–100. **Abstract**:-
Our problem is the natural algorithmic version of a classic
mathematical result: any
(
*n*+ 1)-subset of {1, …, 2*n*} contains a pair of divisible numbers. How do we actually find such a pair? If the subset is accessible only through a membership oracle, we show a lower bound of (4/3)*n*−*O*(1) and an almost matching upper bound of (4/3 + 1/24)*n*+*O*(1) on the number of queries necessary in the worst case. **Length**:- The paper is 2 pages.
**Availability**:- The paper is available in PostScript (105k), gzipped PostScript (43k), and PDF (60k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Yogi_FUN2004 (Finding a Divisible Pair and a Good Wooden Fence)

See also other papers by Erik Demaine.

Last updated May 28, 2024 by Erik Demaine.