1994 Wisconsin Mathematics Science & Engineering Talent Search PSET 3 Problem 3: Find all positive integer solutions of the equation
\[x^3-y^3=xy+61.\] Solution: My first instinct is that the LHS factors: \[(x-y)(x^2+xy+y^2)=xy+61.\] I see that there is an \(xy\) term on both sides of the equation. Perhaps if I distribute the \(x-y\) on the LHS and then subtract \(xy\). Then, we obtain \[(x-y)x^2+(x-y-1)xy+(x-y)y^2=61.\] This doesn't do me any good, but I notice that I can factor out \(x-y\), I can obtain \[(x-y)\left(x^2+\left(1-\frac{1}{x-y}\right)xy+y^2\right)=61.\] Aha! Now we can equate the two factors on the left to the integer factors of \(61\). Luckily, \(61\) is prime so there are only four cases to test. The only one that ends up working is \(x-y=1\), which yields \[x^2+(x-1)^2=61\Rightarrow 2x^2-2x-60=0\Rightarrow (x-6)(x+5)=0.\] So our two integer solutions are \((6,5)\) and \((-5,-6)\). The only positive integer solution is thus \(\boxed{(6,5)}\). 1994 Wisconsin Mathematics Science & Engineering Talent Search PSET 3 Problem 4: Without using a calculator or computer, determine which of the two numbers \(31^{11}\) or \(17^{14}\) is larger. Solution 1: First, I observed that \(31=2^5-1\) and \(17=2^4+1\). So the ratio between the two given numbers is \[\begin{split} \frac{31^{11}}{17^{14}}&=\frac{(2^5-1)^{11}}{(2^4+1)^{14}}\\ &=\frac{(2^5-1)^{11}}{(2^4+1)^{14}}\cdot\frac{2^{-56}}{2^{-56}}\\ &=\frac{1}{2}\cdot\frac{(1-2^{-5})^{11}}{(1+2^{-4})^{14}} \end{split}\] Since \(\frac{(1-2^{-5})^{11}}{(1+2^{-4})^{14}}<\frac{(1-2^{-5})^{11}}{1}<\frac{1}{1}\), we must have \(17^{14}>31^{11}\). Solution 2: This time, we proceed with the difference instead of the ratio. \[\begin{split} 17^{14}-31^{11}&=(2^4+1)^{14}-(2^5-1)^{11}\\ &=\sum_{k=0}^{14}{\binom{14}{k}2^{56-4k}}-\sum_{j=0}^{11}{(-1)^j\binom{11}{j}2^{55-5j}}\\ &=\sum_{k=0}^{11}{\binom{14}{k}2^{56-4k}+(-1)^{k+1}\binom{11}{k}2^{55-5k}}+\sum_{j=12}^{14}{\binom{14}{j}2^{56-4j}} \end{split}\] The second summation in the last expression above is positive since each term is positive. At this point, I wonder if I could decompose \(\binom{14}{k}\) into a linear combination of terms of the form \(\binom{11}{r}\). I realize that this is actually possible with Pascal's identity: \[\begin{split} \binom{14}{k}&=\binom{13}{k}+\binom{13}{k-1}\\ &=\binom{12}{k}+2\binom{12}{k-1}+\binom{12}{k-1}\\ &=\binom{11}{k}+3\binom{11}{k-1}+3\binom{11}{k-2}+\binom{11}{k-3} \end{split}\] Curiously, the coefficients themselves are binomial coefficients! The proof of that follows pretty naturally. I bet there is a counting argument for it too. Anyway, our first summation can now be written as: \[\begin{split} \sum_{k=0}^{11}{\binom{14}{k}2^{56-4k}+(-1)^{k+1}\binom{11}{k}2^{55-5j}}&=\sum_{k=0}^{11}{\left[\binom{11}{k}+3\binom{11}{k-1}+3\binom{11}{k-2}+\binom{11}{k-3}\right]2^{56-4k}+(-1)^{k+1}\binom{11}{k}2^{55-5k}}\\ &=\sum_{k=0}^{1}{\binom{11}{k}\left(2^{56-4k}+(-1)^{k+1}2^{55-5k}\right)+\left[3\binom{11}{k-1}+3\binom{11}{k-2}+\binom{11}{k-3}\right]2^{56-4k}} \end{split}\] Observe that for due to the definition of generalized binomial coefficients, \(\binom{11}{r}=0\) for negative integers \(r\). Furthermore, we observe that to have \(2^{56-4k}>2^{55-5k}\), we must have \(56-4k>55-5k\) or \(k>-1\). But this is obviously always true for our index \(k\) which starts at \(0\). Hence, every term in the summations is positive. So we must have \(\boxed{17^{14}>31^{11}}\).
0 Comments
Here is a fun one.
1994 Wisconsin Mathematics Science & Engineering Talent Search PSET 3 Problem 2: Suppose that each of the three main diagonals \(\overline{AD}\), \(\overline{BE}\), and \(\overline{CF}\) divide the hexagon \(ABCDEF\) into two regions of equal area. Prove that the three diagonals meet at a common point. Solution: Interesting. First, I drew the proper configuration. Where the diagonals concurred at point \(P\) and each split the hexagon into regions of equal area. In this case, six triangles were formed. I let \(T_1=\triangle APB\), and likewise labelled the rest of the triangles, proceeding clockwise with the labeling. Writing our three area conditions in terms of the areas of the \(T_i\)'s, I obtained the system of equations \[\left\{ \begin{array}{ll} [T_1]+[T_2]+[T_3]=[T_4]+[T_5]+[T_6]\\ [T_2]+[T_3]+[T_4]=[T_1]+[T_5]+[T_6]\\ [T_1]+[T_2]+[T_6]=[T_3]+[T_4]+[T_5]. \end{array}\right.\] Wow. There is clearly a massive amount of symmetry in these equations. My instinct is to add them all together. \[3[T_2]+2[T_1]+2[T_3]+[T_4]+[T_6]=3[T_5]+2[T_6]+2[T_4]+[T_1]+[T_3].\] This rearranges to \[2[T_2]+([T_1]+[T_2]+[T_3])=2[T_5]+([T_4]+[T_5]+[T_6]).\] Aha! The sums in the parentheses are equivalent! So \([T_2]=[T_5]\). By symmetry, we must also have \([T_1]=[T_4]\) and \([T_3]=[T_6]\). These results can be obtained explicitly by flipping an equation in our original system before adding all of the equations together. Conveniently, the triangles with equal areas happen to have equal angles since they are formed by the same two diagonals in each instance. Since the area of a triangle is given by \([ABC]=\frac{1}{2}ab\sin{C}\), and the enclosed angles were the same between the pairs of triangles with equal area, the product of the lengths of the enclosing sides must also be the same. So I figured, let \(AP=a\), \(BP=b\), etc. Then, we must have \[\left\{ \begin{array}{ll} af=cd\\ de=ab\\ bc=ef. \end{array}\right.\] At this point, I couldn't really immediately see anything more insightful about the correct configuration. I wondered how to even prove concurrency. Perhaps, I could work with a configuration that was not correct and show that the configuration could not be correct. So then, suppose that the three diagonals were not concurrent. Then there exists a seventh triangle, \(T_7=\triangle RST\), such that \(R=\overline{AD}\cap\overline{BE}\), \(S=\overline{AD}\cap\overline{CF}\), and \(T=\overline{BE}\cap\overline{CF}\). In this case, let \(T_1=\triangle ASF\), \(T_2=\triangle ARB\), \(T_3=\triangle BTC\), \(T_4=\triangle CSD\), \(T_5=\triangle DRE\), and \(T_6=\triangle ETF\). Incredibly, when we write the area conditions out in this configuration, \([T_7]\) vanishes entirely! The resulting system is identical to what we obtained in the correct configuration, and once again we obtain \([T_1]=[T_4]\), \([T_2]=[T_5]\), and \([T_3]=[T_6]\). The manipulations required to obtain these equalities are slightly trickier, however, as we have to strategically subtract \([T_7]\) from both sides of our simplified sum of three equations. Anyway, we let \(RS=\alpha\), \(ST=\beta\), and \(RT=\gamma\). We define the length from a vertex \(V\) of the hexagon to a vertex of \(T_7\) to be the lowercase of \(V\). Then, turning our area conditions into length conditions using the product of side lengths, we obtain \[\left\{ \begin{array}{ll} af=(c+\beta)(d+\alpha)\\ de=(a+\alpha)(b+\gamma)\\ bc=(e+\gamma)(f+\beta). \end{array}\right.\] Again, I see massive symmetry. This time, my instinct is to multiply the three equations together: \[abcdef=(a+\alpha)(b+\gamma)(c+\beta)(d+\alpha)(e+\gamma)(f+\beta).\] Aha! The product on the RHS is \(\geq abcdef\) since every variable is a length, and thus nonnegative. The equality condition is thus only achieved when \(\alpha=\beta=\gamma=0\). In other words, \(T_7\) must be a degenerate triangle whose vertices, the pairwise intersections of the main diagonals, must coincide at the same point. \(\square\) The Axiom of Choice really grinds my gears.
Given a set of nonempty sets, the set of Cartesian products of all of those sets is obviously also nonempty. That is, we can always choose an element from a nonempty set, even when we can't explicitly define a "choosing function" for an arbitrary set. To make this more clear, we use Bertrand Russell's analogy. Given a bunch of pairs of shoes it is easy to define a function that can take in those pairs and output a particular shoe from each pair. Just let the function choose the left shoe of each pair. But what if we had a bunch of pairs of socks? Socks are indistinguishable so it is no longer clear how we can define a function that can take in a pair of socks and output one from that pair. But this doesn't mean that we can't take a pair of socks and output one from that pair. The Axiom of Choice asserts that despite the fact that we can't explicitly define a function that takes in a pair of socks and spits out a single sock, such a function must still exist because it is obviously not impossible to take an element from a nonempty set. Seriously, who sat down one day and thought about this? Anyway, another topic in the back of my head is figuring out the eigenvector of a two-dimensional rotation. Such a vector must be nonreal since no real vector will yield a multiple of itself when subjected to a rotation that is not a multiple of \(\pi\). This sort of computation could be a blog post on its own. I also wonder about the oscillation of a dipole in an electric field. That could make an interesting paper for the physics section. My old research question of what force fields satisfy the shell theorem also still stands, though I am a little stuck on that mathematically. See here for the result. As far as the math section goes, I don't really know. I plan on uploading all my Putnam stuff once the seminar ends, but beyond that, I have no clue what I should work on next, apart from my running solutions of 100 Geometry Problems. I also have a new number theory book, so once I start working on there, maybe I can make more elaborate number theory things. I'm moving at a snail's pace right now :/ |
Categories
All
Archives
July 2023
|