Alcuin’s Sequence—Solutions
Fall 2017 ARML Power Contest
Problem 1. Here are the other four distributions of full, half-full, and empty flasks:
F H E F H E F H E F H E
5 0 5 5 0 5 4 2 4 4 2 4
5 0 5 3 4 3 4 2 4 3 4 3
0 10 0 2 6 2 2 6 2 3 4 3
Problem 2. To avoid having listing out the details of the many possibilities, we will use
the facts discussed later on that show we really only need to display how many full flasks
each person gets, because they will get the same number of empty flasks as full, then enough
half-full to make up their fair share of flasks. So, for example, with eleven flasks of each type,
the triple (2, 4, 5) will mean that one person gets two full, two empty, and seven half-full
flask, while the second person gets four full, four empty, and three half-full, and the last
person gets five full, five empty, and one half-full flask. (This is the same notation used later
in the problem itself.)
So the possibilities for the numbers of flasks within the range of the table are:
3 flasks (1, 1, 1).
4 flasks (1, 1, 2) and (0, 2, 2).
5 flasks (1, 2, 2).
6 flasks (0, 3, 3), (1, 2, 3), and (2, 2, 2).
7 flasks (1, 3, 3), and (2, 2, 3).
8 flasks (0, 4, 4), (1, 3, 4), (2, 2, 4), and (2, 3, 3).
9 flasks (1, 4, 4), (2, 3, 4), (3, 3, 3)
10 flasks Five total possibilities, as given by the answer to problem 1.
11 flasks (1, 5, 5), (2, 4, 5), (3, 3, 5), and (3, 4, 4).
12 flasks (0, 6, 6), (1, 5, 6), (2, 4, 6), (3, 3, 6), (2, 5, 5), (3, 4, 5), and (4, 4, 4).
Therefore, we end up with
n 0 1 2 3 4 5 6 7 8 9 10 11 12
a(n) 1 0 1 1 2 1 3 2 4 3 5 4 7
1
Problem 3. If there are 3n flasks to distribute, each person must receive n flasks. But there
are also 3n/2 total flasks’ worth of oil, so each person receives n/2 flasks’ worth of oil. So the
average amount of oil per flask they receive is 1/2. Thus, each full flask must be balanced
by an empty flask to make the average come out to 1/2. In terms of arithmetic, if the share
F full flasks, H half-full, and E empty, we learn that E + H + F = n and H/2 + F = n/2,
or H + 2F = n. Subtracting, E − F = 0 so E = F .
Problem 4. If c > a + b then since a + b + c = n we subtract to learn 2c > n. But since
the child receives as many empty as full flasks, and they receive c full flasks, they receive 2c
flasks just counting the empty and full ones. In other words, they would receive more than
n flasks, which we know is not allowed.
Problem 5. The two integer triangles with perimeter 7 are represented by [1, 3, 3] and
[2, 2, 3]. The five of perimeter 13 are [1, 6, 6], [2, 5, 6], [3, 5, 5], [3, 4, 6], and [4, 4, 5].
Problem 6. We can find the possibilities by brute force, as we did for problem 2. In fact,
due to the result of problem 7 we know the tables must be the same. Each triple from
problem 2 should have 1 added to each entry to become a triangle triple for this problem.
n 3 4 5 6 7 8 9 10 11 12 13 14 15
t(n) 1 0 1 1 2 1 3 2 4 3 5 4 7
Problem 7. If a + b ≥ c then (a + 1) + (b + 1) ≥ (c + 2) > (c + 1). On the other
hand, if (a + 1) + (b + 1) > (c + 1) then since these numbers are all integers we must have
(a+1)+(b+1) ≥ (c+2) and the results follows subtracting 2 from each side of the inequality.
Problem 8. The correspondence (a, b, c) ↔ [a + 1, b + 1, c + 1] is the correspondence desired.
A solution to the flask problem is a triple (a, b, c) with 0 ≤ a ≤ b ≤ c, a + b ≥ c, and
a + b + c = n as shown by problems 3 and 4. Adding one to each term gives a triple
[a + 1, b + 1, c + 1] with 1 ≤ a + 1 ≤ b + 1 ≤ c + 1, satisfying the triangles inequality
(a + 1) + (b + 1) > (c + 1) by problem 7, so adding one to each term leads to an integer
triangle. Conversely, with an integer triangle, we can subtract one from each side length to
obtain a triple that satisfies the flask problem. And, of course, (a+1)+(b+1)+(c+1) = n+3.
Problem 9. We need to write n as a sum of two positive integers, so let 0 < a ≤ b with
a + b = n. Since a ≤ b we have 2a ≤ a + b = n, so 2a ≤ n or a ≤ n/2. Since a must be a
positive integer, there are bn/2c choices for a.
Problem 10. [a, b, c] represents an integer triangle of perimeter 2n if and only if 1 ≤ a ≤
b ≤ c, a+b > c and a+b+c = 2n. Then n−a ≥ n−b ≥ n−c and (n−a)+(n−b)+(n−c) =
3n − (a + b + c) = 3n − n = 2n. We just need to show that n − c is positive. But since
a + b > c, we see that a + b + c > 2c so 2n > 2c or n > c and n − c is positive.
Problem 11. Let [[a, b, c]] be a triple of positive integers adding to n + 6 with n ≥ 0 and
a ≥ b ≥ c. There are the following possibilities:
Case 1: c > 2. Then [[a − 2, b − 2, c − 2]] is a triple of positive integers adding to n, of which
there are p3 (n).
2
Case 2: c = 2. Then c − 2 = 0 and a + b = n + 4, so (a − 2) + (b − 2) = n. By problem 9
there are bn/2c such pairs if b − 2 > 0, and there is one such if b − 2 = 0, so altogether
we have bn/2c + 1 triples in this case.
Case 3: c = 1. This time a + b = n + 5 so (a − 2) + (b − 2) = n + 1. If b is at least two then,
as in the previous case, we get b(n + 1)/2c + 1 such pairs. But if b is one, we know
a = n + 4 and we have the triple [[n + 4, 1, 1]]. So we get a total of b(n + 1)/2c + 2
triples when c = 1.
Since c is positive, these three cases cover all possibilities, leading to a total of p3 (n) +
bn/2c + b(n + 1)/2c + 3 such triples. By checking the cases of n even or odd, we find
bn/2c + b(n + 1)/2c = n, obtaining the desired recurrence.
Problem 12. We use the recurrence proved in problem 11. First, for n = 0, 1, 2, 3, 4, 5 we
can quickly calculate that p3 (n) = 0, 0, 0, 1, 1, 2 respectively, while n2 /12 has values 0, 1/12,
1/3, 3/4, 4/3, 25/12 which are closest to 0, 0, 0, 1, 1, 2 respectively. That is, both p3 (n) and
kn2 /12k have the same first six starting values. But k(n + 6)2 /12k = k(n2 + 12n + 36)/12k =
kn2 /12 + n + 3k and since n + 3 is an integer, it won’t change how n2 /12 is rounded. So
k(n + 6)2 /12k = kn2 /12k + n + 3 which is the same recurrence satisfied by p3 (n). Since they
have the same recurrence and the same starting values, they must be equal for all n.
Problem 13. The squares modulo 12 are 0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1 (from 02 to 112 ),
none of which are 6.
Alternately, let q be the quotient and r the remainder on dividing n by 6. That is, let
n = 6q + r. Then n2 = 36q 2 + 12qr + r2 and n2 /12 simplifies to 3q 2 + qr + r2 /12. The
fractional part of this is r2 /12 which has possible values of 0, 1/12, 1/3, 3/4, 4/3, and 25/12
for the possible values of r. None of these are half an integer.
Problem 14. Obviously the correspondence takes triples that add to n to triples that add
to n + 3 and is a one-to-one correspondence. All that needs to be shown is that [a, b, c]
represents a triangle if and only if [a + 1, b + 1, c + 1] does also. But [a, b, c] is a triangle if and
only if 0 < a and a + b > c. Then certainly 0 < a + 1 and (a + 1) + (b + 1) > c + 2 > c + 1. On
the other hand, if a+b+c is odd, then a+b and c have opposite parities. Then (a+1)+(b+1)
and (c + 1) have the same parity. So if (a + 1) + (b + 1) > (c + 1), the left side is at least
two more than the right. Thus a + b ≥ (c + 1) and so a + b > c. Finally, note that there are
no even perimeter integer triangles with shortest side one, so the possibility that a + 1 = 1,
leading to the problematic a = 0, is ruled out.
Problem 15. If [a, b, c] is an integer triangle, we have 1 ≤ a ≤ b ≤ c and a + b > c. If we let
γ = c − b, α = b − a, and β = a + b − c − 1 then α, β, and γ are all non-negative integers and
satisfy the relationships with a, b, and c as given in the problem. They are unique because
they are the only solution to the system of three linear equations in the three unknowns α,
β, and γ given in the problem.
Conversely, given nonnegative α, β, and γ, setting a, b, and c to the combinations given
in the problem assures us that b − a = α ≥ 0, c − b = γ ≥ 0, and a ≥ 1 so 1 ≤ a ≤ b ≤ c.
Furthermore, a + b − c = β + 1 > 0 so the numbers satisfy the triangle inequality and form
an integer triangle.
3
Problem 16. Since each integer triangle of perimeter n has a unique α, β, and γ as given
in the previous problem, we find that a + b + c = 3 + 2α + 3β + 4γ so n − 3 can be written
as a sum of α 2’s, β 3’s, and γ 4’s. Since the triangles and the choices of α, β, and γ are
in one-to-one correspondence, so are the triangles and the ways of writing n − 3 as a sum of
2’s, 3’s, and 4’s.
