A triangular number is a number of the form $n(n+1)/2$, where $n$ is a positive integer. Prove that $1$, $11$, $111$, $1111$, $\ldots$ are all triangular numbers in base $9$.
Solution: The proof is by mathematical induction. The first number, $1$, is triangular: $1=\frac{1(1+1)}{2}$. Each successive number is $9$ times the previous number (which puts a $0$ at the right) plus $1$. We claim that the operation of multiplying a number by $9$ and adding $1$ transforms any triangular number into another triangular number. Let's see:
\[
9 \frac{n(n+1)}{2}+1=\frac{9n^2+9n+2}{2}=\frac{(3n+1)(3n+2)}{2}.
\]
This is a triangular number. And that completes the proof.
The operation ``multiply by $9$ and add $1$,'' used to produce new triangular numbers, can be generalized. If $k$ is a positive integer, multiplying any triangular number by $(2k+1)^2$ and adding $k(k+1)/2$ gives another triangular number. This is because of the identity
\[
(2k+1)^2\frac{n(n+1)}{2}+\frac{k(k+1)}{2}=\frac{[(2k+1)n+k][(2k+1)n+k+1]}{2}.
\]
For example (with $k=2$), multiplying any triangular number by $25$ and adding $3$ gives another triangular number. It follows that $3$, $33$, $333$, $3333$, $\ldots$ are all triangular numbers in base $25$.
My math page: https://sites.google.com/site/martinerickson/
Sunday, July 22, 2012
Tuesday, July 10, 2012
Chess on an Infinite Board
Two players (White and Black) are playing on an infinite chess board (extending infinitely in all directions).
First, White places a certain number of queens (and no other pieces) on the board.
Black then places a king on any unoccupied, unattacked square of the board.
The players take turns moving until Black is checkmated.
What is the minimum number of queens White needs to force a checkmate?
Answer the same problem if White starts with rooks instead of queens.
Do the same for bishops and knights.
Let Q, R, B, and N be the minimum number of queens, rooks, bishops, and knights, respectively. What is the sum 1/Q + 1/R + 1/B + 1/N?
This problem appeared as the IBM Research "Ponder This" challenge of December 2011. The problem and solution may be found at: http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2011.html
My math page: https://sites.google.com/site/martinerickson/
This problem appeared as the IBM Research "Ponder This" challenge of December 2011. The problem and solution may be found at: http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2011.html
My math page: https://sites.google.com/site/martinerickson/
Saturday, July 7, 2012
Lines on a Hyperbolic Paraboloid
A ruled surface has the property that through every point on the surface there is a straight line lying on the surface. Cylinders and cones are ruled surfaces. Another example is a hyperbolic paraboloid (a saddle surface). In fact, a hyperbolic paraboloid contains a pair of straight lines through any given point on it. Find equations of a pair of lines through the point $(1,2,3)$ on the hyperbolic paraboloid $z=y^2-x^2$. Prove that these are the only two such lines.
Solution: Remember that a line in space can be given in parametric form $x=x_0+\alpha t$, $y=y_0+\beta t$, $z=z_0+\gamma t$, where $x_0$, $y_0$, $z_0$, $\alpha$, $\beta$, $\gamma$ are constants, and $t \in \mathbf{R}$.
Let $x=1+t$, $y=2+t$. Then \[ z=(2+t)^2-(1+t)^2=3+2t. \] So we have a line $(x,y,z)=(1+t,2+t,3+2t)$. Similarly, let $x=1+t$, $y=2-t$. Then \[ z=(2-t)^2-(1+t)^2=3-6t. \] So we have a line $(x,y,z)=(1+t,2-t,3-6t)$.
We will prove that these are the only two lines on $z=y^2-x^2$ through $(1,2,3)$. Assume that $x=1+\alpha t$, $y=2+\beta t$. Then \[ z=(2+\beta t)^2-(1+ \alpha t)^2=4+4 \beta t + \beta^2 t^2 -1- 2 \alpha t - \alpha^2 t^2. \] In order for us to have a line, the coefficient of $t^2$ must be zero. Hence $\alpha^2=\beta^2$, and $\beta= \pm \alpha$. For definiteness, assume that $\alpha=1$. Then $\beta=\pm 1$, and we have the two cases above.
We could make the same kind of argument to show that given any point on the surface $z=y^2-x^2$, there are exactly two lines through the point and lying on the surface. But there is a method that renders the computations even easier. We make the change of variables \[ x=X-Y, \quad y=X+Y, \quad z=4Z. \] Then \[ 4Z=(X+Y)^2-(X-Y)^2=X^2+2XY+Y^2-X^2-Y^2+2XY, \] and we obtain the particularly simple equation \[ Z=XY. \] The critical thing is that the change of variables is linear; lines are mapped to lines. In our problem, the point was $(1,2,3)$. Under the change of variables, this becomes $(\frac{3}{2},\frac{1}{2},\frac{3}{4})$. The lines that pass through this point and lie on the saddle surface have either $X$ or $Y$ constant: \[ (X,Y,Z)=\left(\frac{3}{2}+s,\frac{1}{2},\frac{3}{4}+\frac{1}{2}s\right) \quad \mbox{and} \quad (X,Y,Z)=\left(\frac{3}{2},\frac{1}{2}+t,\frac{3}{4}+\frac{3}{2}t\right). \] In general, the two lines passing through the point $(X_0,Y_0,Z_0)$ and lying on the surface $Z=XY$ are \[ (X,Y,Z)=(X_0+s,Y_0,Z_0+sY_0) \quad \mbox{and} \quad (X,Y,Z)=(X_0,Y_0+t,Z_0+tX_0). \] Thus we have two families of lines that rule the saddle surface. The lines in each family do not intersect because if two such lines intersected, the intersection point would be on three lines on the saddle surface. Furthermore, every pair of lines from different families intersect. For two such lines have equations \[ (X,Y,Z)=(X_1+s,Y_1,Z_1+sY_1) \quad \mbox{and} \quad (X,Y,Z)=(X_2,Y_2+t,Z_2+tX_2), \] and it is easy to see that the lines intersect at the point $(X_2,Y_1,X_2Y_1)$, when $s=X_2-X_1$ and $t=Y_1-Y_2$.
My math page: https://sites.google.com/site/martinerickson/
Let $x=1+t$, $y=2+t$. Then \[ z=(2+t)^2-(1+t)^2=3+2t. \] So we have a line $(x,y,z)=(1+t,2+t,3+2t)$. Similarly, let $x=1+t$, $y=2-t$. Then \[ z=(2-t)^2-(1+t)^2=3-6t. \] So we have a line $(x,y,z)=(1+t,2-t,3-6t)$.
We will prove that these are the only two lines on $z=y^2-x^2$ through $(1,2,3)$. Assume that $x=1+\alpha t$, $y=2+\beta t$. Then \[ z=(2+\beta t)^2-(1+ \alpha t)^2=4+4 \beta t + \beta^2 t^2 -1- 2 \alpha t - \alpha^2 t^2. \] In order for us to have a line, the coefficient of $t^2$ must be zero. Hence $\alpha^2=\beta^2$, and $\beta= \pm \alpha$. For definiteness, assume that $\alpha=1$. Then $\beta=\pm 1$, and we have the two cases above.
We could make the same kind of argument to show that given any point on the surface $z=y^2-x^2$, there are exactly two lines through the point and lying on the surface. But there is a method that renders the computations even easier. We make the change of variables \[ x=X-Y, \quad y=X+Y, \quad z=4Z. \] Then \[ 4Z=(X+Y)^2-(X-Y)^2=X^2+2XY+Y^2-X^2-Y^2+2XY, \] and we obtain the particularly simple equation \[ Z=XY. \] The critical thing is that the change of variables is linear; lines are mapped to lines. In our problem, the point was $(1,2,3)$. Under the change of variables, this becomes $(\frac{3}{2},\frac{1}{2},\frac{3}{4})$. The lines that pass through this point and lie on the saddle surface have either $X$ or $Y$ constant: \[ (X,Y,Z)=\left(\frac{3}{2}+s,\frac{1}{2},\frac{3}{4}+\frac{1}{2}s\right) \quad \mbox{and} \quad (X,Y,Z)=\left(\frac{3}{2},\frac{1}{2}+t,\frac{3}{4}+\frac{3}{2}t\right). \] In general, the two lines passing through the point $(X_0,Y_0,Z_0)$ and lying on the surface $Z=XY$ are \[ (X,Y,Z)=(X_0+s,Y_0,Z_0+sY_0) \quad \mbox{and} \quad (X,Y,Z)=(X_0,Y_0+t,Z_0+tX_0). \] Thus we have two families of lines that rule the saddle surface. The lines in each family do not intersect because if two such lines intersected, the intersection point would be on three lines on the saddle surface. Furthermore, every pair of lines from different families intersect. For two such lines have equations \[ (X,Y,Z)=(X_1+s,Y_1,Z_1+sY_1) \quad \mbox{and} \quad (X,Y,Z)=(X_2,Y_2+t,Z_2+tX_2), \] and it is easy to see that the lines intersect at the point $(X_2,Y_1,X_2Y_1)$, when $s=X_2-X_1$ and $t=Y_1-Y_2$.
My math page: https://sites.google.com/site/martinerickson/
Friday, July 6, 2012
The Age of Diophantus
Diophantus of Alexandria (c. 200--c. 284 CE) discovered methods for finding integer or rational solutions to certain types of algebraic equations. A riddle from the 5th century purports to express the number of years that Diophantus lived (it isn't known whether the facts in the riddle are accurate):
Diophantus lived one-sixth of his life as a child, then one-twelfth of his life later he grew a beard. After another one-seventh of his life he married, and five years after that he had a son. His son lived only half as long as he did. Four years after his son's death, Diophantus died. How many years did Diophantus live?
Solution: Since the riddle talks about one-twelfth of Diophantus' life and one-seventh of his life, we guess that the number of years he lived is a multiple of both $12$ and $7$, and hence a multiple of $84$. But the only multiple of $84$ reasonable for a human lifespan is $84$, and we see that $84$ years satisfies the conditions of the problem:
\[
\frac{84}{6}+\frac{84}{12}+\frac{84}{7}+5+\frac{84}{2}+4=14+7+12+5+42+4=84.
\]
The reasonable guess succeeded. We can also solve the problem directly. Let $x$ be the number of years Diophantus lived. Then
\[
\frac{x}{6}+\frac{x}{12}+\frac{x}{7}+5+\frac{x}{2}+4=x.
\]
Hence
\[
9=x\left(\frac{9}{84}\right),
\]
and $x=84$.
My math page: https://sites.google.com/site/martinerickson/
Subscribe to:
Posts (Atom)