USAMTS Problem 1/4/13

In a strange language there are only two letters, a and b, and it is postulated that the letter a is a word. Furthermore, all additional words are formed according to the following rules:

A. Given any word, a new word can be formed from it by adding a b at the rightmost end.

B. If in any word a sequence aaa appears, a new word can be formed by replacing the aaa by the letter b.

C. If in any word the sequence bbb appears, a new word can be formed by omitting bbb.

D. Given any word, an new word can be formed by writing down the sequence that constitutes the given word twice.

Prove that in this language baabaabaa is not a word.

If we ignore b’s and look at how the rules apply to the number of “a”’s, in a legal word then:

Rules A and C can be ignored

Rule B allows us to delete any sequence aaa or number of a’s can be reduced by 3.

Rule D allows us to double the number of a’s

Now, if the number of a’s in a word is not divisible by 3, then:

Rule B cannot transform that word into a word, where the number of a’s is divisible by 3 because it reduces the original number by 3 , and original number is not divisible by 3.

Rule D cannot transform that word into a word where the number of a’s is divisible by 3 because it doubles the number of a’s, and the original number of a’s is not divisible by 3.

It is postulated that “a” is a word, and 1 is not divisible by 3. Thus it can not generate a word where the number of a’s is divisible by 3. Thus we can not make a word with 6 a’s in it, because 6 is a multiple of 3

Thus, baabaabaa is not a word because it has 6 a’s

(A less mathematical but perhaps more convincing to some approach is the fact that baabaabaa does get flagged by my spellchecker).

USAMTS Problem 2/4/13

Let f(x) = x [x [x [x]]] for all positive real numbers x, where [y] denotes the greatest integer less than or equal to y.

1. Determine x so that f(x) = 2001

2. Prove that f(x) = 2002 has no solution

It is easy to see that f(x) increases as x increases (because [x
[x
[x]]] either remains the same or increases when x increases.)
We see that:
f(6) = 6⁴ =1296
f(7) = 7⁴ = 2401

So, if f(x) = x
[x
[x
[x]]] = 2001,
6 < x < 7

Let [x
[x
[x]]] = m (m is an integer by the definition of []
So, f(x) = x*m = 2001
or x = 2001/m

Since 6 < x < 7, we have 286 < m < 333 (Eq 1)

Also, since 6<x < 7, [x] = 6
or x
[x] < 42, or [x
[x]] < 41
or x
[x
[x]] <287,
or [x
[x
[x]]] < 286 (Eq 2)

So, eq 1 and Eq 2 gives: 286 > m > 286 ; thus m = 286,
Thus, x = 2001/286

As we have shown in part 1,
f(6) = 6⁴ =1296
f(7) = 7⁴ = 2401
and 1296 < 2002 < 2401

So, if f(x) = 2002, (if it has a solution), it must satisfy
6 < x < 7

Thus, from Eq 2,
[x
[x
[x]]] < 286, so
x
[x
[x
[x]]] < 2002

Thus, f(x) = 2002 has no solution.

USAMTS Problem 3/4/13

Let f be a function defined on the set of all integers, and assume that it satisfiest he following properties:

A. f(0) ≠ 0

f(1) = 3
f(x)f(y) = f(x + y) + f(x
y)

Determine f(7).

Substituting x = 1 and y = 0 in Eq. C, and using Eq. B for f(1), we have:

f(1)f(0) = f(1 + 0) + f(1 0)

= 3 + 3

or 3 · f(0) = 6

or f(0) = 2

Similarly, when x = y = 1 in Eq. C, we have

f(1)f(1) = f(1 + 1) + f(1 1)

or 3 · 3 = f(2) + 2

or 9 2 = f(2)

or f(2) = 7

Similarly,

f(2)f(1) = f(2 + 1) + f(2 1)

or 7 · 3 = f(3) + 3

or 21 3 = f(3)

or f(3) = 18

and,

f(2)f(2) = f(2 + 2) + f(2 2)

or 7 · 7 = f(4) + 2

or 49 2 = f(4)

or f(4) = 47

Thus,

f(4)f(3) = f(4 + 3) + f(4 3)

or 47 · 18 = f(7) + 3

or 846 3 = f(7)

Thus, f(7) = 843

USAMTS Problem 4/4/13

A certain company has a faulty telephone system that sometimes transposes a pair of adjacent digits when someone dials a three-digit extension. Hence a call to x318 would ring at either x318, x138, or x381, while a call received at x044 would be intended for either x404 or x044. Rather than replace the system, the company is adding a computer to deduce which dialed extensions are in error and revert those numbers to their correct form. They have to leave out several possible extensions for this to work. What is the greatest number of three-digit extensions the company can assign under this plan?

In order for the computer to discern the correct extension, no two extensions may be related by having two adjacent interchanged digits. The key is the middle digit and we can say that this digit may get interchanged with its neighbor. Thus if we can correctly identified the middle digit we can correct the mistake.

We will look at extensions of three types:

Case 1 - those with all digits identical. (E.g. 111, 222)

Case 2 - those with exactly two identical and different digit (e.g. 404), and

Case 3 - those with three distinct digits (e.g. 123).

Case 1 - There are 10 such cases, and since all digits are identical, one number can be assigned for each of these cases without any confusion.

Thus, this case gives 10 extensions.

Case 2 - Here the “lone” distinct digit can be assigned as the “middle” digit, and the other (two identical digits) one flanking it. (We assign only those numbers where the “lone” digit is in the middle)

This case gives: 10*9 = 90 extensions.

Case 3 - Here we identify the middle digit as the smallest of the three digits. (Smallest is identifiable because all three digits are distinct). We assign only those extensions that satisfy this property. (Thus, if we get a call at 587, we know that the number being called was 857 because 5 is the smallest number and there is only one flip possible.)

This gives us (10 * 9 * 8)/3 = 240

(There are 10*9*8 permutations, and in each case only one of the three digits is the smallest.)

Thus, the total number of extensions possible under this system is 10 + 90 + 240 = 340

USAMTS Problem 5/4/13

Determine the smallest number of squares into which one can dissect an 11 x 13 rectangle, and exhibit such a dissection. The squares need not be of different sizes, their bases should be integers, and they should not overlap.

1

5

4

4

7

6

In the figure below, I have divided the given rectangle into six squares of side length 7, 6, 5, 4, and 1.

We will show that 6 is the smallest number of squares that we can divide this rectangle into, by showing that no solution exists for any number less than 6.

Theorem 1: If there is a rectangular strip of size (n x an), where n and an are both integers (a need not be an integer), then, then it will dissect into at least “a” squares

Proof: no square can have area larger than n², and we need to cover an area of an². QED

Theorem 1a: Theorem 1 can be applied to individual rectangular strips if they do not have a common border, and the minimum number of squares needed, for these strips can not be less than the sum of each section.

Proof: There cannot be a common square between such strips. Thus proved.

Theorem 2: any solution with a square larger than 7 units, will require more than 6 squares

Proof: If there is a square with side length 8, we will have at least two additional strips of 3 x 8 and 5 x 8, (without a common border). These would require, including the first square, at least 1+3+2 , or at least 6 squares. (In fact, it would require a minimum of 7, because there is still a “gap.”).

If we have a square with side length greater than 8, then the strip will be even narrower and we would need more than 6 squares in each case:

For square with side length 9, we have strips of 2 x 9 and 4 x 9, which would need at least 7 square.

Side length of 10 square would give strips of 1 x 10 and 3 x 10 which would need at least 14 squares.

11 length square would give a strip of 2 x 11 which would need at least 7 squares.

Now, let us consider the squares toughing the outer boundary of the rectangle. Since each square has side length less than 8 (Theorem 2) no one square can touch two opposite sides. So, if we take the side lengths of the squares touching the outer boundary as a, b, c, and d and arrange them such that

a < b < c < d

and obviously a > 2;

then the total number of squares is > a + b + c + d 4.

We only have to consider the cases where:

a = b = c = d = 2 Case 1

a = b = c = 2, d = 3 Case 2

In all other cases, a + b + c + d 4 > 6

We can easily prove that Case 1 is impossible because, assuming that the dimension of a square on the 11-side is x, than the square adjacent to it is 11 x, the square adjacent to that one would be 13-(11 x) = x+2. Calculating from the other side, we get 11-(13-x) = x-2. This would mean that the fourth figure has dimensions of both x + 2 and x 2, which is impossible for a square.

For Case 2 : Since 3 sides of rectangle have 2 squares touching them, (and only one side has 3 squares touching it), consider the 13-side which has only 2 squares touching.

Since we do not allows squares with side length > 7, there is only one way to divide 13 in two parts, so that two squares touch this side: namely:

6 + 7

The other 13-side cannot have only 2 squares touching it as the only combination is 6 and 7, and 6² + 7² + 6² + 7² > 143, so it must have 3 squares touching it, and thus both 11-sides must have only 2 squares touching them. We get the dimensions of the other two squares on the 11-sides as 11-6=5 and 11-7= 4,

so the 13-side with three squares touching it has third side 13 5 - 4 = 4.

This gives us the solution given at the top of the page, and since there are no other solutions of this type, No other solution exist with smaller number than 6.

QED.