OFFSET
1,3
COMMENTS
A cake of size 1 is to be divided between n people. The cutter iterates the following procedure: to obtain a new piece of the cake, he cuts the biggest piece into two subpieces (if several pieces are biggest ex aequo, he cuts just one of them); the cut is biased in the proportions t versus 1-t, where t is a constant real number between 1/2 and 1. We will assume that t is transcendental. After the procedure is applied, each piece's size is clearly t^x*(1-t)^y for some (x,y), ordered pair of nonnegative integers. The obtained ordered multiset of t^x*(1-t)^y polynomials depends on t and n; we shall call this the f(t,n) configuration. By definition a(n) is Card({f(t,n); t varies}), i.e., the number of configurations that the procedure for n people can possibly generate, when one does not know the value of t before it starts.
The problem boils down to a geometrical one, where one has to compare the Y-coordinates of rotated lattice points, the angle of rotation depending on t: tan(angle)=log(1-t)/log(t). See SVG link.
LINKS
EXAMPLE
=========================================================================
1 | 2 | 3 | 4 |
=========================================================================
| | | t^3 > 1-t > t*(1-t) > t^2*(1-t) |
| | t^2 > 1-t > t*(1-t) +-----------------------------------+
| | | 1-t > t^3 > t*(1-t) > t^2*(1-t) |
1 | t > 1-t +---------------------+-----------------------------------+
| | 1-t > t^2 > t*(1-t) | t^2 > t*(1-t) = t*(1-t) > (1-t)^2 |
=========================================================================
n=1: the whole cake is the only piece, a(1) = 1.
n=2: the first division necessarily divided 1 into t and 1-t; t and 1-t are necessarily ordered this way: t > 1-t. a(2) = 1.
n=3: the second division necessarily divided t into t^2 and t*(1-t); t*(1-t) is necessarily smaller than both t^2 and 1-t; but either t^2 or 1-t may be the biggest: it depends on whether t < 1/phi or t > 1/phi, where phi denotes the golden ratio; so there are two cases and a(3) = 2.
n=4:
* in the case when t^2 > 1-t, the third division divided t^2 into t^3 and t^2*(1-t); t^2*(1-t) is necessarily smaller than t*(1-t) which is necessarily smaller than both t^3 and 1-t; but either t^3 or 1-t may be the biggest: it depends on whether t < 1/psi or t > 1/psi, where psi denotes the constant described in A092586 (sometimes called the supergolden ratio); so there are two subcases;
* in the case when 1-t > t^2, the third division divided 1-t into t*(1-t) and (1-t)^2; the order of the elements is fully determined without requiring new assumptions on t, so there is just one subcase;
* gathering all subcases contributions yields a(4) = 3.
PROG
(Java) // See Rousseau link.
CROSSREFS
KEYWORD
nonn
AUTHOR
Luc Rousseau, Feb 13 2021
STATUS
approved