3
$\begingroup$

Given a finite set $X$ of real numbers greater than one. I'm looking for disjoint sets $A,B$ such that $X=A\cup B$ and such that $$\prod_{x\in A}x\leq\prod_{x\in B}x\,.$$ Especially am I interested of those pair of sets $A,B$ with a maximal product for the elements in $A$, so that the $A$-product is maximal for the set $X$.

This give arise to a combinatorial problem: if $X=\{a,b\},\;a<b$ there is only one possibility. If $X=\{a,b,c\},\;a<b<c$ there are two maximal possibilities: $ab\leq c\:$ and $\:c\leq ab \:$ since always $a<b<ab<ac<bc$.

In the table below '|' means 'or' and for example 'ab c' stands for:

that $A=\{a,b\}$, $\:B=\{c\}$, that there are different real numbers $a<b<c$ greater than one such that $\:ab\leq c\:$ and such that the partition is a maximal one.

a<b                a b
a<b<c              ab c | c ab
a<b<c<d            abc d | bc ad | ac bd | d abc
a<b<c<d<e          abcd e | bcd ae | acd be | abd ce | abc de | ...?
a<b<c<d<e<f        ?

How many possible combinations are there for sets with $5,6,\dots,n$ elements?

Hint: it may be more easy to find the impossible combinations $\;a_1\cdots a_i\:\:\: b_1\cdots b_j\;$ that doesn't match for any numbers $\;a_1,\dots ,a_i,b_1,\dots ,b_j\;$ when substituted.


As joriki pointed out there is an equivalent formulation with partitions of sets of real numbers greater than zero such that: $$\sum_{x\in A}x\leq\sum_{x\in B}x\,.$$

$\endgroup$
  • 2
    $\begingroup$ @coffeemath: I think the idea is that a bc isn't maximal since it's dominated by b ac. $\endgroup$ – joriki Oct 8 '15 at 22:13
  • 3
    $\begingroup$ Note that you can take logarithms to get positive numbers that you want to equipartition as much as possible. $\endgroup$ – joriki Oct 8 '15 at 22:27
  • 1
    $\begingroup$ @joriki: I will try to do that. $\endgroup$ – Lehs Oct 9 '15 at 6:45
  • 1
    $\begingroup$ Please give a more descriptive title to your question. $\endgroup$ – Ethan MacBrough Oct 9 '15 at 8:15
  • 1
    $\begingroup$ From a numerical simulation, the number of candidates is $1,2,4,12,24,58,116,260$ for $n=2,\ldots,9$. This sequence isn't in OEIS. The number of admissible partitions (that satisfy the inequality but can't necessarily be maximal) is $2,5,10,22,44,93,186,386$, which is OEIS sequence A045621 and is given by $2^n-\binom n{\lfloor\frac n2\rfloor}$. If you're interested, I could explain why this is "the probability that a majority of heads had occurred at some point after $n$ flips of a fair coin", as stated in the comments section of the OEIS sequence. $\endgroup$ – joriki Oct 10 '15 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.