  We investigate the problem of fairly dividing a divisible heterogeneous
resource, also known as a cake, among a set of agents who may have different
entitlements. We characterize the existence of a connected
strongly-proportional allocation -- one in which every agent receives a
contiguous piece worth strictly more than their proportional share. The
characterization is supplemented with an algorithm that determines its
existence using O(n * 2^n) queries. We devise a simpler characterization for
agents with strictly positive valuations and with equal entitlements, and
present an algorithm to determine the existence of such an allocation using
O(n^2) queries. We provide matching lower bounds in the number of queries for
both algorithms. When a connected strongly-proportional allocation exists, we
show that it can also be computed using a similar number of queries. We also
consider the problem of deciding the existence of a connected allocation of a
cake in which each agent receives a piece worth a small fixed value more than
their proportional share, and the problem of deciding the existence of a
connected strongly-proportional allocation of a pie.
