MHB Solve the Pigeonhole Principle Problem w/ PHP

  • Thread starter Thread starter magneto1
  • Start date Start date
  • Tags Tags
    Principle
Click For Summary
The discussion revolves around applying the Pigeonhole Principle to a problem involving a set of 16 distinct positive integers. It establishes that by partitioning the interval of possible sums of the reciprocals of subsets into smaller segments, two subsets of equal size will yield similar sums within a specified range. The argument shows that if two subsets are not disjoint, adjustments can be made to maintain equal size while refining the sum comparison. The conclusion suggests that the derived bounds are tighter than initially required, indicating a potential oversight in calculations. This exploration highlights the effectiveness of combinatorial methods in solving complex mathematical problems.
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.
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.