Star problems Advanced ← Back to chapter

Introduction to Algebra: Star problems

Ten optional challenges to stretch your reasoning. Work on paper, use hints when you need them, and check the answer or full solution when you are ready. You can skip these problems and continue the course.

1 of 3 stars: Stretch
2 of 3 stars: Challenge
3 of 3 stars: Deep challenge

Stars indicate difficulty within this set.

0 of 10 completed

Progress saved in this browser.

Problem 1 of 10

Problem 1 Two machines, two orders

Difficulty: 1 of 3 stars, Stretch

Machine A doubles its input and then adds 3. Machine B triples its input and then adds a fixed number $c$ . Each output becomes the next machine's input.

(a) When $c=-4$ , compare A followed by B with B followed by A, starting with the same arbitrary real number. Which result is larger, and by how much?

(b) Find every real value of $c$ for which the two orders give the same result for every starting number. Prove your answer.
1. Hint 1
  Name the starting number $x$ and write the output after each machine.
2. Hint 2
  When comparing the final expressions, check which terms cancel. Do not assume the starting number needs to be solved for.
Answer

For $c=-4$ , A followed by B is always larger by 10. The two orders agree for every input exactly when $c=6$ .

Full solution

Let the starting number be $x$ .
A followed by B produces
$3(2x+3)+c=6x+9+c.$
B followed by A produces
$2(3x+c)+3=6x+2c+3.$

For $c=-4$ , the two outputs are $6x+5$ and $6x-5$ .
Their difference is 10, regardless of whether $x$ is positive, negative, zero, or fractional.
The input cancels from the comparison.

For general $c$ , the first output minus the second is
$(6x+9+c)-(6x+2c+3)=6-c.$
Therefore, the outputs agree precisely when $6-c=0$ , or $c=6$ .
Substitution gives $6x+15$ in either order, verifying that this choice works for every real input.

If $c$ is any other value, the difference is a fixed nonzero number.
Then no starting number makes the outputs equal.
Writing an arbitrary input made it possible to prove a statement about all inputs at once.

Answer

For $c=-4$ , A followed by B is always larger by 10. The two orders agree for every input exactly when $c=6$ .

Key idea

Simplifying a difference can reveal an input-independent relationship.
Problem 1: Mark complete
Problem 2 Two erased numbers

Difficulty: 1 of 3 stars, Stretch

Five consecutive positive integers are written in increasing order. Two of them are erased. The remaining three numbers have sum 45.

Find every possible original block of five numbers and every erased pair that works. Prove that your list is complete.
1. Hint 1
  Write the original numbers as $n,n+1,n+2,n+3,n+4$ . Bound the smallest and largest possible remaining sums.
2. Hint 2
  After bounding $n$ , the three retained offsets from $0,1,2,3,4$ must have one of only three possible sums.
Answer

Block 12 through 16: erase 12 and 13. Block 13 through 17: erase 13 and 17, or erase 14 and 16. Block 14 through 18: erase 17 and 18.

Full solution

Let the smallest original number be $n$ .
The smallest possible sum of three retained numbers is
$n+(n+1)+(n+2)=3n+3.$
The largest is
$(n+2)+(n+3)+(n+4)=3n+9.$
Hence $3n+3\leq45\leq3n+9$ , giving
$12\leq n\leq14.$

When $n=12$ , the retained offsets must sum to $45-36=9$ .
The maximum offset sum is $2+3+4=9$ , so the only retained numbers are 14, 15, and 16.
Erase 12 and 13.

When $n=13$ , the offsets must sum to 6.
If 0 is included, the other two distinct offsets must be 2 and 4.
If 0 is absent, the smallest possible sum is $1+2+3=6$ , giving the only other choice.
Thus retain 13, 15, 17 and erase 14, 16; or retain 14, 15, 16 and erase 13, 17.

When $n=14$ , the offsets must have the minimum sum 3, forcing $0,1,2$ .
Retain 14, 15, 16 and erase 17, 18.
Each listed retained triple sums to 45, and the bounds and offset cases exclude every other possibility.

Answer

Block 12 through 16: erase 12 and 13. Block 13 through 17: erase 13 and 17, or erase 14 and 16. Block 14 through 18: erase 17 and 18.

Key idea

A variable and two extreme cases can turn a large search into a few complete cases.
Problem 2: Mark complete
Problem 3 A row controlled by one number

Difficulty: 1 of 3 stars, Stretch

Five positive integers are written in a row. The sums of neighboring pairs, from left to right, are 12, 17, 23, and 20.

(a) Find every possible value of the middle number. For each allowed value, explain how the entire row is determined.

(b) If the five numbers also have total 44, find the row.
1. Hint 1
  Call the first number $x$ . Use each adjacent sum to express the next number in terms of $x$ .
2. Hint 2
  Every entry must be a positive integer. Determine which entry gives the strongest upper bound on $x$ .
Answer

The middle number can be any integer from 6 through 16. All rows are $(x,12-x,5+x,18-x,2+x)$ for $x=1,2,\ldots,11$ . With total 44, the row is $(7,5,12,11,9)$ .

Full solution

Let the first entry be $x$ .
The first pair sum makes the second entry $12-x$ .
The second pair sum makes the third
$17-(12-x)=5+x.$
Continuing gives the row

$(x,\ 12-x,\ 5+x,\ 18-x,\ 2+x).$

The first entry is a positive integer, so $x\geq1$ .
Positivity of the second gives $x\leq11$ .
Positivity of the fourth would only require $x\leq17$ , and the third and fifth are already positive when $x\geq1$ .
Thus precisely the integers $1$ through $11$ are allowed.
Every one gives a valid row because the neighboring sums simplify to the required values.

The middle entry is $5+x$ , so it can be any integer from 6 through 16.
Conversely, choosing any such middle entry fixes $x$ and therefore all five entries.

Adding the entries gives $37+x$ .
For a total of 44, $x=7$ , yielding $7,5,12,11,9$ .
Its pair sums are $12,17,23,20$ , and its total is 44, confirming all the conditions.

Answer

The middle number can be any integer from 6 through 16. All rows are $(x,12-x,5+x,18-x,2+x)$ for $x=1,2,\ldots,11$ . With total 44, the row is $(7,5,12,11,9)$ .

Key idea

Several unknown entries may depend on just one freely chosen variable.
Problem 3: Mark complete
Problem 4 Which targets can the machine reach?

Difficulty: 2 of 3 stars, Challenge

A machine starts at 1. On each move, you may either double the current number or add 3. You may make any finite number of moves, including no moves.

Describe exactly which positive integers can appear. Prove both that the excluded integers are impossible and that every integer in your description can be reached.
1. Hint 1
  Track whether the current number is divisible by 3.
2. Hint 2
  For reachability, work backward from a proposed target. An even target can be halved; an odd target greater than 1 can first have 3 subtracted.
Answer

Exactly the positive integers that are not divisible by 3.

Full solution

Starting from 1, a number is never divisible by 3.
Adding 3 preserves its remainder upon division by 3.
Doubling also preserves nondivisibility: a number of the form $3k+1$ doubles to $3(2k)+2$ , and a number of the form $3k+2$ doubles to $3(2k+1)+1$ .
Neither result is a multiple of 3.

To show that every other positive integer is reachable, reverse the moves.
Start with any positive target not divisible by 3.
If it is even, halve it.
The result is positive, smaller, and still not divisible by 3; otherwise doubling it would have made the original target divisible by 3.

If the target is odd and greater than 1, it is at least 5, because 3 is excluded.
Subtract 3.
The result is an even positive integer, smaller than before and still not divisible by 3.

Repeat these backward steps.
The numbers strictly decrease while remaining positive, so the process must stop.
Every allowed number greater than 1 has a backward step, so it can stop only at 1.
Reversing the entire path uses only the permitted forward moves and reaches the original target.

Answer

Exactly the positive integers that are not divisible by 3.

Key idea

An invariant proves impossibility; a decreasing reverse process proves that the remaining cases are all possible.
Problem 4: Mark complete
Problem 5 A score chosen by your opponent

Difficulty: 2 of 3 stars, Challenge

You choose an integer $x$ , which may be positive, negative, or zero. Your opponent then chooses one of the three numbers $x+4$ , $18-2x$ , and $2x-1$ . The chosen number is your score, and your opponent wants your score to be as small as possible.

(a) What is the greatest score you can guarantee, and which integer choices of $x$ achieve it?

(b) If you may instead choose any real number $x$ , what is the greatest score you can guarantee? Find all real choices that achieve it.
1. Hint 1
  Your guaranteed score is the smallest of the three expressions.
2. Hint 2
  Add the second and third expressions. Their sum is fixed, which gives a bound on how large their smaller value can be.
Answer

For integer $x$ , the greatest guaranteed score is 8, achieved only by $x=5$ . For real $x$ , it is $17/2=8.5$ , achieved only by $x=19/4=4.75$ .

Full solution

The second and third expressions always sum to
$(18-2x)+(2x-1)=17.$
They cannot both exceed $8.5$ .
When $x$ is an integer, both expressions are integers, so at least one is at most 8.
This bounds the guaranteed integer score by 8.

At $x=5$ , the three expressions are 9, 8, and 9.
The opponent can choose 8, but cannot force anything lower, so the bound is attained.
Any other integer choice guaranteeing 8 would need $2x-1\geq8$ and
$18-2x\geq8.$
These require $x\geq4.5$ and $x\leq5$ , leaving only the integer 5.

For a real choice, the fixed-sum bound is $8.5$ .
To attain it, both the second and third expressions must equal $8.5$ ; if one were greater, the other would be less.
Solving $2x-1=8.5$ gives $x=4.75$ .
At this input, the first expression is $8.75$ , so the opponent's minimum is indeed $8.5$ .
The equality condition proves this real choice is unique.

Answer

For integer $x$ , the greatest guaranteed score is 8, achieved only by $x=5$ . For real $x$ , it is $17/2=8.5$ , achieved only by $x=19/4=4.75$ .

Key idea

A fixed sum limits the smaller quantity; equality conditions identify the best choice.
Problem 5: Mark complete
Problem 6 One equation, many possible coefficients

Difficulty: 2 of 3 stars, Challenge

A positive integer $a$ is chosen, and then the equation $a(x-2)=3x+6$ is considered.

Find every ordered pair of positive integers $(a,x)$ that satisfies the equation. Your reasoning must cover arbitrarily large positive integers, not just a tested range.
1. Hint 1
  First rule out $x=1$ and $x=2$ . Then rewrite $3x+6$ as $3(x-2)+12$ .
2. Hint 2
  Subtract three copies of $x-2$ from both sides. Two positive integer quantities must have product 12.
Answer

The pairs are $(4,14)$ , $(5,8)$ , $(6,6)$ , $(7,5)$ , $(9,4)$ , and $(15,3)$ .

Full solution

If $x=1$ , the left side is $-a$ , which is negative, while the right side is 9.
If $x=2$ , the left side is zero and the right side is 12.
Neither works.
Therefore every positive integer solution has $x\geq3$ .

Rewrite the right side as $3(x-2)+12$ .
The original equation then says that $a$ copies of $x-2$ equal three copies of $x-2$ , plus 12.
Subtracting those three copies gives

$(a-3)(x-2)=12.$

Since $x-2$ is positive, $a-3$ must also be positive.
Both factors are positive integers.
The complete ordered factor pairs of 12 are $(1,12),(2,6),(3,4),(4,3),(6,2),(12,1)$ .
Adding 3 to the first coordinate and 2 to the second gives exactly the six stated pairs.

Each listed pair has
$(a-3)(x-2)=12.$
Reversing the rewriting restores the original equation, so all six really work.
Conversely, every positive integer solution had to give one of these factor pairs, proving completeness without an arbitrary search limit.

Answer

The pairs are $(4,14)$ , $(5,8)$ , $(6,6)$ , $(7,5)$ , $(9,4)$ , and $(15,3)$ .

Key idea

Choosing a helpful repeated expression can turn an equation into a complete factor-pair search.
Problem 6: Mark complete
Problem 7 The center is forced

Difficulty: 2 of 3 stars, Challenge

The nine numbers $2,5,8,11,14,17,20,23,26$ are to be placed once each in a $3\times3$ square. Each of the three rows, each of the three columns, and both main diagonals must have the same sum.

(a) Prove that the center must be 14 and that every pair of opposite cells sums to 28.

(b) Prove that 2 cannot occupy a corner.

(c) Give one arrangement that satisfies all the conditions. You may describe it by its three rows.
1. Hint 1
  The sum of all nine entries determines each row sum. Add the four line sums passing through the center.
2. Hint 2
  If a corner contained 2, the two remaining entries in its row would have a fixed sum. Which unused pair could produce that sum?
Answer

The common line sum is 42, the center is 14, and opposite cells sum to 28. The number 2 cannot be a corner. One arrangement has rows $(23,2,17)$ , $(8,14,20)$ , and $(11,26,5)$ .

Full solution

The nine numbers total 126, so each row, column, and diagonal must sum to $126/3=42$ .
Let the center be $c$ .
Add the middle row, middle column, and both diagonals.
These four lines count each noncenter entry once and the center four times.
Their total is therefore $126+3c$ .
It also equals $4\times42=168$ , so $3c=42$ and $c=14$ .

Each line through the center now has its other two entries summing to $42-14=28$ .
This proves the opposite-pair claim.

Suppose 2 were in a corner.
Its diagonally opposite corner would have to contain 26.
The two other entries in 2's row would sum to 40, and so would the two other entries in its column.
Among the available numbers, the only possible distinct pairs summing to 40 are 14 with 26, or 17 with 23.
But 14 is already the center and 26 is in the opposite corner; neither belongs in that row or column.
Both lines would therefore require 17 and 23.
Their noncorner cells are distinct, so this would repeat numbers, which is forbidden.

Finally, rows $(23,2,17)$ , $(8,14,20)$ , and $(11,26,5)$ use every number once.
Direct addition gives 42 for all three rows, all three columns, and both diagonals.

Answer

The common line sum is 42, the center is 14, and opposite cells sum to 28. The number 2 cannot be a corner. One arrangement has rows $(23,2,17)$ , $(8,14,20)$ , and $(11,26,5)$ .

Key idea

Counting the same entries through overlapping sums can force a hidden value before any search.
Problem 7: Mark complete
Problem 8 Adding to two jars at a time

Difficulty: 3 of 3 stars, Deep challenge

Three labeled jars start empty. On each move, choose two different jars and add one counter to each of those two jars. You cannot remove counters. Any finite number of moves is allowed, including zero.

(a) Give a necessary and sufficient rule for a target triple $(a,b,c)$ of nonnegative integers to be reachable. Prove both directions of your rule.

(b) Apply your rule to $(17,23,30)$ , $(10,14,26)$ , and $(11,14,26)$ . For every reachable example, give the numbers of moves using each pair of jars.
1. Hint 1
  Each move adds two counters in total. If there are $M$ moves, how many counters can any one jar receive?
2. Hint 2
  If the target is reachable in $M$ moves, exactly $M-a$ moves omit the first jar. Those are the moves using the second and third jars.
Answer

A triple is reachable exactly when its total is even and no entry exceeds the sum of the other two. Only $(17,23,30)$ among the three examples is reachable: use pairs first-second 5 times, first-third 12 times, second-third 18 times.

Full solution

After $M$ moves, the total number of counters is $2M$ , so $a+b+c$ must be even.
Each jar gains at most one counter per move, giving
$a,b,c\leq M.$
With $M=(a+b+c)/2$ , these conditions say that no entry exceeds the sum of the other two.
They are necessary.

Now suppose the target satisfies both conditions.
Define $M=(a+b+c)/2$ , a nonnegative integer.
Use the second-third pair $M-a$ times, the first-third pair $M-b$ times, and the first-second pair $M-c$ times.
These are nonnegative integers by the assumed bounds.
Their sum is
$3M-(a+b+c)=M.$

The first jar then receives $(M-b)+(M-c)=2M-b-c=a$ counters.
The same reasoning gives $b$ and $c$ for the other jars.
Performing the specified moves in any order constructs the target, including the all-zero target with no moves.
Thus the conditions are also sufficient.

For $(17,23,30)$ , the total is 70, so $M=35$ .
The pair counts are 5, 12, and 18 as stated.
For $(10,14,26)$ , the total is even but $26>10+14$ , so it fails the largest-entry condition.
The triple $(11,14,26)$ has odd total 51, so it is impossible.

Answer

A triple is reachable exactly when its total is even and no entry exceeds the sum of the other two. Only $(17,23,30)$ among the three examples is reachable: use pairs first-second 5 times, first-third 12 times, second-third 18 times.

Key idea

Necessary conditions become a complete solution only when a construction proves they are sufficient.
Problem 8: Mark complete
Problem 9 A surprising replacement rule

Difficulty: 3 of 3 stars, Deep challenge

Five cards initially show $1,2,3,4,5$ . On a move, choose two cards showing $a$ and $b$ , discard them, and replace them with one card showing $ab+a+b$ . Continue until one card remains.

(a) Prove that the final number is independent of the choices and order of moves, and find that number.

(b) Before any moves, you may replace exactly one of the five starting numbers with a different positive integer. The five starting numbers after this change must still be distinct. Find every such replacement that makes the final number 1439, and prove completeness.
1. Hint 1
  Add 1 to the replacement expression and look for a product.
2. Hint 2
  Track the product of one more than every current card number. For part (b), compare the new product with the original product.
Answer

The original final number is 719. Exactly three replacements give 1439 with distinct starting numbers: replace 3 by 7, replace 4 by 9, or replace 5 by 11.

Full solution

The key identity is $ab+a+b+1=(a+1)(b+1)$ , which follows by distributing the product.
Consider the product formed by adding 1 to every current card number and multiplying.
A move replaces the two factors $a+1$ and $b+1$ by the single factor $ab+a+b+1$ , equal to their product.
Thus this tracked product never changes.

Initially it is
$2\times3\times4\times5\times6=720.$
At the end, if the lone card shows $F$ , the product is simply $F+1$ .
Hence $F+1=720$ and $F=719$ , whatever choices were made.

For part (b), a final value of 1439 requires a tracked product of 1440, exactly twice the original.
If the original card $k$ is replaced by $r$ , the product changes by the factor $(r+1)/(k+1)$ .
That factor must be 2, so $r=2k+1$ .

For $k=1,2,3,4,5$ , the required new values are respectively $3,5,7,9,11$ .
The first two repeat another starting card and are disallowed.
The other three preserve distinctness and double the product, so each works.
The forced equation for $r$ proves there are no additional replacements.

Answer

The original final number is 719. Exactly three replacements give 1439 with distinct starting numbers: replace 3 by 7, replace 4 by 9, or replace 5 by 11.

Key idea

A small change of expression can reveal a quantity preserved through a complicated process.
Problem 9: Mark complete
Problem 10 Four additions and four doublings

Difficulty: 3 of 3 stars, Deep challenge

Start with the number 1. Make exactly eight moves: four moves of type A, which add 1, and four moves of type D, which double the current number. You may arrange the eight moves in any order.

(a) Find the smallest and largest possible final numbers, and prove your bounds.

(b) Find every move sequence that ends at 44. Write sequences from left to right in the order performed, and prove that your list is complete.
1. Hint 1
  The original 1 is doubled four times in every sequence. An added 1 is doubled only by the D moves after it.
2. Hint 2
  Each addition contributes one of $1,2,4,8,16$ to the final number. To reach 44, the four contributions must sum to 28. Split into cases according to whether a contribution of 16 occurs.
Answer

Minimum 20, from D D D D A A A A. Maximum 80, from A A A A D D D D. Exactly three sequences end at 44: A D A D D A A D; A D D A A A D D; D A A A D A D D.

Full solution

The original 1 contributes $2^4=16$ at the end.
Every added 1 contributes $2^j$ , where $j$ is the number of doublings still to come.
Thus the final number is 16 plus four contributions, each belonging to $1,2,4,8,16$ .
The minimum is $16+4=20$ , with all additions last.
The maximum is $16+4\times16=80$ , with all additions first.

For a final value of 44, the four contributions must sum to 28.
At most one can be 16.
If there is one 16, the other three sum to 12.
If one of those is 8, the other two must be 2 and 2.
If none is 8, all three are at most 4, so all three must be 4.
This gives contribution groups $(16,8,2,2)$ and $(16,4,4,4)$ .

If there is no 16, all contributions are at most 8.
With at most two 8s, their sum is at most
$8+8+4+4=24.$
Four 8s sum to 32.
Therefore there must be three 8s and one 4, giving $(8,8,8,4)$ .

A contribution specifies its addition's position relative to the four doublings: 16 means before all four, 8 after the first, 4 after the second, 2 after the third, and 1 after the fourth.
The three groups therefore give exactly the three stated sequences.
Each totals $16+28=44$ , and the exhaustive contribution cases prove no others work.

Answer

Minimum 20, from D D D D A A A A. Maximum 80, from A A A A D D D D. Exactly three sequences end at 44: A D A D D A A D; A D D A A A D D; D A A A D A D D.

Key idea

Track each contribution separately to replace an order-sensitive process with a short numerical classification.
Problem 10: Mark complete