Timeline for Generalizing a problem to make it easier
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 13, 2011 at 9:25 | comment | added | Isaac Gorelic | The argument above suggests a fool-proof proof in the original divisibility terms: choose and fix one of the k primes. Those divisors of the full product which are not divisible by this fixed prime are "small," and those divisible are "big." The bijection is the multiplication by this prime. | |
| Sep 12, 2011 at 11:40 | comment | added | Isaac Gorelic | Re #7, the divisors of a squere-free integer. What's wrong with the following proof? By induction on k > 0, starting with the obvious case of a singleton, check that the family of all subsets of a finite k-set can be partitioned into subset-related pairs (by keeping the old arrangement + fattening the old arrangement by the new point everywhere). | |
| Nov 20, 2010 at 6:55 | comment | added | Fedor Petrov | By the way, the generalization may be stated as follows: Let A be any collection of subsets of $\\{1,2,\dots,n\\}$ s.t. if $U\in A$ and $V\subset U$, then $V\in A$. Then there exists a bijection $\pi:A\rightarrow A$ such that $V\cap \pi(V)=\emptyset$ for any $V\in A$. | |
| Nov 10, 2010 at 17:55 | comment | added | I. J. Kennedy | Yes, $f$ is a bijection. Edited. | |
| Nov 10, 2010 at 16:40 | history | edited | I. J. Kennedy | CC BY-SA 2.5 |
function -> bijection
|
| Nov 10, 2010 at 16:26 | comment | added | darij grinberg | ... instead of the lattice of divisors of $n$ we can just consider the lattice $\left\lbrace 0,1\right\rbrace^n$, and we claim that there are at least $2^k$ pairs $\left(s,t\right)\in S\times T$ with $s$ and $t$ adjacent. | |
| Nov 10, 2010 at 16:26 | comment | added | darij grinberg | There is a similar problem, by the way, with exactly the same trick: We divide the set of divisors of squarefree $n$ into two sets $S$ and $T$ of equal size, this time arbitrary (but of equal size). Then we claim that there exist at least $2^k$ pairs $\left(s,t\right)\in S\times T$ with at least one of $\frac{s}{t}$ and $\frac{t}{s}$ being a prime integer. Of course, for this problem the setting is artificial - ... | |
| Nov 10, 2010 at 16:21 | comment | added | darij grinberg | How do you define $S$ and $T$? By letting $S$ be those divisors smaller than $\sqrt n$? | |
| Nov 10, 2010 at 7:09 | history | answered | I. J. Kennedy | CC BY-SA 2.5 |