Paper by Erik D. Demaine

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.

BibTeX

@Article{DivisiblePair_SIGSAM,
  AUTHOR        = {Stelian Ciurea and Erik D. Demaine and
                   Corina E. P\v{a}tra\c{s}cu and Mihai P\v{a}tra\c{s}cu},
  TITLE         = {Finding a Divisible Pair},
  JOURNAL       = {ACM SIGSAM Bulletin},
  VOLUME        = 38,
  NUMBER        = 3,
  MONTH         = {September},
  YEAR          = 2004,
  PAGES         = {98--100},

  papers        = {Yogi_FUN2004},
  length        = {2 pages},
  withstudent   = 1,
  unrefereed    = 1,
}

Abstract:

Our problem is the natural algorithmic version of a classic mathematical result: any (n + 1)-subset of {1, …, 2n} 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)