Archive for Puzzles

Permutable Dates

Gregorus seems to have already posted about this, but I can post my solution. We came up with the puzzle of finding the 8-digit number (with zeros allowed at the beginning) which has the largest possible number of permutations that are possible dates. Some numbers like 99,999,999 don’t have any. Others like 01,234,567 have a lot (starting with 01/23/4567, and most of those digits can be swapped around).

I wrote my program in the Bash shell language and it has two lines.

Line One:

perl -e 'useĀ  Date::Manip; my $d = ParseDate("01/01/0001");while(UnixDate("%Y") < 10000) {print UnixDate($d,"%m%d%Y\n"); $d = DateCalc($d, "+ 1 day");}' >> all-dates.txt


This just makes all the possible dates, one day at a time. Perl’s Date::Manip module is notoriously slow, and it took almost two hours to make all 3,652,059 dates in this millenium (not quite actually: the last year of the millenium has a five digit year). As for the delay, I rationalized that I had optimized my code for “programmer time”.

Line Two:

perl -ne 'print join("", sort (split("", $_)))' all-dates.txt | sort | uniq -c | sort -n


This sorts the digits in each date to make ordered digit clusters, then orders the clusters of digits by how many times they appear.

The results? 00,123,578 will make 2,472 dates! Of course, it is a 20,160-way tie, because any permutation of 00,123,578, such as 57,800,123 will make the same 2,472 dates.

Unfortunately, I can’t make any dates near to us from 00,123,578. The closest I can get on both sides is 07/08/2135 and 03/20/1875. Can anyone do better?

Advertisements

Comments (2)

Clockwork Powers

Here’s another problem I’ve been looking at lately:

Find a number $x$, such that if $j$ is any digit from 0 to 9, $x^{j}$ has $j$ as its first digit past the decimal point. For instance, 63.18 works for the first power $(63.18^{\b{1}} = 63.\b{1}8)$ and the third power $(63.18^{\b{3}} = 252196.\b{3}89432)$, but it doesn’t work for the second $(63.18^{\b{2}} = 3991.\b{7}124)$ where the first digit is 7 instead of 2.

Hint: The smallest such number is less than 10.

To prove that the problem is possible to solve quickly, I’ll provide the solution to a more complicated version. Suppose that the first two digits of $x^{j}$ must match $j$ instead of just the first one. This means that $x^{3}$ has “03” just to the right of the decimal point all way to up to $x^{99}$ having “99” just after the decimal point. Then the smallest solution is the following number:

95.01063709417263364386569653065071891390859441647675346849
01552762611728856071543459219055118914594166160224386992990
49592128996983422861693601042135900702684741868297684742429
253949832737577847233354…

The smallest solution’s digits actually never end so I had to cut it off somewhere. I choose the cut off point to be the first place where the remaining digits still worked. In other words, if you truncated the 4 off of the end, the number would be changed too much and would fail to meet all the conditions. Furthermore, I was forced to round up (because anything smaller doesn’t work).

Leave a Comment

The Monkey Problem

I’ve been forwarded a classic problem, in bold below.

The Monkey Problem

A rope over the top of a fence has the same length on each side, and weighs one-third of a pound per foot. On one end hangs a monkey holding a banana, and on the other end a dead-weight equal to the weight of the monkey. The banana weighs 2 ounces per inch. The length of the rope in feet is the same as the age of the monkey, and the weight of the monkey in ounces is as much as the age of the monkey’s mother. The combined ages of the monkey and its mother are 30 years. One-half the weight of the monkey, plus the weight of the banana is one-fourth the sum of the weights of the rope and the dead-weight.

The monkey’s mother is one-half as old as the monkey will be in when it is three times as old as its mother was when she was one-half as old as the monkey will be when it is as old as its mother will be when she is four times as old as the monkey was when it was twice as old as its mother was when she was one-third as old as the monkey was when it was as old as its mother was when she was three times as old as the monkey was when it was one-fourth as old as it is now.

How long is the banana in inches?

In fact, I’ve seen this problem back when I was kid, though I’ve never tried to solve it, mostly because that last paragraph looked tedious and as though it would require a deeply nested set of multiplied and offset variables. It turns out however, to be simpler than I imagined. Here we go….

A rope over the top of a fence has the same length on each side, and weighs one-third of a pound per foot.

Everything else in the problem uses ounces, so let’s make it consistent. We’ll make up variables as go along. First we need rope weight and rope length.

\begin{eqnarray*}RW = RL * 1/3 * 16\end{eqnarray*}

On one end hangs a monkey holding a banana, and on the other end a dead-weight equal to the weight of the monkey.

Add in variables for Dead Weight and Monkey Weight.

\begin{eqnarray*}DW = MW\end{eqnarray*}

The banana weighs 2 ounces per inch.

Add in variables for banana weight and banana length.

\begin{eqnarray*}BW = 2 * BL\end{eqnarray*}

The length of the rope in feet is the same as the age of the monkey

Rope Length and Monkey Age.

\begin{eqnarray*}RL = MA\end{eqnarray*}

… and the weight of the monkey in ounces is as much as the age of the monkey’s mother.

Add in MMA for Monkey Mother Age.

\begin{eqnarray*}MW = MMA\end{eqnarray*}

The combined ages of the monkey and its mother are 30 years.

\begin{eqnarray*}MA + MMA = 30\end{eqnarray*}

One-half the weight of the monkey, plus the weight of the banana is one-fourth the sum of the weights of the rope and the dead-weight.

\begin{eqnarray*}1/2 * MW + BW = 1/4(RW + DW)\end{eqnarray*}

The monkey’s mother is one-half as old as the monkey will be in when it is three times as old as its mother was when she was one-half as old as the monkey will be when it is as old as its mother will be when she is four times as old as the monkey was when it was twice as old as its mother was when she was one-third as old as the monkey was when it was as old as its mother was when she was three times as old as the monkey was when it was one-fourth as old as it is now.

\begin{eqnarray*}MMA = \frac{1}{2} ( 3 ( \frac{1}{2} ( 4 ( 2 ( \frac{1}{3} ( 3 ( \frac{1}{4} MA)))))))\end{eqnarray*}

How long is the banana in inches?

\begin{eqnarray*}\textrm{Find } BL\end{eqnarray*}

No doubt these equations are easy to solve by hand, but why settle? We can write them in a form that can be solved by computer. Right now, I prefer the mathematical software Sage . Formatted for Sage, the equations look like this:

var('RW, RL, DW, MW, BW, BL, MA, MMA')
equations = [
RW == RL * 1/3 * 16,
DW == MW,
BW == 2 * BL,
RL == MA,
MW == MMA,
MA + MMA == 30,
1/2 * MW + BW == 1/4 * (RW + DW),
MMA == 1/2 * (  3 * ( 1/2 * ( 4 * ( 2 * ( 1/3 * ( 3 * ( 1/4 * MA)))))))]
s = solve(equations, RW, RL, DW, MW, BW, BL, MA, MMA, solution_dict = True) 
print s

And the output is:

18\}\end{eqnarray*}

Notice the banana weighs 11.5 ounces and the monkey only weighs 18 oz., so something is little implausible about the problem, but as mathematicians, that’s not our problem…

Comments (1)

Divisible by 7, Both Ways

Author’s Update on 7/26/08: I submitted these numbers to the On-Line Encyclopedia of Integer Sequences. You can see a much longer list of the sums here.

I briefly wrote about this several years ago, but with my newfound powers of publishing LaTeX to the web, I feel that it can be made more accessible now.

Here’s the math problem, which sounds innocent enough:
Find the sum of all integers $i$ between 0 and $10^{6}$ (one million) such that both $i$ and the reverse of $i$ are divisible by 7. More generally, replace $10^{6}$ by $10^N$ and find an algorithm that works for any $N$.

Just to work up to this a bit, if those extra conditions did not exist, the problem would be easy. Ignoring 0, there are exactly $10^{6}$ integers between 1 and $10^{6}$, and they can be paired off into $\frac{10^{6}}{2}$ sets: $[1, 10^{6}], [2, 10^{6}-1],$ all the way up to the last set $[\frac{10^{6}}{2}-1,\frac{10^{6}}{2}]$. Each of these sets has the same sum: $10^{6}+1$. Therefore the sum of all the numbers is just $\frac{10^{6}}{2} \times (10^{6}+1) = 500,000,500,000$.

In addition, if the divisible-by-7 condition did exist, but not the condition on the reverse of $i$, it would also be relatively easy. The numbers to add would be the multiples of 7: $0, 7, 14, 21...$ up to $ ..., 999,999$. We can divide each of these numbers by 7, add them, then multiply the product by 7 at the end. That addition can be done the same way as in the above paragraph and we end up with $\frac{142857}{2} \times (142857 + 1) \times 7 = 71,428,928,571$.

It is the condition on $i$‘s reverse that makes this hard. Qualifying numbers start out 0, 7, 70, 77, 161, 168, 252, 259…, and end with …999838, 999922, 999929, 999992, 999999. There doesn’t seem to be anything obvious about the digits themselves, nor anything very regular about the spacing between the numbers (which was the key to the intermediate problem with only one condition).

However, we can solve this problem using Dynamic Programming with Modular Arithmetic. First, let’s look at the more general problem.

Breaking Down

Let $F(n, m, x, y)$ be the number of integers $i$ with $ n \le i < m$ and $i \equiv x$ (mod 7) and $Reverse(i) \equiv y$ (mod 7). Similarly, let $G(n, m, x, y)$ be the sum of those integers. $G(0, 10^N, 0, 0)$ is the answer to the our question, by definition, but first let’s look at $F(0, 10^N, 0, 0)$. It will turn out that we can use this to calculate $G(0, 10^N, 0, 0)$.

Observe that $F(0, 10^N, x, y)$ can be represented as the sum of 10 instances of $F$ over intervals of size $10^{N-1}$, one for each possible first digit (left padding with zeros to ensure N digits).

$\displaystyle F(0, 10^N, x, y) = \sum_{i=0}^9 F(10^{N-1}i, 10^{N-1}(i+1), x, y)$     (1)

As an example, what Equation (1) is saying is that

$\displaystyle F(0, 100, 0, 0) = F(0, 10, 0, 0) + F(10, 20, 0, 0) + ... + F(90, 100, 0, 0)$     (2)

This is because however many numbers there are between 0 and 100 with our divisibility properties, they are divided up among the ranges [0,9], [10,19], [20,29] up to [90,99]. If we count the numbers in those bins up separately and then add the totals for the bins, it will come at the same as if the numbers are counted up all at once.

We will characterize the numbers counted by each of the summands in Equation (2) in order to fold them together. The property we use to relate $F$ functions over different intervals comes from the digits of the numbers. Let $id_1d_2d_3 \dots d_N$ be an $N+1$-digit number, with first digit $i$. Then,

$\displaystyle id_1d_2d_3 \dots d_N$ $\textstyle =$ $\displaystyle i \times 10^{N} + d_1d_2d_3 \dots d_N$ (3)
$\displaystyle d_N \dots d_3d_2d_1i$ $\textstyle =$ $\displaystyle i + 10 \times d_N \dots d_3d_2d_1$ (4)

That is, every number in an interval $\left[10^{N}(i-1), 10^Ni\right]$ can be mapped to a number in $\left[0, 10^{N-1}\right]$ with quantifiable changes to its (and its reverse’s) residue modulo 7, simply by removing the first digit. In particular, by (3) and (4) this reduction is

$\displaystyle F(10^{N}(i-1), 10^Ni, x, y) = F(0, 10^N, x - 10^Ni, 10^{-1}(y - i))$     (5)

For example, each number in the interval [60, 69], can be mapped onto a one digit number by removing the tens digit, 6 (e.g, 62 becomes 2). If we were trying to calculate $F(60, 70, 6, 5)$, we could use this relation:

$\displaystyle F(60, 70, 6, 5)$ $\textstyle =$ $\displaystyle F(0, 10, 2, 2)$ (6)

Here’s why: The first 2 comes from the fact that when you subtract 60 from something with a remainder of 6 when divided by 7, the difference has a remainder of $6 - 60 \equiv 2$ (mod 7). The second 2 in Equation (6) is a little harder to see: Removing an initial 6 from a number whose reverse has a remainder of 5 has the effect of removing the last digit from its reverse. Subtracting 6 from a number that had a remainder of 5 changes the remainder to 6, then dividing by 10 changes the remainder to $6 \times 10^{-1} \equiv 6 \times 5 \equiv 2$ (mod 7).

Returning to Equation (2) and applying Equation (5), we have

\begin{eqnarray*}F(0, 100, 0, 0) & = & F(0, 10, 0, 0) + F(10, 20, 0, 0) + F(20,......) + F(0, 10, 0, 0) + F(0, 10, 4, 2) \\& & + F(0, 10, 1, 4) \\\end{eqnarray*}

Notice anything? Three of the terms, $F(0, 10, 0, 0)$, $F(0, 10, 4, 2)$ and $F(0, 10, 1, 4)$, appear twice. That means that rather than examine each number from 0 to 99 as it looked like we might need to do to find $F(0, 100, 0, 0)$, we need only examine the numbers from 0 to 9, 7 times each. We would then sum up the results of those 7 passes, taking care to count a certain three of them twice. That’s a 30% savings, but it doesn’t end there.

Suppose the original problem had been $F(0, 1000, 0, 0)$. We could divide it into 10 subproblems, each ranging from 0 to 100. Then, we could divide each of those up into 10 smaller problems from 0 to 10, then combining the ones that are copies. How many distinct problems would there be at this stage? They all have the form $F(0, 10, x, y)$ and $x$ and $y$ can only be integers in $[0,6]$. That’s only 49 subsubproblems, at the most. Now we have saved more than half the work. For any larger-sized ranges we could think of, the number of subproblems stays limited to 49.

We could find $F(0, 10^{1000}, 0, 0)$ by only looking at $F(0, 10, x, y)$ for 49 sets of $x$ and $y$, then doing a lot of adding!

There are two things left to do: Figure out how to add these subproblems back together and how to get the sum of those numbers, which was the original question.

Summing

Just to make things a little more compact, let $\alpha(N, x,i)$ be equal to $x - 10^Ni$ (mod 7) and $\beta(N, y,i)$ to $10^{-1}(y - i) \equiv 2(y - i) \equiv 2y + 5i$ (mod 7), we have

\begin{eqnarray*}F(0, 10^{N+1}, x, y) = \sum_{i=0}^9 F(0, 10^N, \alpha(N, x,i), \beta(N, y,i))\end{eqnarray*}

Remember the explanation for how we derived Equation (1)? We can carry out a similar reduction on $G$ to get

$\displaystyle G(0, 10^{N+1}, x, y)$ $\textstyle =$ $\displaystyle \sum_{i=0}^9 \Big{[}G(0, 10^N, \alpha(N, x,i), \beta(N, y,i)) +$  
    $\displaystyle \hspace{1em} 10^NiF(0, 10^N, \alpha(N, x,i), \beta(N, y,i))\Big{]}$ (7)

This is somewhat more complicated because when we map $i$-digit numbers to $i-1$-digit numbers, we aren’t changing $F$, which counts the numbers, but we are changing $G$, their sum. We have to add back in contributions made by the removed digits.

Building Back Up

We’ll maintain tables $\mathcal{F}_i$ and $\mathcal{G}_i$ at each level $i$ that hold the multiplicity of each of the $i$-digit subproblems.
To continue our mission to compute $G(0, 10^6, 0, 0)$, we begin by initializing the lowest order $\mathcal{F}$ table as follows below. The colors will be explained in a moment.

\begin{eqnarray*}\mathcal{F}_0 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......0 & 0 & \cellcolor[rgb]{.1,.4,0.4} 0 & 0 \\\hline\end{tabular}\end{eqnarray*}

Only $\mathcal{F}_0[0,0]$ has the value 1 because the only number with “0 digits” is 0, and it and its reverse have residue 0 modulo 7. We can apply Equation (1) to populate $\mathcal{F}_1$. Notice that each element in $\mathcal{F}_1$ is the sum of 7 elements in $\mathcal{F}_0$, 3 of them counted twice. E.g.,

\begin{eqnarray*}\mathcal{F}_1[2,2] & = & F(0, 10^1, 2, 2) \\& = & \sum_{i=0}...... 2) \\& = & \sum_{i=0}^9 F(0, 1, \alpha(0, 2,i), \beta(0, 2,i)\end{eqnarray*}

with $\alpha(0, 2, i) \equiv 2 - i \equiv 2 + 6i$ (mod 7), and $\beta(0, 2, i) = 4 + 5i$. When $i = 0$, this corresponds to the bluest cell (2,4) in $\mathcal{F}_0$. At $i = 1$, we’ve moved up and to the left to a slighter lighter blue cell. As $i$ ranges up to 9, we take a knight’s tour illustrated by the color fading from blue to green. The other cells visited are (1,2), (0,0), wrapping to (6,5), (5,3), (4,1), (3,6), and back to (2,4), (1,2) and (0,0). Notice that the 3 bluest cells are visited twice. In particular (0,0) is visited third and tenth, giving us two 1’s in the sum and $\mathcal{F}_1[2,2] = 2$.

Filling out the rest of $\mathcal{F}_1$,

\begin{eqnarray*}\mathcal{F}_1 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 0 \\& 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\\hline\end{tabular}\end{eqnarray*}

And continuing with $\mathcal{F}_2$,

\begin{eqnarray*}\mathcal{F}_2 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 2 \\& 6 & 2 & 1 & 4 & 2 & 2 & 2 & 1 \\\hline\end{tabular}\end{eqnarray*}

To illustrate the interpretation of this, take $\mathcal{F}_2[5,0]$, in red. This means that are 4 numbers between 0 and 100 which have a remainder of 5 when divided by seven and when reversed, have a remainder of 0. Sure enough, there are four and they are 12, 19, 82 and 89. Continuing,

\begin{eqnarray*}\mathcal{F}_3 & = &\begin{tabular}{\vert cc\vert ccccccc\ve......& 6 & 19 & 19 & 19 & 19 & 19 & 19 & 28 \\\hline\end{tabular}\end{eqnarray*}

and…

\begin{eqnarray*}\mathcal{F}_4 & = &\begin{tabular}{\vert cc\vert ccccccc\ve...... 195 & 203 & 216 & 186 & 235 & 187 & 206 \\\hline\end{tabular}\end{eqnarray*}

and…

\begin{eqnarray*}\mathcal{F}_5 & = &\begin{tabular}{\vert cc\vert ccccccc\ve...... 2021 & 1994 & 2123 & 2035 & 2100 & 2026 \\\hline\end{tabular}\end{eqnarray*}

At this point, we can extract all the needed values of the $F$-function to generate the $\mathcal{G}_i$ tables, via Equation (7). The $\mathcal{G}_i$ table is built in a similar fashion, except it draws from both $\mathcal{G}_{i-1}$ and $\mathcal{F}_{i-1}$. Unlike $\mathcal{F}_0$, $\mathcal{G}_0$ is entirely zeros. Within an asymptotically constant factor, the numbers in $\mathcal{G}_i$ are the squares of those in $\mathcal{F}_i$. As a result, the $\mathcal{G}_i$ tables must be omitted for space. However, ultimately, we do arrive at our answer $\mathcal{G}_6[0,0] = 10,363,989,636$.

Theoretical Analysis:

In general, for a base $b$ the computation of each subproblem is $\Theta(b)$. With forward and backward divisors $d_1$ and $d_2$, there are $d_1d_2$ subproblems on each of $N$ levels, thus this algorithm requires $\Theta(bd_1d_2N)$ operations. Practically speaking, $G(0, 10^{1000}, 0, 0)$, a number with 1,999 digits, can be calculated in only 14 seconds on my laptop.

More Numbers:

For completeness and for the curious, here are some extended results. The numbers in the range on the left that meet our divisibility conditions have their sum equal to the number on the right.

[0, 1] –$>$ 0

[0, 10] –$>$ 7

[0, 100] –$>$ 154

[0, 1000] –$>$ 10787

[0, 10000] –$>$ 1029567

[0, 100000] –$>$ 105714126

[0, 1000000] –$>$ 10363989636

[0, 10000000] –$>$ 1027216680497

[0, 100000000] –$>$ 102184086890270

[0, 1000000000] –$>$ 10205609904879424

[0, 10000000000] –$>$ 1020424310227628614

[0, 100000000000] –$>$ 102049428685193293045

[0, 1000000000000] –$>$ 10204479595989795520404

[0, 10000000000000] –$>$ 1020425244837350504933851

[0, 100000000000000] –$>$ 102041179796115463104759635

[0, 1000000000000000] –$>$ 10204085511291024760949778376

And the list continues….

Leave a Comment

Concrete Riddling

In trying to make a riddle for someone, I put a famous quote into Google translate in telephone-game style sequence of language translations. The idea was to see if it would come out puzzling but not completely impossible to determine the original saying.

It didn’t work. The first half of the quote is oddly untouched and the second half has collapsed into a single-word non-sequitur. If it only there were a way to compromise on these two extremes.

Here’s the sequence I used: English -> Arabic -> Finnish -> Croatian -> Czech -> Russian -> Japanese -> Dutch -> Chinese -> German -> French -> Greek -> Bulgarian -> Korean -> English.

And here’s the garbled quote:

“Be careful when you fight monsters and concrete.”

Leave a Comment