Maths Olympiad Prep

Library / /40 of 41

Number theory Difficulty 7.4 National Olympiad, round 2 Prove it New Zealand

Problem:
A dot-trapezium consists of several rows of dots such that each row contains one more dot than the row immediately above (apart from the top row). For example here is a dot-trapezium consisting of 15 dots, having 3 rows and 4 dots in the top row.

Figure 1

A positive integer nn is called a trapezium-number if there exists a dot-trapezium consisting of exactly nn dots, with at least two rows and at least two dots in the top row. How many trapezium-numbers are there less than 100?

Solutions — 2

Solution 1

Solution:
Let nn be a trapezium number and suppose there are aa dots in the first row and bb dots in the last row. So the required conditions are a2a \geq 2 and ba+1b \geq a + 1. Then the equation becomes:

2n=b(b+1)a(a1)=b2a2+b+a=(a+b)(ba+1)2n = b(b + 1) - a(a - 1) = b^{2} - a^{2} + b + a = (a + b)(b - a + 1)

because it is the difference between two triangle numbers. Let the two factors on the RHS be x=(a+b)x = (a + b) and y=(ba+1)y = (b - a + 1). Rearranging gives us

a=xy+12andb=x+y12.a = \frac{x - y + 1}{2} \qquad \mathrm{and} \qquad b = \frac{x + y - 1}{2}.

In order for aa and bb to be integers we must have xx and yy being opposite parity. So we are looking for factorizations of the form 2n=xy2n = xy such that one of xx and yy is even while the other is odd. We also need a<ba < b (so that the trapezium has at least two rows) which is equivalent to y2y \geq 2. Finally we also need a2a \geq 2 (so there are at least two dots in the top row) which is equivalent to xy+3x \geq y + 3. We need

Now write n=2kmn = 2^{k}m with mm odd.

- If n=2kn = 2^{k} is a power of 2, then the only factorization of 2n=2k+1=xy2n = 2^{k + 1} = xy such that both xx and yy have opposite parity is x=2k+1x = 2^{k + 1} and y=1y = 1. This doesn't work because we require y>1y > 1. (when y=1y = 1 the "trapezium" would consist of only one row)
- If m>2k+1+1m > 2^{k + 1} + 1 or 1<m<2k+111 < m < 2^{k + 1} - 1 then we can choose

x=max{2k+1,m}andy=min{2k+1,m}.x = \max \{2^{k + 1},m\} \quad \mathrm{and}\quad y = \min \{2^{k + 1},m\}.

To check that this works we simply check that y>1y > 1 and xy+3x \geq y + 3. Note that this still works even when k=0k = 0.
- If m=2k+1±1m = 2^{k + 1} \pm 1 and mm is prime then the only factorization of 2n=2k+1m=xy2n = 2^{k + 1}m = xy such that both xx and yy have opposite parity and x>y>1x > y > 1 is

x=max{2k+1,m}andy=min{2k+1,m}.x = \max \{2^{k + 1},m\} \quad \mathrm{and}\quad y = \min \{2^{k + 1},m\}.

However this doesn't work because we require x>x+1x > x + 1. (when y=1y = 1 the "trapezium" would consist have one dot in the top row)

The only remaining possibility is when m=2k+1±1m = 2^{k + 1} \pm 1 and mm is composite. If k>2k > 2 then m=2k+1±115m = 2^{k + 1} \pm 1 \geq 15, so n=2km8×15>100n = 2^{k} m \geq 8 \times 15 > 100 and we don’t need to consider it. For k2k \leq 2 we get m=1,3,5,7,9m = 1, 3, 5, 7, 9. We can’t have m=1m = 1 because then nn would be a power of 2. We also can’t have m=3,5,7m = 3, 5, 7 because they are prime. Finally we consider m=9m = 9 and so k=2k = 2. In this case we get n=2km=36n = 2^{k} m = 36, which is a trapezium number as seen here:

Figure 2

Therefore all non-trapezium-numbers less than 100, are the powers of two and numbers of the form n=2k(2k+1±1)n = 2^{k}(2^{k + 1} \pm 1) where (2k+1±1)(2^{k + 1} \pm 1) is prime (and k2k \leq 2). The powers of two are: {1,2,4,8,16,32,64}\{1, 2, 4, 8, 16, 32, 64\}. The numbers of the form 2k(2k+1±1)2^{k}(2^{k + 1} \pm 1) with k2k \leq 2 and (2k+1±1)(2^{k + 1} \pm 1) being prime are

{20(21+1)=3,21(221)=6,21(22+1)=10,22(231)=28}.\{2^{0}(2^{1} + 1) = 3, 2^{1}(2^{2} - 1) = 6, 2^{1}(2^{2} + 1) = 10, 2^{2}(2^{3} - 1) = 28\}.

All together the non-trapezium numbers are {1,2,3,4,6,8,10,16,28,32,64}\{1, 2, 3, 4, 6, 8, 10, 16, 28, 32, 64\}. There are 99 positive integers less than 100 and exactly 11 of them are non-trapezium numbers. So the final answer is 9911=8899 - 11 = 88.

Solution 2

Solution:
First, notice that any odd integer can be written as a sum of consecutive integers: 2n+1=(n)+(n+1)2n + 1 = (n) + (n + 1), e.g. 23=11+1223 = 11 + 12.

Then observe that any multiple of 3 can be written as a sum of consecutive integers: 3n=(n1)+(n)+(n+1)3n = (n - 1) + (n) + (n + 1), for example, 18=5+6+718 = 5 + 6 + 7.

Similarly, any multiple of 5 can be written as a sum of consecutive integers:

5n=(n2)+(n1)+(n)+(n+1)+(n+2).5n = (n - 2) + (n - 1) + (n) + (n + 1) + (n + 2).

In general, any number with an odd factor can be written as a sum of consecutive integers. The only numbers that have no odd factors (other than 1) are the powers of two. There are 7 such numbers less than 100: {1,2,4,8,16,32,64}\{1,2,4,8,16,32,64\}.

In general, any number with an odd factor (greater than one) can be written as a sum of consecutive integers. Note that if the odd factor is too large then some of these terms are negative. For example our above method for 26 would produce

26=(4)+(3)+(2)+(1)+0+1+2+3+4+5+6+7+8.26 = (-4) + (-3) + (-2) + (-1) + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8.

Because the centre of the consecutive run is always positive, there will always be more positive terms than negative terms. Therefore each negative term can be 'cancelled' with its corresponding positive term. At a minimum, the centre of the run must be at least 1, so there will always be at least two positive terms remaining even after cancelling.

But we are also not allowed to have one dot in the top row, i.e. our sum (after cancelling) cannot include 1. This would seem to exclude the triangular numbers:

{1,3,6,10,15,21,28,36,45,55,66,78,91}.\{1,3,6,10,15,21,28,36,45,55,66,78,91\}.

Except some can be rewritten as a different sum of consecutive integers in more than one way. For example 15=1+2+3+4+515 = 1 + 2 + 3 + 4 + 5, but also 15=7+815 = 7 + 8. In general, if the triangular number, Tn=12n(n+1)T_{n} = \frac{1}{2} n(n + 1), is either odd, or has an odd factor less than nn, it can be rewritten as a sum of consecutive integers that do not include 1. The following triangular numbers can be salvaged:

- 15 is odd, so 15=7+815 = 7 + 8
- 21 is odd, so 21=10+1121 = 10 + 11
- 36 is a multiple of 3, so 36=11+12+1336 = 11 + 12 + 13
- 45 is odd, so 45=22+2345 = 22 + 23
- 55 is odd, so 55=27+2855 = 27 + 28
- 66 is a multiple of 3, so 66=21+22+2366 = 21 + 22 + 23
- 78 is a multiple of 3, so 78=25+26+2778 = 25 + 26 + 27
- 91 is odd, so 91=45+4691 = 45 + 46

So there are 5 triangular numbers that are not possible: {1,3,6,10,28}\{1,3,6,10,28\}. Combined with the powers of two that are also impossible: {1,2,4,8,16,32,64}\{1,2,4,8,16,32,64\}, there are 11 numbers (5+7=12(5 + 7 = 12 but the number 1 is included in both lists) that can not be written as trapezium numbers:

{1,2,3,4,6,8,10,16,28,32,64}.\{1,2,3,4,6,8,10,16,28,32,64\}.

There are 99 numbers less than 100, so there are 9911=8899 - 11 = 88 trapezium numbers.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.