The blog is many screens long, but the same poster (he didn't say how he found it) shows that f(8) <= 16: [image: $17,23,25,32,37,38,47,52,53,58,67,68,73,80,82,88.$] [image: $23+82=80+25=88+17=32+73=52+53=38+67=68+37=47+58,$] [image: $23+80+17=25+37+58=88+32=52+68=73+47=82+38=53+67,$] [image: $82+58=88+52=25+68+47=23+80+37=73+67=17+32+53+38,$] [image: $53+68+47=23+82+25+38=80+88=73+37+58=17+32+52+67.$] On Tue, Dec 19, 2017 at 10:41 AM, Victor Miller <victorsmiller@gmail.com> wrote:
And for f(8) <= 17 (also from the Russian discussion):
[image: $36,35,57,48,105,50,62,15,63,55,42,17,43,34,58,47,73.$]
[image: $36+35+34=50+55=15+17+73=57+48=58+47=105=63+42=62+43,$] [image: $62+58=105+15=48+55+17=36+50+34=47+73=35+42+43=57+63,$] [image: $36+57+47=50+17+73=35+105=55+42+43=48+34+58=62+15+63,$] [image: $105+63=57+62+15+34=36+35+55+42=48+47+73=50+17+43+58.$]
On Tue, Dec 19, 2017 at 10:38 AM, Victor Miller <victorsmiller@gmail.com> wrote:
I was wrong. The Russian discussion group gave the following
[image: $F(7) \leq 15$]: [image: $(60, 5+5+50, 34+26, 15+5+40, 44+16, 54+6, 36+24)/420=(1,1,1,1,1,1,1)/7$] [image: $(60+5+5, 50+15+5, 34+36, 6+24+40, 44+26, 54+16)/420=(1,1,1,1,1,1)/6$] [image: $(60+24, 50+34, 16+36+6+26, 44+40, 54+15+5+5+5)/420=(1,1,1,1,1)/5$] [image: $(60+40+5, 50+34+16+5, 26+5+24+44+6, 54+15+36)/420=(1,1,1,1)/4$]
On Tue, Dec 19, 2017 at 10:35 AM, Victor Miller <victorsmiller@gmail.com> wrote:
This was discussed on seq-fan by Max Alexeyev in January 2016. Max did something similar to what I did -- he wrote a MIP (mixed integer program). However, he said that he needed to run Gurobi (pretty much equivalent to cplex) on 40 cores for one day to get f(6). It only took me 80 seconds on my workstation (it has 4 cores) with cplex. I think that the improvement in my code is that it uses symmetry breaking (which is really essential here). However, I let it run overnight (it's still running) for f(7) and it hasn't even found a feasible solution. It looks like this was also discussed (in Russian -- and mine is rather rusty) on http://dxdy.ru/topic102739.html
I was thinking about the problem last night and came up with the following:
1) As has been stated before one only needs to look at the division condition for ceil(n/2) <= m <= n. 2) For a putative value of k, one can enumerate all possible set partitions for each of the above m -- i.e. one needs to partition {1,...,k} into m subsets. 3) Once one has fixed a partition, the set of solutions compatible with that partition is given by a system of linear equations with 0/1 coefficients. Is the coefficient matrix *totally unimodular* -- i.e. every square submatrix has determinant 0, +/-1? 4) For each fixed m, it seems reasonable that m-1 of the equations might be independent. So, for example, with n=5 we would have (3-1) + (4-1) + (5-1) = 9 independent equations. Since we've established that f(5) = 9, it might be the case there there are only a finite number of solutions with k=9 (at most 1 for each possible partition). In fact, I keep getting the same solution when I rerun cplex. Cplex uses randomization all the time, so that if there is another solution it might well have turned up. It seems reasonable to me that if two of the m's are not relatively prime that there is some redundancy. So for n=6 the above reasoning would give (4-1) + (5-1) + (6-1) = 12, but I would like to subtract 1 since gcd(4,6) = 2. This reasoning would give the following for n=7, (4-1) + (5-1) + (6-1) + (7-1) - 1 = 17 for f(7).
On Tue, Dec 19, 2017 at 10:10 AM, Allan Wechsler <acwacw@gmail.com> wrote:
It certainly looks like it. I somehow overlooked Don's post. So I lose the bet in my previous post -- I must somehow have also overlooked A265286.
OEIS gives f(7) = 14, f(8) = 16. Perhaps we could establish f(9)?
The sequence is growing far more slowly than I would have expected. I am very surprised that it only takes 3 more cuts to serve 7 people than it does to serve 6.
On Mon, Dec 18, 2017 at 11:07 PM, James Propp <jamespropp@gmail.com> wrote:
I am finding this discussion confusing. Aren't we agreed that the sequence I called f(n) is the one called A265286 (as Don Reble pointed out)?
Jim
On Monday, December 18, 2017, Allan Wechsler <acwacw@gmail.com> wrote:
OEIS has 18 matches for (1,2,4,6,9,11); at the moment I am betting that none of them are "the answer"; if any one of them is in fact the f(n) we have been discussing, it will take nontrivial mathematics to prove it.
On Mon, Dec 18, 2017 at 4:29 PM, <rcs@xmission.com> wrote:
> We can extend Victor's 11 piece solution for n=6 to a 17-piece solution > for n=7. > > There's an inequality: F(n) <= F(n-1)+n-1 > Arrange all the pieces along the line [0,1] in any order. > Make n-1 cuts at k/n for 0<k<n. > > I'd like to say F(n) <= F(n-1) + phi(n), but I can only get > > F(n) <= F(n-1) + (n - maximum-proper-divisor(n)) > > I'm allowing 1 as a proper divisor, but not n. > To get the inequality: let m = max-prop-div(n). > Arrange the pieces in the n-1 solution into size 1/m groups. > Place these along the [0,1] line. > Then some of the cuts for k/n will overlap all the cuts for the 1/m > grouping. > > We can say F(n) <= sum(phi(n)). In this case, just make all > the cuts for k/j with (k,j)=1 and 0<=k<j<=n. (This is just > the Farey series for n, excluding 1/1.) With no rearrangement > of the pieces, when we get around to making the cuts for k/n, > cuts will already exist for all proper divisors d|n. > The sum should be roughly n(n+1)/2 * 6/pi^2. > In this solution, the smallest piece is 1/n(n-1). > The common denominator for all the pieces is indeed LCM(1...n), > very roughly e^n. > > Rich > > ----------- > > Quoting Tom Karzes <karzes@sonic.net>: > >> For what it's worth, here's a naive, almost-certainly-suboptimal >> 18-part solution for n=7 corresponding to the bound of 18 given by >> https://oeis.org/A092249 >> >> 1/42, 1/42, 1/35, 1/35, 1/30, 1/30, 1/28, 1/28, 1/21, 1/21, >> 1/20, 1/20, 1/15, 1/15, 1/14, 1/14, 1/7, 1/7 >> >> Tom >> >> Victor Miller writes: >> > Tom, Thanks. I'm trying f(7) now, but it looks really hard. I give a >> > tentative upper bound for the number of parts, and let it optimize >> it. I >> > suspect that the previously conjectured upper bound from A092249 isn't >> > right. Just to see if I could give it a much larger space to explore, >> I >> > gave it a tentative upper bound of 112 and after a few minutes it >> hasn't >> > even found any feasible solution! The only thing that it's proved so >> far >> > is that f(7) >= 12. >> > >> > Victor >> > >> > On Mon, Dec 18, 2017 at 2:57 PM, Tom Karzes <karzes@sonic.net
wrote: >> > >> > > Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution >> > > beats a simple union of divisions into equal parts! >> > > >> > > And your 11-part solution for f(6) also beats a simple union of >> divisions >> > > into equal parts! >> > > >> > > Have you tried f(7), or is that past what it can handle? >> > > >> > > Tom >> > > >> > > Victor Miller writes: >> > > > Whoops, in f(6) threre should have been 2 parts of size 7/60: >> 1/30, >> > > 1/30, >> > > > 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6 >> > > > >> > > > On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller < >> victorsmiller@gmail.com >> > > > >> > > > wrote: >> > > > >> > > > > I coded the model in cplex (I'll give the slightly corrected >> version >> > > > > subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, >> 1/20, 1/12, >> > > > > 1/10, 3/20, 1/6, 1/5, 1/5 >> > > > > and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, >> 7/60, >> > > 1/6, >> > > > > 1/6 >> > > > > >> > > > > On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > > wrote: >> > > > > >> > > > >> Slight correction in my last post. Here is the correct >> version. >> > > > >> Tomorrow, when I get into work, I'll give the f(5) problem to >> cplex >> > > and >> > > > >> report back. >> > > > >> >> > > > >> Victor >> > > > >> >> > > > >> Solve the following problem -- given a positive integer n
>> 1, and a >> > > > >> positive integer k decide if there are k reals x[1], ..., >> x[k] >= 0 >> > > > >> such that, for every integer i > 1, there are y[i,r,j], j=1, >> ..., k, >> > > > >> r=1,...,i in {0,1} >> > > > >> >> > > > >> 1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 >> for >> > > each i >> > > > >> 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i >> > > > >> 3) x[j] in [0, 1/n] for j=1,..., k >> > > > >> >> > > > >> We can linearize (2) by using big-M: >> > > > >> >> > > > >> z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n] >> > > > >> >> > > > >> (1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * >> (1-y[i,r,j]) >> > > > >> >> > > > >> There's lots of symmetries. We can (partially) break them by >> > > insisting >> > > > >> that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), >> j=1,...,k >> > > are >> > > > >> lexicographically increasing. >> > > > >> >> > > > >> Also, as remarked before, we don't need to put any conditions >> for i, >> > > for >> > > > >> which a non-trivial multiple is <=n. >> > > > >> >> > > > >> >> > > > >> On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > >> wrote: >> > > > >> >> > > > >>> More specifically let x[1], ..., x[k] be non-negative >> variables <= >> > > 1, >> > > > >>> and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose >> value >> > > of 1 >> > > > >>> means that x[i] contributes to the j-th 1/i. We then have >> > > > >>> 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 >> (or >> > > maybe <= >> > > > >>> 1 if you want to omit that piece). You might object that >> sum(j) >> > > y[i,j] * >> > > > >>> x[j] isn't linear. You can fix this by introducting new >> variables >> > > > >>> z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can >> enforce this >> > > by >> > > > >>> z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). >> So >> > > giving >> > > > >>> this to a MIP solver is a finite algorithm for the problem. >> > > > >>> >> > > > >>> On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller < >> > > victorsmiller@gmail.com> >> > > > >>> wrote: >> > > > >>> >> > > > >>>> Here's a proof that there are optimal rational solutions: >> For a >> > > > >>>> putatitve solution to f(n) = k, you can write a mixed integer >> > > program which >> > > > >>>> will say whether or not there is such a solution. The only >> integer >> > > > >>>> variables are 0/1 variables which indicate whether "piece" i >> > > contributes to >> > > > >>>> a particular sum producing 1/n. There are only a finite >> number of >> > > settings >> > > > >>>> for these. Once you have done this the remainder is a >> polytope >> > > bounded by >> > > > >>>> half spaces with integer coefficients. So the vertices of >> the >> > > polytope >> > > > >>>> have rational coefficients. An optimal solution must be >> among >> > > these. >> > > > >>>> >> > > > >>>> On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes < >> karzes@sonic.net> >> > > wrote: >> > > > >>>> >> > > > >>>>> Can you prove that it's safe to ignore irrational solutions? >> > > Here's a >> > > > >>>>> (non-optimal) irrational solution for f(3), using 5 >> component >> > > values: >> > > > >>>>> >> > > > >>>>> 1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 >> > > > >>>>> 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 >> > > > >>>>> 1/3 = 1/3 >> > > > >>>>> >> > > > >>>>> 1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 >> > > > >>>>> 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - >> 4)/24 >> > > > >>>>> >> > > > >>>>> Can we always do as well (or better) using only rational >> component >> > > > >>>>> values? >> > > > >>>>> I suspect the answer is yes. >> > > > >>>>> >> > > > >>>>> Note that the example above has the general form: >> > > > >>>>> >> > > > >>>>> 1/3 = a + (1/3 - a) >> > > > >>>>> 1/3 = (1/2 - a) + (a - 1/6) >> > > > >>>>> 1/3 = 1/3 >> > > > >>>>> >> > > > >>>>> 1/2 = a + (1/2 - a) >> > > > >>>>> 1/2 = 1/3 + (1/3 - a) + (a - 1/6) >> > > > >>>>> >> > > > >>>>> This works for any value of "a" that doesn't produce zero or >> > > negative >> > > > >>>>> values. In particular, "a" can be given a rational >> value. Is it >> > > the >> > > > >>>>> case that any solution involving irrational values can be >> > > decomposed >> > > > >>>>> into something like this, which in turn can be converted >> into a >> > > > >>>>> rational solution? >> > > > >>>>> >> > > > >>>>> Tom >> > > > >>>>> >> > > > >>>>> >> > > > >>>>> Allan Wechsler writes: >> > > > >>>>> > I was challenging myself to try to think of any finite >> > > algorithm, >> > > > >>>>> be it >> > > > >>>>> > ever so expensive and cumbersome, that would settle the >> > > question of >> > > > >>>>> whether >> > > > >>>>> > p pieces suffices for a given n. A useful lemma would >> be that >> > > if it >> > > > >>>>> can be >> > > > >>>>> > done in p pieces, then it can be done with pieces whose >> > > > >>>>> denominaters divide >> > > > >>>>> > n!. (LCM(1,...,n) would be even stronger, but for my >> purposes >> > > it >> > > > >>>>> doesn't >> > > > >>>>> > matter how weak this lemma is.) >> > > > >>>>> > >> > > > >>>>> > Then, we could say, "Iterate over all partitions of n! >> into p >> > > > >>>>> parts, and >> > > > >>>>> > for each such partition, check to see if it works, using >> the >> > > > >>>>> partition as >> > > > >>>>> > the numerators of fractions whose denominators are all >> n!." >> > > This >> > > > >>>>> would be >> > > > >>>>> > heinously expensive but it would at least provide an >> upper >> > > bound on >> > > > >>>>> how >> > > > >>>>> > much computational work we have to do. >> > > > >>>>> > >> > > > >>>>> > But I can't even prove the lemma. >> > > > >>>>> > >> > > > >>>>> >> > > >> > > _______________________________________________ >> > > math-fun mailing list >> > > math-fun@mailman.xmission.com >> > > https://mailman.xmission.com/c gi-bin/mailman/listinfo/math-fun >> > > >> > _______________________________________________ >> > math-fun mailing list >> > math-fun@mailman.xmission.com >> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-f un >> > >> >> -- >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> >> > > > _______________________________________________ > math-fun mailing list > math-fun@mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun