Search Results

Consider the following problem. You have a rainbow pyramid of M&Ms with n rows. For example, when n = 4 you may have one red, two orange, three yellow, and four green {inline.pdf}. You want to eat n of the M&Ms in such a way that the remaining M&Ms can be rearranged into a rainbow pyramid with n-1 rows. Two approaches are distinct if a different number from a particular row are eaten. In other words, we only care about the multiset of row frequencies (or colours) that are eaten and not the order in which they are eaten. One solution eats one M&M per row (e.g., 1234 → {inline.pdf}). Another eats the entire bottom row (e.g., 4444 → {inline.pdf}). How many different solutions are there? We show that the answer is 2^{n-1}. Furthermore, each solution can be naturally encoded with combinatorial objects enumerated by 2^{n-1} including binary words of length n-1, compositions of n, and subsets of [n-1]. Less obviously they are encoded by M&M permutations where each value in [n] is at most one position to the right of its position in the identity (e.g., 123, 132, 213, 312 for n = 3). What if at most m from each row can be eaten? When m = 1 the only solution is to eat one of each colour. Otherwise, the solutions are counted by Fibonacci (m = 2), Tribonacci (m = 3), Tetranacci (m = 4), and so on, up to 2^{n-1} (m = n). Furthermore, solutions can be naturally encoded by limited versions of the aforementioned objects including binary strings avoiding the substring 0^{m} and M&M permutations where values are limited by moving at most 𝓁 = m-1 positions to the left. Motivated by the works of Samuel Beckett, we consider minimal-change orders of the solutions. We obtain a satisfying result by filtering the binary reflected Gray code to words avoiding 0^{m}. For example, when n = 4 we have BRGC(n) = 000, 100, 110, 010, 011, 111, 101, 001 and the words avoiding 00 are BRGC_𝓁(3) = 110, 010, 011, 111, 101 where 𝓁 = 1 is the limit on the run-lengths of 0s. Our bijection then creates solutions that differ in by a single M&M 1244, 2244, 2234,1234, 1334. Thus, Beckett’s character Murphy can imagine every experience by changing one M&M at a time. The generalized Gray code BRGC_𝓁(n) was previously defined recursively [Bernini et. al Acta Informatica 2015] with its change sequence supporting amortized 𝒪(1)-time generation [Arndt Matters Computational 2010]. We uncover a simple greedy definition - flip the leftmost bit that creates a new binary word avoiding 0^m starting from w = ⋯ 110^{𝓁}110^{𝓁} - and a successor rule that supports loopless worst-case 𝒪(1)-time generation. Furthermore, the corresponding limited M&M permutations are greedily generated by swapping the smallest value (or the leftmost pair of adjacent values) that gives a valid new permutation (e.g., ̅{12}43, 21 ̅{43}, ̅{21}34, 1 ̅{23}4, 1324 for n = 4 and 𝓁 = 1). We also consider a relaxed version of the problem in which the initial pyramid’s n rows have respective widths r, r+1, r+2, …, n, n, …, n. Here the answer is an n-term product ⟨n,r⟩! = 1 ⋅ 2 ⋅ 3 ⋯ r ⋅ (r+1) ⋅ (r+1) ⋯ (r+1) that we refer to as a flatorial number. Furthermore, the solutions are represented by a generalization of M&M permutations in which each symbol can appear at most r positions to the right of its position in the identity. We complete our investigation by showing that eight distinct classes of permutations are enumerated by flatorial numbers.

We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation.