cp's OEIS Frontend

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

%I A341534 #22 Jan 06 2025 21:46:44
%S A341534 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,
%T A341534 33,35,37,38,39,40,41,43,45,47,48,49,50,51,52,53,55,56,58,59,60,61,62,
%U A341534 64,66,67,68,69,71,72,74,75,76,77,78,79,80,81
%N A341534 Number of possible final configurations in a biased cake-cutting procedure for n people.
%C A341534 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.
%C A341534 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.
%H A341534 Luc Rousseau, <a href="/A341534/a341534.java.txt">Java program</a>
%H A341534 Luc Rousseau, <a href="/A341534/a341534_1.svg">SVG illustration for n=1..10</a>
%e A341534 =========================================================================
%e A341534   1 |    2    |          3          |                4                  |
%e A341534 =========================================================================
%e A341534     |         |                     | t^3 > 1-t > t*(1-t) > t^2*(1-t)   |
%e A341534     |         | t^2 > 1-t > t*(1-t) +-----------------------------------+
%e A341534     |         |                     | 1-t > t^3 > t*(1-t) > t^2*(1-t)   |
%e A341534   1 | t > 1-t +---------------------+-----------------------------------+
%e A341534     |         | 1-t > t^2 > t*(1-t) | t^2 > t*(1-t) = t*(1-t) > (1-t)^2 |
%e A341534 =========================================================================
%e A341534 n=1: the whole cake is the only piece, a(1) = 1.
%e A341534 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.
%e A341534 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.
%e A341534 n=4:
%e A341534   * 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;
%e A341534   * 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;
%e A341534   * gathering all subcases contributions yields a(4) = 3.
%o A341534 (Java) // See Rousseau link.
%Y A341534 Cf. A094214, A001622 (1/phi, phi).
%Y A341534 Cf. A263719, A092586 (1/psi, psi).
%K A341534 nonn
%O A341534 1,3
%A A341534 _Luc Rousseau_, Feb 13 2021