| Transcript
for the Math
Jam "USAMTS Round 4 Math Jam"
on Mar 19. |
| Math Jam hosted by Valentin Vornicu
(Valentin Vornicu ). |
Valentin Vornicu (18:29:13)
Hello and welcome to the USA Math Talent Search Math Jam for Year 18, Round 4.
Valentin Vornicu (18:29:29)
My name is Valentin Vornicu and I will be teaching this Math Jam.
Valentin Vornicu (18:29:34)
Before we get started I would like to take a moment to explain our virtual classroom to those who have not previously participated in a Math Jam or one of our online classes.
Valentin Vornicu (18:29:45)
The classroom is moderated, meaning that students can type into the classroom, but only the moderator (that's me) can choose a comment to drop into the classroom. This helps keep the class organized and on track.
Valentin Vornicu (18:29:50)
This also means that only well-written comments will be passed into the classroom, so please take time writing responses that are complete, easy to read, and on-topic.
Valentin Vornicu (18:30:03)
Also, only the moderator can enter into private chats with other users, although due to the size and nature of this Math Jam, it is unlikely that this will happen.
Valentin Vornicu (18:30:15)
There will be images in this lecture. The images should appear directly in the classroom window, as in the example below:
Valentin Vornicu (18:30:22)
Valentin Vornicu (18:30:25)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/a7dcd8010feb2cc00e4a33dc6e5ef2cd.png
Valentin Vornicu (18:30:34)
If you click on the link, the image will appear in a separate window. You may have to hold down the CTRL key while you click on an image link, and/or you may have to disable your popup blocker.
Valentin Vornicu (18:30:49)
You can view the Round 4 problems as we discuss them by clicking on the following link:
Valentin Vornicu (18:30:54)
http://www.usamts.org/Tests/USAMTSProblems_18_4.pdf
Valentin Vornicu (18:31:11)
Let's get started!
Valentin Vornicu (18:31:26)
Valentin Vornicu (18:31:33)
http://www.artofproblemsolving.com/Classroom/cbe6/images/lx-250636302.gif
Valentin Vornicu (18:31:43)
Where can we start on this problem?
Xantos C. Guin (18:31:47)
Find a formula for S(n) when n is even and when n is odd
Valentin Vornicu (18:32:07)
We can start by trying to find a formula for S(n).
Valentin Vornicu (18:32:12)
The sign of the last term n depends on whether n is even or odd, so let's separate these cases.
Valentin Vornicu (18:32:22)
Let's take the case n even first. We must evaluate the following sum:
Valentin Vornicu (18:32:27)
Valentin Vornicu (18:32:33)
(Since n is even, the sign of the last term n is negative.)
Valentin Vornicu (18:32:40)
How can we evaluate this sum?
JerryS (18:33:07)
look at pairs of numbers summing to -1
longwan (18:33:11)
pair them
Valentin Vornicu (18:33:21)
We can group the terms as follows:
Valentin Vornicu (18:33:25)
Xantos C. Guin (18:33:18)
S(n) = (1-2)+(3-4)+(5-6)+...+((n-1)-n) = (-1)+(-1)+(-1)+...+(-1) = -n/2
Valentin Vornicu (18:33:38)
With the signs in the sum alternating, we might expect there to be some cancellation in the sum. Grouping the terms this way takes advantage of this cancellation.
Valentin Vornicu (18:33:48)
Valentin Vornicu (18:34:03)
The term -1 appears n/2 times, once for each pair of terms (1,2), (3,4), ..., (n - 1, n). Therefore, S(n) = -n/2.
Valentin Vornicu (18:34:22)
Now we take the case where n is odd. We must evaluate the following sum:
Valentin Vornicu (18:34:26)
Valentin Vornicu (18:34:35)
(Since n is odd, the sign of the last term n is positive.)
Valentin Vornicu (18:34:41)
How can we evaluate this sum?
vishalarul (18:34:31)
Pair them up again to get that the sum equals (n+1)/2.
jbano (18:35:01)
pair 2 and 3 and so on
JerryS (18:35:01)
S(n-1) + n, n-1 is even
monkeymatt (18:35:21)
Valentin Vornicu (18:35:33)
We can group the terms the same way as above:
Valentin Vornicu (18:35:36)
Valentin Vornicu (18:35:46)
The term -1 appears (n - 1)/2 times, once for each pair of terms (1,2), (3,4), ..., (n - 2, n - 1).
Valentin Vornicu (18:35:59)
Valentin Vornicu (18:36:12)
Alternatively, we could have used a recurrence, knowing S(n-1).
Valentin Vornicu (18:36:23)
Thus, S(n) has the following formula:
Valentin Vornicu (18:36:27)
Valentin Vornicu (18:36:38)
Now, if we look at parts (a) and (b), we see that both are equations of the form S(x) + S(y) + S(x + y) = k. So let's compute the LHS first, and then worry about the constant k later.
Valentin Vornicu (18:36:42)
How can we compute the LHS?
perfectnumber628 (18:36:45)
go through the cases with a and b being even or odd
Valentin Vornicu (18:36:59)
Since S(n) is defined by the cases of n odd and n even, we can re-write the expression by splitting up into the same cases.
Valentin Vornicu (18:37:03)
How many cases do we have?
vishalarul (18:37:08)
4 caess
Xantos C. Guin (18:37:09)
4 or 3
Valentin Vornicu (18:37:46)
We have four cases to deal with: (1) both x and y are odd, (2) x is odd and y is even, (3) x is even and y is odd, and (4) both x and y are even.
Valentin Vornicu (18:38:01)
(1) If both x and y are odd, then what is S(x) + S(y) + S(x + y)?
besttate (18:38:13)
1
Valentin Vornicu (18:38:30)
If both x and y are both odd, then x + y is even, so
Valentin Vornicu (18:38:37)
Valentin Vornicu (18:38:46)
This clearly tells us that the expression can never be 2007 or 2008, so we will not have to worry about this case for parts (a) or (b).
Valentin Vornicu (18:38:52)
(2) What if x is odd and y is even?
besttate (18:39:06)
x+1
Valentin Vornicu (18:39:23)
If x is odd and y is even, then x + y is odd, so
Valentin Vornicu (18:39:28)
Valentin Vornicu (18:39:42)
(3) What if x is even and y is odd?
Xantos C. Guin (18:39:46)
y+1
besttate (18:39:47)
y+1
JerryS (18:39:51)
y + 1
.cpp (18:39:52)
y + 1
Valentin Vornicu (18:40:02)
We can go through all the calculations, but the easiest way is to recognize that this case is just case (2) with x and y switched, so S(x) + S(y) + S(x + y) = y + 1.
Valentin Vornicu (18:40:07)
(4) What if both x and y are even?
vishalarul (18:40:14)
-x-y
Xantos C. Guin (18:40:16)
-(x+y)
Valentin Vornicu (18:40:31)
If both x and y are even, then x + y is also even, so
Valentin Vornicu (18:40:35)
Valentin Vornicu (18:40:40)
What does this tell us?
.cpp (18:40:31)
The answer is negative...
vishalarul (18:40:47)
That the sum has to be negative.
Valentin Vornicu (18:40:55)
Like case (1), the expression can never be 2007 or 2008 (since -(x + y) is always negative), so we will not have to worry about this case either for parts (a) or (b).
Valentin Vornicu (18:41:04)
Now we are ready to tackle the given equations.
Valentin Vornicu (18:41:08)
For part (a), we must solve S(a) + S(b) + S(a + b) = 2007.
Valentin Vornicu (18:41:14)
We've already eliminated cases (1) and (4), so let's look at case (2).
Valentin Vornicu (18:41:23)
We saw that if a is odd and b is even, then S(a) + S(b) + S(a + b) = a + 1.
Valentin Vornicu (18:41:30)
What do we conclude?
besttate (18:41:29)
x must be 2006 and odd simultaniously, so it never works
Xantos C. Guin (18:41:39)
a=2006, but that is even, so there are no solutions
Valentin Vornicu (18:41:58)
There are in fact no solutions, because this case assumes that a is odd, so a cannot be 2006.
Valentin Vornicu (18:42:08)
What about case (3), where a is even and b is odd?
VDLmath_2 (18:41:59)
there are no solutions
besttate (18:42:19)
same thing, except with b, so no solutions
Valentin Vornicu (18:42:27)
As we saw above, case (3) is the same as case (2) with a and b switched. Therefore, there are no solutions in case (3) either, because if there were any solutions in case (3), there would be solutions in case (2).
Valentin Vornicu (18:42:42)
Hence, there are no solutions to the equation S(a) + S(b) + S(a + b) = 2007.
Valentin Vornicu (18:42:47)
For part (b), we must solve S(c) + S(d) + S(c + d) = 2008.
Valentin Vornicu (18:42:50)
Again, we've already eliminated cases (1) and (4), so let's look at case (2).
Valentin Vornicu (18:43:27)
We saw that if c is odd and d is even, then S(c) + S(d) + S(c + d) = c + 1.
Valentin Vornicu (18:43:30)
What do we conclude?
jbano (18:43:10)
c=2007
besttate (18:43:10)
c = 2007
Valentin Vornicu (18:43:45)
We conclude that c = 2007. (And this case does assume that c is odd, so this is consistent.)
Valentin Vornicu (18:43:49)
What values can d be?
besttate (18:43:38)
c = 2007, d is any even integer
vishalarul (18:43:45)
c=2007 and d is even
Valentin Vornicu (18:44:04)
The case assumed that d is even, so d can be any even positive integer.
Valentin Vornicu (18:44:09)
What about case (3), where c is odd and d is even?
vishalarul (18:44:16)
d=2007 and c is even
Xantos C. Guin (18:44:17)
d = 2007 and c is any even positive integer
Valentin Vornicu (18:44:44)
Since case (3) is the same as case (2) with c and d switched, the solutions are d = 2007 and c any even integer.
besttate (18:44:28)
whoops, you mean d is odd and c is even, right?
Valentin Vornicu (18:45:02)
Yeah, small typo there :)
JerryS (18:45:21)
Will points be counted off if I put just c = 2007 and d is any positive even integer?
Valentin Vornicu (18:45:58)
I'm no grader for USAMTS, but at the IMO you would not get all the points. Not sure about USAMTS though.
Valentin Vornicu (18:46:16)
Probably not all the points since you don't present the full range of solutions.
Valentin Vornicu (18:46:51)
Therefore, the solutions to S(c) + S(d) + S(c + d) = 2008 are (c,d) = (2007, d) where d is any even positive integer, and (c,d) = (c, 2007) where c is any even positive integer.
Valentin Vornicu (18:47:24)
Problem 2
Valentin Vornicu (18:47:26)
Valentin Vornicu (18:47:31)
http://www.artofproblemsolving.com/Classroom/cbe6/images/lx-235536841.gif
Valentin Vornicu (18:48:08)
First, let's translate the problem into algebraic terms. How can we do that?
Xantos C. Guin (18:48:21)
n^3-n will end in 2007 zeros, so n^3-n = 10^2007*k
VDLmath_2 (18:48:43)
n^3-n=10^2007 x z (an integer)
Valentin Vornicu (18:49:00)
Valentin Vornicu (18:49:04)
Valentin Vornicu (18:49:14)
We can move everything to one side:
Valentin Vornicu (18:49:19)
Valentin Vornicu (18:49:25)
Then what?
vishalarul (18:49:35)
Factor left side.
Xantos C. Guin (18:49:35)
n^3-n = (n-1)(n)(n+1)
Valentin Vornicu (18:49:56)
Valentin Vornicu (18:50:03)
None of these steps should surprise us, as these are the same steps we would take if we were solving an equation.
Valentin Vornicu (18:50:07)
Now what?
Xantos C. Guin (18:50:42)
(n-1)(n)(n+1) = 0 mod 2^2007 and 0 mod 5^2007
Valentin Vornicu (18:51:03)
Valentin Vornicu (18:51:09)
Valentin Vornicu (18:51:22)
By splitting up the congruence this way, we only have to worry about each prime factor one at a time. Later, we will see how to combine the solutions with respect to each of these prime powers.
Valentin Vornicu (18:51:33)
Valentin Vornicu (18:51:42)
Valentin Vornicu (18:51:52)
Let's solve the second one first, as it is easier.
Valentin Vornicu (18:51:58)
We have the congruence
Valentin Vornicu (18:52:05)
Valentin Vornicu (18:52:13)
Valentin Vornicu (18:52:19)
How can this happen?
Xantos C. Guin (18:52:13)
n = -1, 0, or 1 mod 5^2007
perfectnumber628 (18:52:28)
only one of them can be a mulitple of 5
Valentin Vornicu (18:53:08)
Valentin Vornicu (18:53:29)
Since all three of n-1, n, n+1 give different residues when divided by 5.
Valentin Vornicu (18:53:58)
Valentin Vornicu (18:54:18)
Lest you think that solving all congruencies is this easy, the second congruence has a slight twist to it.
Valentin Vornicu (18:54:23)
The second congruence is
Valentin Vornicu (18:54:33)
Valentin Vornicu (18:54:43)
Valentin Vornicu (18:54:59)
Let's take a small example. Suppose n is even. What can we say about n - 1 and n + 1?
perfectnumber628 (18:55:08)
they're odd
p4fn2w (18:55:09)
they are both odd
VDLmath_2 (18:55:24)
They are odd
besttate (18:55:50)
they are both not divisible by 2
Valentin Vornicu (18:56:17)
If n is even, then both n - 1 and n + 1 are odd.
Valentin Vornicu (18:56:24)
What does this mean?
perfectnumber628 (18:55:23)
so n is divisible by 2^2007
.cpp (18:56:35)
That n mod 2^2007 ~ 0\
Xantos C. Guin (18:56:35)
n = 0 mod 2^2007
besttate (18:56:46)
that n is a multiple by 2^2007
Valentin Vornicu (18:56:54)
Valentin Vornicu (18:57:03)
Now we look at the case of n odd. What can we say about n - 1 and n + 1?
besttate (18:57:10)
they are BOTH even!
VDLmath_2 (18:57:19)
they are both even
Xantos C. Guin (18:57:21)
both are divisible by 2 and one is divisible by 4
Valentin Vornicu (18:57:36)
So this gets a bit tricky, because now both n - 1 and n + 1 contain factors of 2.
Valentin Vornicu (18:57:39)
How many factors of 2 can they contain? For example, can both n - 1 and n + 1 be divisible by 4?
perfectnumber628 (18:57:36)
but only one can be divisible by 4
VDLmath_2 (18:57:44)
no
besttate (18:57:47)
no
VDLmath_2 (18:57:47)
only one can
Valentin Vornicu (18:58:02)
If both n - 1 and n + 1 were divisible by 4, then their difference would also be divisible by 4. But their difference is (n + 1) - (n - 1) = 2, so this is not the case.
Valentin Vornicu (18:58:11)
So one of n - 1 and n + 1 has exactly one factor of 2.
Valentin Vornicu (18:58:18)
Suppose n - 1 has exactly one factor of 2. We know n is odd. So what do we require of n + 1?
Xantos C. Guin (18:58:04)
no, so n = -1 or 1 mod 2^2006
.cpp (18:58:15)
Therefore one is mod 2^2006 at least.
besttate (18:58:25)
that means the other must be a multiple of 2^2006
Valentin Vornicu (18:58:39)
Valentin Vornicu (18:58:44)
Valentin Vornicu (18:58:48)
Now we have the other case, where n + 1 has exactly one factor of 2. What happens in this case?
Valentin Vornicu (18:59:38)
Valentin Vornicu (18:59:49)
Valentin Vornicu (19:00:07)
Valentin Vornicu (19:00:21)
Valentin Vornicu (19:00:27)
Xantos C. Guin (19:00:50)
-1 or -1+2^2006
perfectnumber628 (19:00:54)
-1 or 2^2006-1
kostya (19:01:12)
-1, 2^2006 - 1
Valentin Vornicu (19:01:36)
Valentin Vornicu (19:01:51)
Valentin Vornicu (19:02:00)
Valentin Vornicu (19:02:38)
We now have all the solutions with respect to the prime powers. As mentioned before, we must combine these solutions to solve the original congruence.
Valentin Vornicu (19:02:44)
What is the mathematical tool that allows us to do this?
besttate (19:03:09)
chinese remainder theorem
Valentin Vornicu (19:03:50)
For the sake of simplicity, we state the specific version of the Chinese Remainder theorem required here.
Valentin Vornicu (19:04:02)
Valentin Vornicu (19:04:26)
.
Valentin Vornicu (19:04:33)
(The result is also true for more than two congruences, which is the general statement of the Chinese Remainder theorem.)
Valentin Vornicu (19:04:39)
Valentin Vornicu (19:05:00)
We won't discuss the proof of this theorem here, or how to find the solution. If you want to, there are plenty of online resources that discuss these, which you can consult on your own.
Valentin Vornicu (19:05:08)
How can we apply the Chinese Remainder theorem to this problem?
Valentin Vornicu (19:05:51)
Remember, we're not really interested in finding the solutions themselves, we're only interested in finding the number of solutions. How can we do that?
Xantos C. Guin (19:05:38)
n has 3*5 = 15 congruences in mod 2^2007*5^2007 = 10^2007
besttate (19:05:43)
5 values for the first congruence, 3 for the second, so 15 unique combinations
Valentin Vornicu (19:06:09)
The key part of the Chinese Remainder theorem, as stated above, is that there is a unique solution x for every pair (a,b).
Valentin Vornicu (19:06:12)
Valentin Vornicu (19:06:17)
Valentin Vornicu (19:06:38)
Valentin Vornicu (19:06:47)
We're not quite done yet. What is the last step we must take?
Valentin Vornicu (19:07:20)
.
Valentin Vornicu (19:07:31)
Valentin Vornicu (19:07:52)
Valentin Vornicu (19:08:01)
Therefore, there are 15 integers that satisfy the given property.
Valentin Vornicu (19:08:23)
Problem 3
Valentin Vornicu (19:08:29)
Valentin Vornicu (19:08:38)
http://www.artofproblemsolving.com/Classroom/cbe6/images/lx-186706046.gif
Valentin Vornicu (19:08:48)
Valentin Vornicu (19:08:49)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/1f4d0cde7a3100f12879b24d1d39e75e.png
Valentin Vornicu (19:08:57)
For reference, let's label the midpoints P, Q, R, and S.
Valentin Vornicu (19:09:06)
Valentin Vornicu (19:09:08)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/d231135137a34658615d174d4a3eb706.png
Valentin Vornicu (19:09:37)
When we join O to P, Q, R, and S, one of the four pieces we obtain is BPOQ. Let's take a closer look at it.
Valentin Vornicu (19:09:50)
Valentin Vornicu (19:09:53)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/fbf1455af7bcf6864112aaecd3684bb5.png
Valentin Vornicu (19:09:59)
We want to show that BPOQ has the same area as the other three pieces. Put it another way, we want to show that BPOQ has one-fourth the area of quadrilateral ABCD.
Valentin Vornicu (19:10:18)
How can we deal with the area of a quadrilateral?
besttate (19:10:37)
break it into triangles
vfiroiu (19:10:37)
split it into triangles
perfectnumber628 (19:10:48)
divide it into triangles
kostya (19:10:29)
divide into 2 triangles
Valentin Vornicu (19:11:52)
There are no nice formulas for the area of a quadrilateral. (There are formulas, but none of them are particularly easy to work with.)
Valentin Vornicu (19:11:56)
We can split a quadrilateral into two triangles, since triangles have nice formulas for their areas and are much easier to work with.
Valentin Vornicu (19:12:01)
How can we split quadrilateral BPOQ into two triangles?
besttate (19:12:12)
draw in PQ
kostya (19:12:23)
or draw PQ
jbano (19:12:25)
connect p and Q
Valentin Vornicu (19:12:36)
We can split it into triangles BPQ and OPQ.
Valentin Vornicu (19:12:41)
Valentin Vornicu (19:12:43)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/f4fea561210a64d6c070253dfafd5cc3.png
Valentin Vornicu (19:12:50)
You may already notice some interesting things about the diagram. If not, we can take it one step at a time.
Valentin Vornicu (19:13:01)
We know that ON is parallel to PQ, and that OM is parallel to BD.
Valentin Vornicu (19:13:15)
Does either of these say anything about the area of triangle OPQ?
Xantos C. Guin (19:13:57)
It equals the area of NPQ
Valentin Vornicu (19:14:32)
Since ON is parallel to PQ, triangles NPQ and OPQ have the same area.
Valentin Vornicu (19:14:37)
Valentin Vornicu (19:14:39)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/462be66411ca1a6f27cfdbf4a07ba6a4.png
Valentin Vornicu (19:14:45)
(There are several results about areas of triangles relating to their bases and heights. These are often overlooked facts, and should not be taken for granted.)
Valentin Vornicu (19:14:52)
What does this say about the area of quadrilateral BPOQ?
Xantos C. Guin (19:15:08)
It equals the area of BPNQ
vfiroiu (19:15:19)
same area as BPNQ
kostya (19:15:20)
it is equal to PNQB
VDLmath_2 (19:15:27)
It equals the area of BPNQ
Valentin Vornicu (19:15:40)
It says that the area of quadrilateral BPOQ is equal to the area of quadrilateral BPNQ.
Valentin Vornicu (19:15:49)
Valentin Vornicu (19:15:51)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/a072ad75505793df495bc048f66dc29f.png
Valentin Vornicu (19:15:56)
Now, do you notice anything about quadrilateral BPNQ?
vfiroiu (19:16:08)
similar to BADC
Xantos C. Guin (19:16:20)
Its dimentions are half of BADC's
Valentin Vornicu (19:16:38)
Does it relate to quadrilateral ABCD in any special way?
Valentin Vornicu (19:17:00)
Why are its dimensions half of BADC's ?
robertnishihara (19:17:16)
because p is the midpoint of ab q is the mid of bc and n is the mid of bd
Valentin Vornicu (19:17:34)
Therefore, quadrilateral BPNQ can be obtained by dilating quadrilateral BADC through B by a factor of 1/2.
Valentin Vornicu (19:17:47)
This means that the area of quadrilateral BPNQ is exactly 1/4 the area of quadrilateral ABCD. It follows that the area of quadrilateral BPOQ is also exactly 1/4 the area of quadrilateral ABCD.
Valentin Vornicu (19:17:57)
But there's nothing special about quadrilateral BPOQ. The same argument works on all the other parts.
Valentin Vornicu (19:18:08)
Valentin Vornicu (19:18:10)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/590ded71c94c611dfae64f89f8159e46.png
Valentin Vornicu (19:18:16)
Hence, all four parts have equal area.
Valentin Vornicu (19:18:39)
Problem 4
Valentin Vornicu (19:18:42)
Valentin Vornicu (19:18:49)
http://www.artofproblemsolving.com/Classroom/cbe6/images/lx-174228622.gif
Valentin Vornicu (19:19:00)
Valentin Vornicu (19:19:02)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/11475e56af4b4e3f825522d5988ec4af.png
Valentin Vornicu (19:19:10)
Valentin Vornicu (19:19:11)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/764179c82fc87969e2af2aa4b170e453.png
Valentin Vornicu (19:19:55)
First, to get a feel for the problem, we compute T_n for small value of n.
Valentin Vornicu (19:20:05)
What is T_1?
robertnishihara (19:20:05)
t1=1
Xantos C. Guin (19:20:07)
T1 = 1
VDLmath_2 (19:20:09)
1
vfiroiu (19:20:11)
1
Valentin Vornicu (19:20:19)
There is only one graph on a 2 x 1 array that is a valid connection, namely the one with an edge connecting the two nodes, so T_1 = 1.
Valentin Vornicu (19:20:26)
What is T_2?
p4fn2w (19:20:30)
4
jbano (19:20:31)
4
kostya (19:20:32)
4
Valentin Vornicu (19:20:40)
There are exactly four valid connections on a 2 x 2 array of nodes, so T_2 = 4.
Valentin Vornicu (19:20:47)
Valentin Vornicu (19:20:48)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/1c0e8ce203232a35ab3927443b190a8e.png
Valentin Vornicu (19:20:55)
What is T_3?
besttate (19:20:57)
15
VDLmath_2 (19:20:59)
15
kostya (19:20:59)
15
robertnishihara (19:20:59)
15
Valentin Vornicu (19:21:08)
There are exactly 15 valid connections on a 2 x 3 array of nodes, so T_3 = 15.
Valentin Vornicu (19:21:16)
Valentin Vornicu (19:21:19)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/f42f95a3792c1ebe221dba9012b6415b.png
Valentin Vornicu (19:21:40)
For n greater than 3, trying to count all the valid connections by hand gets very unwieldy, and is not a viable option for calculating T_n.
Valentin Vornicu (19:21:43)
This being the case, how else can we compute T_n?
besttate (19:21:48)
recursion
Xantos C. Guin (19:21:51)
recursion
Valentin Vornicu (19:22:05)
We can try recursion. In this problem, it seems reasonable to try to build valid connections on a 2 x n array from valid connections on a smaller array.
Valentin Vornicu (19:22:19)
For example, how can we build the following valid connection on a 2 x 3 array from a smaller array?
Valentin Vornicu (19:22:24)
Valentin Vornicu (19:22:26)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/c858d77ce06b4579ab4016094f654a12.png
Valentin Vornicu (19:23:28)
We can add edges (on the right) to a valid connection on a 2 x 2 array:
Valentin Vornicu (19:23:34)
Valentin Vornicu (19:23:38)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/dd98e187d15b03eb72ca0e2447acf0de.png
Valentin Vornicu (19:23:49)
How about the following valid connection?
Valentin Vornicu (19:23:55)
Valentin Vornicu (19:23:57)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/335245ba67dff0680cdf7d47131d17ed.png
Xantos C. Guin (19:24:10)
Add two edges on another valid connection
perfectnumber628 (19:24:11)
add the two segments on the right to a valid array
Valentin Vornicu (19:24:28)
Again, we can add edges, on the right:
Valentin Vornicu (19:24:31)
Valentin Vornicu (19:24:35)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/d3701241608220913bea74642e59720a.png
Valentin Vornicu (19:24:52)
What about the following valid connection? This one is a bit more tricky:
Valentin Vornicu (19:25:00)
Valentin Vornicu (19:25:04)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/a0973973e298ead6e504ab53166ab840.png
Valentin Vornicu (19:26:06)
We can add edges to (on the right) to valid connection on a 2 x 5 array:
Valentin Vornicu (19:26:13)
Valentin Vornicu (19:26:15)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/1d5066feb7f83b668a6de5f91ab3954e.png
Valentin Vornicu (19:26:23)
Note that the 2 x 5 array is the largest subarray (on the left) that we can use as the "base array".
Valentin Vornicu (19:26:34)
These examples show us that we can build valid connections on a 2 x n array in two different ways.
Valentin Vornicu (19:26:44)
First, we can add the edge on the top and on the bottom to a valid connection on a 2 x (n - 1) array:
Valentin Vornicu (19:26:52)
Valentin Vornicu (19:27:03)
How many such valid connections are produced this way?
robertnishihara (19:27:09)
T_n-1
besttate (19:27:19)
T(n-1)
Valentin Vornicu (19:27:32)
There is one for each valid connection on a 2 x (n - 1) array, so there are T_(n - 1).
Valentin Vornicu (19:27:47)
The second way is to add a "hook-like" structure to a valid connection on a 2 x k array, where k is less than n, and there are actually two such ways to do this:
Valentin Vornicu (19:27:55)
Valentin Vornicu (19:28:12)
Note that the width of the hook is uniquely defined by the first gap that appears either in the top edge or the bottom.
Valentin Vornicu (19:28:18)
For a given k, how many such valid connections are produced this way?
besttate (19:29:04)
2T_k
Xantos C. Guin (19:29:05)
2T_k
Valentin Vornicu (19:29:44)
We can add two hooks to a 2 x k array, so there are 2T_k.
Valentin Vornicu (19:29:50)
Letting k vary from 1 to n - 1, the total number is 2T_1 + 2T_2 + ... + 2T_(n - 1).
Valentin Vornicu (19:29:58)
There is actually one more valid connection we need to count. Which one is it?
Xantos C. Guin (19:30:13)
k=0
Valentin Vornicu (19:30:35)
The following valid connection can't be produced as described above, so we need to count it separately:
Valentin Vornicu (19:30:42)
Valentin Vornicu (19:30:53)
http://www.artofproblemsolving.com/Admin/latexrender/pictures/2f4ca012acb869c52286237d624de8df.png
Valentin Vornicu (19:30:56)
So what is our formula for T_n?
besttate (19:31:17)
2(T_1+T_2...T_n-1) + T_n-1 + 1
robertnishihara (19:31:25)
T_n=2(T_1+T_2+T_3+...+T_n-1)+T_n-1+1
Xantos C. Guin (19:31:31)
T_n = T_{n-1} + 2( T_1+T_2+...+T_{n-1}) + 1
Valentin Vornicu (19:31:39)
Valentin Vornicu (19:31:49)
This formula is sufficient to generate all the terms up to T_(10), but with a bit more work, we can make it simpler.
Valentin Vornicu (19:32:13)
Given the formula above for T_n, what is T_(n + 1)?
Valentin Vornicu (19:32:36)
Valentin Vornicu (19:32:39)
What can we do with these formulas?
vfiroiu (19:32:16)
take T(n) - T(n-1)
besttate (19:32:47)
subtract them
Valentin Vornicu (19:32:56)
Since they have so many terms in common, we can subtract them.
Valentin Vornicu (19:33:02)
Valentin Vornicu (19:33:11)
Now we have a recursion that uses only the two previous terms, instead of all of them.
Valentin Vornicu (19:33:14)
So what is T_(10)?
Valentin Vornicu (19:33:30)
besttate (19:33:28)
151316
Valentin Vornicu (19:33:45)
Valentin Vornicu (19:33:59)
Problem 5
Valentin Vornicu (19:34:26)
Valentin Vornicu (19:34:33)
http://www.artofproblemsolving.com/Classroom/cbe6/images/lx-138494910.gif
Valentin Vornicu (19:34:36)
How can we get started on the problem?
besttate (19:34:50)
try to find A_n for smaller n's
kostya (19:34:55)
find one that works and try to make it smaller
Valentin Vornicu (19:35:55)
Since we want to minimize A_2007, one idea is to take the smallest possible value for each term. This is known as a "greedy algorithm". (Actually, maybe we should call it an "unselfish algorithm", because we are taking smallest possible value.)
robertnishihara (19:35:10)
Try numbers and start with 1
Valentin Vornicu (19:36:08)
The smallest possible value for x_1 is 1.
Valentin Vornicu (19:36:12)
Then what is the smallest possible value for x_2?
kostya (19:36:20)
3
vfiroiu (19:36:20)
3
tjhance (19:36:20)
3
Valentin Vornicu (19:36:32)
From condition (2), we want x_1 + x_2 = 1 + x_2 to be divisible by 2, but from condition (1), x_2 can't be equal to 1.
Valentin Vornicu (19:36:35)
The smallest value that satisfies both these conditions is x_2 = 3.
Valentin Vornicu (19:36:38)
Then what is the smallest possible value for x_3?
besttate (19:36:40)
2
tjhance (19:36:41)
2
p4fn2w (19:36:44)
2
robertnishihara (19:36:44)
2
Valentin Vornicu (19:36:51)
From condition (2), we want x_1 + x_2 + x_3 = 4 + x_3 to be divisible by 3, so we can take x_3 = 2.
Valentin Vornicu (19:36:57)
Then what is the smallest possible value for x_4?
Xantos C. Guin (19:37:02)
x_4 = 6
p4fn2w (19:37:03)
6
tjhance (19:37:03)
6
Valentin Vornicu (19:37:11)
The smallest possible value for x_4 is 6.
Valentin Vornicu (19:37:18)
We can construct a table of the terms that the greedy algorithm generates:
Valentin Vornicu (19:37:22)
Valentin Vornicu (19:37:32)
In this sequence,
Valentin Vornicu (19:37:36)
Valentin Vornicu (19:37:43)
These are in fact the minimum values for A_(2n) and A_(2n + 1), which we prove now.
Valentin Vornicu (19:37:56)
Note that this greedy algorithm does not guarantee the minimum possible value of A_2007. It only guarantees the smallest possible value for each term; it's possible there is a different sequence that may ultimately lead to a smaller value of A_2007.
Valentin Vornicu (19:38:07)
Valentin Vornicu (19:38:15)
We will prove this using induction.
Valentin Vornicu (19:38:20)
The base case is the inequality A_1 >= 1, which is trivial.
Valentin Vornicu (19:38:27)
To make things easier, we introduce some notation.
Valentin Vornicu (19:38:34)
Valentin Vornicu (19:38:40)
What can we say about S_n?
tjhance (19:38:55)
it is divisible by n
Xantos C. Guin (19:38:56)
it must be divisible by n
besttate (19:39:00)
it is a multiple of n
Valentin Vornicu (19:39:19)
From condition (2), S_n is a multiple of n for all n. Furthermore, (S_n) is a strictly increasing sequence - each term is greater than the previous term.
Valentin Vornicu (19:39:27)
Valentin Vornicu (19:39:30)
What does that say about S_(2k + 1)?
Xantos C. Guin (19:39:54)
S(2k+1) \ge (2k+1)(k+1)
Valentin Vornicu (19:40:48)
Valentin Vornicu (19:40:58)
Let's look at the next term, S_(2k + 2). What do we know about this term?
vfiroiu (19:40:51)
bigger than (k+1)(2k+1)
Valentin Vornicu (19:41:19)
Valentin Vornicu (19:41:25)
Valentin Vornicu (19:41:31)
Can you see what that multiple is?
besttate (19:42:05)
(2k+2)(k+1)
kostya (19:42:07)
2k^2 + 4k +2
Valentin Vornicu (19:42:19)
Valentin Vornicu (19:42:23)
Therefore, S_(2k + 2) must be at least (2k + 2)(k + 1) = 2k^2 + 4k + 2.
Valentin Vornicu (19:42:28)
Now we can play the same game with S_(2k + 3):
Valentin Vornicu (19:42:34)
Valentin Vornicu (19:42:44)
What is a multiple of 2k + 3 that is greater than 2k^2 + 4k + 2?
Valentin Vornicu (19:43:23)
Valentin Vornicu (19:43:29)
S_(2k + 3) must be at least (2k + 3)(k + 1) = 2k^2 + 5k + 3.
Valentin Vornicu (19:43:34)
What does that say about A_(2k + 3)?
Valentin Vornicu (19:44:22)
A_{2k + 3} must be at least k + 1.
Valentin Vornicu (19:44:28)
Unfortunately, for our induction argument, this isn't quite good enough. We want to show that A_{2k + 3} is at least k + 2.
Valentin Vornicu (19:44:31)
How can we deal with this case?
besttate (19:44:54)
try to negate the case when it equals k+1
Valentin Vornicu (19:45:17)
We can proceed with an argument by contradiction.
Valentin Vornicu (19:45:23)
Suppose that S_(2k + 3) = 2k^2 + 5k + 3.
Valentin Vornicu (19:45:30)
Now, we're going to work backwards, trying to find bounds on S_(2k + 2) and S_(2k + 1).
Valentin Vornicu (19:45:35)
Valentin Vornicu (19:45:41)
What does this say about S_(2k + 2)?
Valentin Vornicu (19:46:17)
Valentin Vornicu (19:46:25)
S_(2k + 2) is at most (2k + 2)(k + 1) = 2k^2 + 4k + 2.
Valentin Vornicu (19:46:28)
However, what else do we know about S_(2k + 2)?
Valentin Vornicu (19:47:35)
We know from above that S_(2k + 2) is at least (2k + 2)(k + 1) = 2k^2 + 4k + 2.
Valentin Vornicu (19:47:40)
Therefore, S_(2k + 2) = (2k + 2)(k + 1).
Valentin Vornicu (19:47:48)
Again, we go backwards one step.
Valentin Vornicu (19:47:52)
Valentin Vornicu (19:47:56)
What does that say about S_(2k + 1)?
Valentin Vornicu (19:48:46)
Valentin Vornicu (19:48:52)
S_(2k + 1) is at most (2k + 1)(k + 1).
Valentin Vornicu (19:49:00)
But again from above, we know that S_(2k + 1) is at least (2k + 1)(k + 1). (This was in fact our induction hypothesis). Therefore, S_(2k + 1) = (2k + 1)(k + 1).
Valentin Vornicu (19:49:06)
So where is our contradiction?
besttate (19:49:38)
S(2k+1)=S(2k+2)=S(2k+3), which leads to equal consecutive terms
Valentin Vornicu (19:50:13)
Note that we haven't yet used condition (1), the condition that two adjacent terms cannot be equal.
Valentin Vornicu (19:50:16)
So let's compute x_(2k + 2) and x_(2k + 3). What are these values?
Valentin Vornicu (19:50:37)
Valentin Vornicu (19:50:45)
Valentin Vornicu (19:50:54)
This gives us two consecutive terms that are equal, and our contradiction.
Valentin Vornicu (19:51:00)
So S_(2k + 3) cannot be equal to (2k + 3)(k + 1), which means that S_(2k + 3) is at least (2k + 3)(k + 2).
Valentin Vornicu (19:51:09)
Hence, A_(2k + 3) is at least k + 2, which completes the induction. Therefore, A_(2n + 1) is at least n + 1 for all n.
Valentin Vornicu (19:51:18)
Now that we have a bound, we need to show that there is a sequence that achieves this bound. Is there such a sequence?
vfiroiu (19:51:31)
the greedy sequence
kostya (19:51:34)
yes the one we just did
besttate (19:51:35)
the greed algorithm sequence
Valentin Vornicu (19:51:41)
Yes, namely the one we found at the beginning. We can define this sequence more explicitly as follows: Let x_n = (n + 1)/2 for n odd, x_n = 3n/2 for n even.
Valentin Vornicu (19:51:47)
Then it is easy to check that consecutive terms are distinct, so condition (1) is satisfied. Also,
Valentin Vornicu (19:51:53)
Valentin Vornicu (19:52:02)
and
Valentin Vornicu (19:52:03)
Valentin Vornicu (19:52:17)
Hence, condition (2) is satisfied. In particular, A_(2007) = 1004.
Valentin Vornicu (19:52:23)
Therefore, the minimum possible value of A_(2007) is 1004.
Valentin Vornicu (19:53:00)
And this concludes today's Math Jam!
Valentin Vornicu (19:53:08)
Thanks for being here, we see you next time
