Solve the Pigeonhole Principle Problem w/ PHP

  • Context:
  • Thread starter Thread starter magneto1
  • Start date Start date
  • Tags Tags
    Principle
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 2K views
magneto1
Messages
100
Reaction score
0
Ran across this problem reading another forum, and wonder if PHP allies here.

Given a set $X$ of 16 positive distinct integers, you can find non-empty, disjoint subsets $A, B \subset X$ such
that $A$ and $B$ have the same number of elements, and $|\alpha - \beta| < 0.0025$, where $\alpha = \sum_{a \in A} \frac 1a$, and $\beta = \sum_{b \in B} \frac 1b$.
 
Physics news on Phys.org
magneto said:
Ran across this problem reading another forum, and wonder if PHP allies here.

Given a set $X$ of 16 positive distinct integers, you can find non-empty, disjoint subsets $A, B \subset X$ such
that $A$ and $B$ have the same number of elements, and $|\alpha - \beta| < 0.0025$, where $\alpha = \sum_{a \in A} \frac 1a$, and $\beta = \sum_{b \in B} \frac 1b$.
Given any subset $S$ of $X$, we have

$$
\sum_{s\in S}\frac{1}{s} \leq \sum_{x\in X} \frac{1}{x} \leq \frac{1}{1}+\frac{1}{2}+ \frac{1}{3}+\cdots +\frac{1}{16} \leq 3.4
$$

Let us denote the set of all the $8$ element subsets of $X$ by $X_8$.
Now there are $\binom{16}{8}=12,870$ distinct members in $X_8$.

Partition the interval $[0,3.4]$ into $12,869$ equal parts. So each part has length no more than $0.00027$.

By pigeon hole principle, some two members of $X_8$ will have their corresponding sums falling in a common partition. Thus we have $|\alpha -\beta|<0.00027$ for some $\alpha = \sum_{a\in A}1/a$ and $\beta = \sum_{b\in B}1/b$, where $A, B\in X_8$.

If $A$ and $B$ are not disjoint, then we consider $A'=A-B$ and $B'=B-A$. Thus we again have $|A'|=|B'|$, and

$$\sum_{a'\in A'}\frac{1}{a'}-\sum_{b'\in B'}\frac{1}{b'} = \alpha -\beta$$

This bound is better than the one the question asks for. May be I made some calculation error. I cannot find any errors.