A341534 Number of possible final configurations in a biased cake-cutting procedure for n people.

1, 1, 2, 3, 5, 6, 7, 8, 11, 12, 13, 14, 16, 18, 19, 20, 22, 23, 24, 26, 27, 29, 30, 31, 32, 33, 35, 37, 38, 39, 40, 41, 43, 45, 47, 48, 49, 50, 51, 52, 53, 55, 56, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81

Offset: 1

Author

Luc Rousseau, Feb 13 2021

Keywords

• nonn

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.

Examples

			=========================================================================
  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.
		

Links

• Luc Rousseau, Java program
• Luc Rousseau, SVG illustration for n=1..10

Crossrefs

Cf. A094214, A001622 (1/phi, phi).

Cf. A263719, A092586 (1/psi, psi).

Programs

Java

// See Rousseau link.