Solve the Pigeonhole Principle Problem w/ PHP

  • Context: MHB 
  • Thread starter Thread starter magneto1
  • Start date Start date
  • Tags Tags
    Principle
Click For Summary
SUMMARY

The discussion focuses on solving the Pigeonhole Principle problem using PHP, specifically for a set of 16 distinct positive integers. It establishes that for non-empty, disjoint subsets A and B of equal size, the sums of their reciprocals can be made to differ by less than 0.0025. The analysis shows that by partitioning the interval [0, 3.4] into 12,869 equal parts, the Pigeonhole Principle guarantees that at least two subsets will have their sums fall into the same partition, leading to the desired result. The conclusion emphasizes the effectiveness of this approach in demonstrating the principle's application in combinatorial problems.

PREREQUISITES
  • Understanding of the Pigeonhole Principle
  • Familiarity with combinatorial mathematics
  • Basic knowledge of PHP programming
  • Concept of subsets and their properties
NEXT STEPS
  • Implement the Pigeonhole Principle in PHP for different set sizes
  • Explore combinatorial algorithms for subset generation in PHP
  • Study the mathematical properties of harmonic sums
  • Learn about optimization techniques in PHP for performance improvement
USEFUL FOR

Mathematicians, PHP developers, and computer scientists interested in combinatorial algorithms and their practical applications in programming.

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.
 

Similar threads

  • · Replies 20 ·
Replies
20
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 4 ·
Replies
4
Views
4K
Replies
8
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 4 ·
Replies
4
Views
4K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 69 ·
3
Replies
69
Views
9K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K