# POTW 6

If you're in the mood, go have a look at the new Problem of the Week. It's a Shakespeare-themed alphametic this week, with bonus sonnet! It's a bit more challenging than last week's problem (a solution to which has now been posted at the above link), but still doable if you look at it right. So give it a shot!

Incidentally, just to clarify a point that was raised in the comments to last week's POTW, in working out problems of this sort it is taken for granted that the first digit of a number cannot be 0. So, keep that in mind.

Tags

### More like this

##### Sunday Chess Problem
Folks, I entertained tonight. Had actual people over at my house and served them dinner. And quite a dinner it was, if I do say so myself! I prepared filet mignon, with a homemade pan sauce made from balsamic vinegar, Dijon mustard, and chopped onion. For side dishes I roasted some red potatoes…
##### Sunday Function
Last week we did the sinc function. Let's do it again! The function, to refresh our collective memory, is this: Now I was thinking about jumping right into some contour integration, but on actually doing it again I see that it's a little hardcore for one post so eventually when we do it we'll…
##### To Baltimore!
On Thursday I'll be heading up to Baltimore to give a talk at Johns Hopkins University. I'll be discussing an old favorite: The Monty Hall Problem! Actually, it's been about two years since I've given a talk on that particular subject, so it will be nice to have an excuse to revisit it. From…
##### Zero (classic repost)
I'm away on vacation this week, taking my kids to Disney World. Since I'm not likely to have time to write while I'm away, I'm taking the opportunity to re-run an old classic series of posts on numbers, which were first posted in the summer of 2006. These posts are mildly revised. This post…

I found this one a bit easier because there are more constraints than before. I'd like not to be the first one to respond this time, though. Does scienceblogs have math markup in comments? An explanation could be a lot clearer if so.

By Another Matt (not verified) on 12 Oct 2014 #permalink

I don't know if it has math markup in the comments - Jason? Anyway, I believe I have a solution to this, and I believe it is unique. Let's give it a few days so that Jason's students don't just read his blog for the answers. :)

There's a limited version of LaTeX that works in the main posts, but I've never tried it in the comments. Let's see if it works:

$latex \Delta S \geq \int \dfrac{dQ}{T}$

Apparently it does! The math in the previous comment was generated by the code

$latex \Delta S \geq \int \dfrac{dQ}{T} Only with a second dollar sign at the end. I wonder how limited it is? Forgive me this test:$latex \begin{array}{cccccccc}
& & D & O & U & B & L & E \\
& & D & O & U & B & L & E \\
+ & & & & T & O & I & L \\
\hline
T & R & O & U & B & L & E
\end{array}$By Another Matt (not verified) on 13 Oct 2014 #permalink Works. Misplaced space. fixed:$latex \begin{array}{cccccccc}
& & D & O & U & B & L & E \\
& & D & O & U & B & L & E \\
+ & & & & T & O & I & L \\
\hline
& T & R & O & U & B & L & E
\end{array}$Code:$latex \begin{array}{cccccccc}
& & D & O & U & B & L & E \\
& & D & O & U & B & L & E \\
+ & & & & T & O & I & L \\
\hline
& T & R & O & U & B & L & E
\end{array}

By Another Matt (not verified) on 13 Oct 2014 #permalink

By Another Matt (not verified) on 17 Oct 2014 #permalink

Sure.

1. O + O ends in O. Either O = 0 (carry 0), O = 8 (carry 1), or O = 9 (carry 9). In either case, we have a carry of at most 1 into the leftmost column. Thus D is at least 5 (otherwise 2D + 1 would not be >= 10). With a carry of at most 1, even if D = 9 we still have 2D + 1 <= 19, so therefore T = 1. (T = 1).

2. From the fourth column, we have 2B + O + (0 to 2) ends in B. If O = 0, then B is 7, 8, or 9 with a carry of 1. If O = 8, B is 0, 2, 3, or 4 with a carry of 1. If O = 9, B = 0, with a carry of 1. So regardless of I, there must be a carry of exactly 1 into the third column. That means that U + U + 1 + 1 ends in U; this can only be true if U = 8. (T = 1, U = 8).

3. With U = 8, there is a carry of 1 into the second column. From 1, we know this means that O = 9, and hence (from 2) B = 0. (B = 0, T = 1, U = 8, O = 9).

4. Now we know from 1 that D is at least 5, and since we know what 8 and 9 are, it cannot be more than 7. If D = 5, then 2D + 1 = 11, which would mean R = 1. But T = 1, so D is either 6 or 7. If D = 6, R = 3; if D = 7, R = 5. Now, take a look at the rightmost column. 2E + L ends in E. E can be 3 (L = 7), 4 (L = 6), 6 (L = 4), or 7 (L = 3). If E = 3/L = 7, then D and R would have no valid values; similarly if E = 7/L = 3. Therefore E and L are 4 and 6 (not necessarily in that order). So D cannot be 6, therefore D = 7 and R = 5. (B = 0, T = 1, R=5, D = 7, U = 8, O = 9).

5. With E either 4 or 6, 2E + L is either 14 or 16 - a carry of 1 in either case. 2L + I + 1 must give a carry of 1, so 2L + 1 + 1 is between 10 and 19, and ends in L. If L is 4, then I = 5; since R = 5, we know that L must be 6, which means E is 4 and therefore I is 3. (B = 0, T = 1, I = 3, E = 4, R=5, L = 6, D = 7, U = 8, O = 9)

Final equation:

7 9 8 0 6 4
7 9 8 0 6 4
1 9 3 6
-------------------
1 5 9 8 0 6 4

Well that didn't line up properly, sorry about that.

Olayavm.com Açılıyor.

Açılışını 2014 ün 11. ayında yapılacagı
bilinen olayavm.com diger
alışveriş sitelerinin korkulu rüyası oldu
2015 e kadar en uygun fiyatlarla satış
yapılacagı belirtildi. Alışveriş

By mehmet gürbüz (not verified) on 17 Oct 2014 #permalink

Interesting. I took almost the opposite tack. Let's hope I didn't make mistakes in my latex markup!

1. Last week, there were only two addends, so the maximum possible carry value was 1. This week there are three, so you have to watch out for a carry of 2 as well. The other thing to look at is the "rhyme" of "double" and "trouble" is going to be really important, and so it makes sense to look at lower places first.

2. There is no solution to 2x+y=20+x -> x+y=20 or if x and y are single-digit numbers, so the maximum carry for the rightmost place is 1. Likewise, there is no solution for 2x+y+1=20+x -> x+y+1 = 20 for the 10s column. So continuing that logic down the line, the maximum carry is 1 after all.

3. If there is no carry from 1s to 10s, then E and L would both be 0. Therefore 2E+L = 10+L, so E+L=10. Neither E nor L can be 0 or 5. There's a carry of 1 to the 10s place.

4. Similar logic applies to the next three columns to the left -- can 2L+I+1 = L? Obviously not, so there's a carry, and L+I=9. Thus all these columns carry, and so B+O=9, and U+T=9.

5. The O+O column receives a carry of 1, so we have 2O+1 = 10+O; therefore O = 9, and B=0. And because we're never going to get a carry of 2, T = 1. And since U+T=9, U=8.

$latex \begin{array}{cccccccc} & & D & 9 & 8 & 0 & L & E \\ & & D & 9 & 8 & 0 & L & E \\ + & & & & 1 & 9 & I & L \\ \hline & 1 & R & 9 & 8 & 0 & L & E \end{array}$

6. 2D+1=R+10 -> 2D=R+9. So R is odd. Remembering that neither L nor E can be 0 or 5, our final constraints, using the numbers and letters we have left, are as follows:

$latex \begin{array}{cccccccc} R & D & & E & L & & I & L\\ \hline 3 & 6 & & 3 & 7 & & 2 & 7\\ 5 & 7 & & 4 & 6 & & 3 & 6\\ & & & 6 & 4 & & 5 & 4\\ & & & 7 & 3 & & & \end{array}$

7. Looking at that, it's clear that if R=3 and D=6, there are no numbers left over for E & L. So R=5 and D=7. This erases the 2 & 7 and 5 & 4 options for I & L, so I = 3, L = 6, and E = 4. Putting it all together:

$latex \begin{array}{cccccccc} & & 7 & 9 & 8 & 0 & 6 & 4 \\ & & 7 & 9 & 8 & 0 & 6 & 4 \\ + & & & & 1 & 9 & 3 & 6 \\ \hline & 1 & 5 & 9 & 8 & 0 & 6 & 4 \end{array}$

By Another Matt (not verified) on 17 Oct 2014 #permalink

I did POTW 7. oops. I get 45% for that one. It is the least overlap of the two least populous attributes.

You can get lower than 45% -- the overlap of the two smaller populations needn't overlap with both of the larger populations.

Sometimes percentage can be hard to think about. It can be easier to rewrite the problem as though it were about 20 people, say.

By Another Matt (not verified) on 20 Oct 2014 #permalink

For PotW 7, if the four attributes were independent (they aren't in the problem), then the percentage of folks who would do all four activities is .85 * .80 * .75 * .70 = 0.3570. So the answer is not more than that.

It can be helpful also to try solving a similar problem with smaller numbers that are easier to keep in mind. Try it with a total population of 10, and the distributions as .9, .8, .7, and .6. There's a way to get that one to 0% 4-way overlap.

By Another Matt (not verified) on 21 Oct 2014 #permalink

Sorry, did not want to reveal the answer before the deadline. Honestly, I think the answer to POTW #7 is 10%. Did not mean to create a discussion on it yet. Just the sum of the missings.

POTW 7 answer, again hoping my LaTeX markup is not totally screwed up:

1. All the given percentages are divisible by 5, so it's easier to imagine 20 people; 17 do math, 16 play chess, 15 read mysteries, 14 have cats.

2. If we want to minimize the number of people who have all four attributes, we will want to maximize the number of people who have three of the four attributes. Let's say we have x people who have four attributes and 20-x people who have three attributes (the maximum number); moving an attribute from one of the persons with three to another person with three will increase the number of persons with four. No good.

We can begin by making a grid with people along the top and columns along the side:

$latex \begin{array}{r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \hline Math & & & & & & & & & & & & & & & & & & & & \\ \hline Chess & & & & & & & & & & & & & & & & & & & & \\ \hline Mysteries & & & & & & & & & & & & & & & & & & & & \\ \hline Cats & & & & & & & & & & & & & & & & & & & & \\ \hline \end{array}$

$latex \begin{array}{r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \hline Math & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & & & \\ \hline Chess & & & & & & & & & & & & & & & & & & & & \\ \hline Mysteries & & & & & & & & & & & & & & & & & & & & \\ \hline Cats & & & & & & & & & & & & & & & & & & & & \\ \hline \end{array}$

Add 16 chess-players, minimizing the overlap:

$latex \begin{array}{r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \hline Math & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & & & \\ \hline Chess & & & & & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \hline Mysteries & & & & & & & & & & & & & & & & & & & & \\ \hline Cats & & & & & & & & & & & & & & & & & & & & \\ \hline \end{array}$

Add 15 mystery-readers, maximizing the number of people who have two of the three attributes:

$latex \begin{array}{r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \hline Math & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & & & \\ \hline Chess & & & & & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \hline Mysteries & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & & & & & & \bullet & \bullet & \bullet \\ \hline Cats & & & & & & & & & & & & & & & & & & & & \\ \hline \end{array}$

Add 14 cat-owners, finally maximizing the number of people who have three of the four attributes:

$latex \begin{array}{r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ \hline Math & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & & & \\ \hline Chess & & & & & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \hline Mysteries & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & & & & & & \bullet & \bullet & \bullet \\ \hline Cats & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & & & & & & & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet & \bullet \\ \hline \end{array}$

We've minimized the number of people who have all four attributes -- 2 have all four and 18 have three of the four. So 2/20, or 10% is the minimum percentage of the population who share all four attributes given the constraints.

Cross fingers for LaTeX!

By Another Matt (not verified) on 22 Oct 2014 #permalink

Looks like the grids are too wide, but they are images you can open in a new window.

By Another Matt (not verified) on 22 Oct 2014 #permalink

By the way, once you realize that you can systematically maximize attribute "trios," these problems become very easy; all you have to do is subtract the complement of each attribute from 100%:
100%-15%-20%-25%-30%=10%.

By Another Matt (not verified) on 23 Oct 2014 #permalink

First, I did it a hard way:

We have 100 people (to choose a convenient number)
85 of them do math (M)
80 of them play chess (C)
75 of them read mysteries, aka whodunits (W)
70 of them own cats, aka felines (F)

We just start at the beginning with person #1 and let the first 85 do math. the first 80 play chess, and so forth. Thus

70 people do all four {MCWF},
5 do three of the four {MCW-},
5 do two of the three {MC--},
5 do one {M---}, and
15 do none {----}.

This is, of course, the opposite of what we are looking for, being the maximum number that do all four, while we want the minimum.

Consider a person who does all four {MCWF} and a person who does only two {MC--}, We can move either the W or the F from the {MCWF} to the {MC--} to get {MCW-} and {MC-F}. This reduces the number of those who do all four by one.

Similarly, for those who do only one {M---}, we can eliminate two of the {MCWF}'s by moving one of C,W, or F from one {MCWF} and a different one of C,W,F from the other, going from ({MWCF}, {MWCF} {M---}) to ({MWC-}. {MW-F}, {M-CF}). Thus we have, for each of the folks who do only M, reduced the number of all-fours by two.

In a similar manner, we can go from ({MCWF},{MCWF},{MCWF},{----}) to ({MCW-},{MC-F},{M-WF},{-CWF}), reducing the number of all-fours by three.

At this point all 100 people do either three or four, so no more reductions are possible.

As there are 5 {MC--}'s, this reduces the number by 5, and the 5 {M---}'s reduce the number by 2 * 5 = 10, and the 15 {----}'s reduce the number of all-fours by 3*15 = 45.

So we have reduced the number of all-fours by 5 + 10 + 45 = 60. But since there are 70 all-fours to begin with, after a reduction of 60 there are 10 left.

Changing to a fraction, the answer is .10.

And then I realized there was an easy way:

Choose a convenient number, say 100. Over these 100 we need to distribute 85 + 80 + 75 + 70 = 310 predicates. We can distribute the first 300 over the 100 people three each, with 10 left over. So there must be 10 with four, and 90 with only three.

Did anyone work on POTW8 yet? It's a good one.

By Another Matt (not verified) on 28 Oct 2014 #permalink

Another Matt:

I have a solution for PotW 8, but I don't know if I should post it until Friday.

I seem to have a problem typing in my email address properly; I am usually the man-eating dinosaur fir tree.

Rick,

I can't tell you what to do, but I usually refrain from posting POTW solutions until after the due date. I'm sure there are other ways for the students to cheat, but I certainly don't want to participate myself.

One option is to post your calculated total.

Good idea Eric. I came up with what I think is a solution, but I am not totally confident that I didn't make some mistake. My calculated total is 8,439,739,020. If someone comes up with a higher one, I'll know I'm wrong.

Sean, it is just the numbers 1-9, right? No 0?

By Another Matt (not verified) on 29 Oct 2014 #permalink

Sean and Matt,
You've got me beat; mine is 842,864,013 (like Matt, I didn't use the zero). I've been brute forcing it though, so I'll try and give it a little more elegant thought.

Okay just figured out the combo for your two's answers (by brute force; it only took me two variations on my original to get there). Still light on the logic though.

I think I have the logic, but wrote a python script to make sure. Trust but verify!

By Another Matt (not verified) on 29 Oct 2014 #permalink

Yikes! I did the wrong problem. Yes, I did use 0-9. Using 1-9 does indeed give me my original answer divided by 10: 843,973,902. I did this analytically, and I suspect that Matt and I probably had a similar idea.

I actually should have realized that I was doing the wrong problem because when you include 0-9 the solution is no longer unique. One of the numbers ends with zero. If we let x be that number and y the other, it's clear that x/10 * 10y is also a solution - that's equivalent to taking the zero off the end of one number and putting on the end of the other.

Actually, now that I think about it, using the 0 temporarily makes the problem easier to intuit, especially if you know some old SAT/GRE tricks for product maxima.

By Another Matt (not verified) on 29 Oct 2014 #permalink

843,973,902 is also what I have. I also did not allow a 0, just 1 through 9. My logic ends up as rather elegant, but getting there is a bit convoluted.

Hi all. Sorry for pulling another of my disappearing acts. I'm glad the POTW's are attracting so much interest here. Around this time in the semester the number of correct answers I receive from students declines precipitously, so it's nice to see that they are provoking discussion here.

Incidentally, with the posting of POTW 8 I have now exhausted the problems I prepared at the start of the semester. That means I need two more to finish out the term. If anyone knows any really good arithmetic problems that would fit well with the other problems this term, I'd appreciate you directing me towards them.

Jason-
there a a few of this type of puzzle here.

There's always this one:

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?

By Another Matt (not verified) on 30 Oct 2014 #permalink

I have a solution for POTW8, and I can "prove" that it's the best possible solution, but I suspect Jason would not approve of my methods.

The solution is 87531 * 9642 = 843 973 902. As for the proof, I brute forced it with a simple perl script. :) If you assume that the largest possible result must be a 5 digit number multiplied by a 4 digit number - which isn't difficult to show - and that each of the numbers is going to be sorted in descending order of digits - which is again easy to show - then there are 126 possibilities (9 choose 5 - I have no Latex skills, sorry), which is entirely possible to brute force with pen and paper (I'm just way lazier than that).

I of course don't mean to suggest that this is an acceptable answer; I'm working on my logical approach, but it does confirm that this must be the correct answer.

GAZZA -- "Proof by inspection." Here are the top 100, by the way:

87531 * 9642 = 843973902
96421 * 8753 = 843973013
87521 * 9643 = 843965003
96431 * 8752 = 843964112
87532 * 9641 = 843896012
96412 * 8753 = 843894236
87431 * 9652 = 843884012
96521 * 8743 = 843883103
87512 * 9643 = 843878216
96432 * 8751 = 843876432
87421 * 9653 = 843874913
96531 * 8742 = 843874002
875321 * 964 = 843809444
87523 * 9641 = 843809243
96413 * 8752 = 843806576
87432 * 9651 = 843806232
96512 * 8743 = 843804416
875312 * 964 = 843800768
87513 * 9642 = 843800346
96423 * 8751 = 843797673
87412 * 9653 = 843788036
96532 * 8741 = 843786212
964321 * 875 = 843780875
964312 * 875 = 843773000
875231 * 964 = 843722684
874321 * 965 = 843719765
87423 * 9651 = 843719373
96513 * 8742 = 843716646
874312 * 965 = 843711080
87413 * 9652 = 843710276
96523 * 8741 = 843707543
875213 * 964 = 843705332
964231 * 875 = 843702125
965321 * 874 = 843690554
964213 * 875 = 843686375
965312 * 874 = 843682688
874231 * 965 = 843632915
875132 * 964 = 843627248
875123 * 964 = 843618572
874213 * 965 = 843615545
964132 * 875 = 843615500
965231 * 874 = 843611894
964123 * 875 = 843607625
965213 * 874 = 843596162
874132 * 965 = 843537380
874123 * 965 = 843528695
965132 * 874 = 843525368
965123 * 874 = 843517502
87541 * 9632 = 843194912
96321 * 8754 = 843194034
87521 * 9634 = 843177314
96341 * 8752 = 843176432
87542 * 9631 = 843117002
96312 * 8754 = 843115248
87512 * 9634 = 843090608
96342 * 8751 = 843088842
875421 * 963 = 843030423
875412 * 963 = 843021756
87341 * 9652 = 843015332
96521 * 8734 = 843014414
87321 * 9654 = 842996934
96541 * 8732 = 842996012
963421 * 875 = 842993375
963412 * 875 = 842985500
86531 * 9742 = 842985002
97421 * 8653 = 842983913
86521 * 9743 = 842974103
97431 * 8652 = 842973012
87524 * 9631 = 842943644
96314 * 8752 = 842940128
87342 * 9651 = 842937642
96512 * 8734 = 842935808
87514 * 9632 = 842934848
96324 * 8751 = 842931324
87312 * 9654 = 842910048
86532 * 9741 = 842908212
96542 * 8731 = 842908202
97412 * 8653 = 842906036
86512 * 9743 = 842886416
97432 * 8651 = 842884232
86431 * 9752 = 842875112
97521 * 8643 = 842874003
86421 * 9753 = 842864013
97531 * 8642 = 842862902
875241 * 963 = 842857083
873421 * 965 = 842851265
873412 * 965 = 842842580
963241 * 875 = 842835875
875214 * 963 = 842831082
865321 * 974 = 842822654
86523 * 9741 = 842820543
97413 * 8652 = 842817276
865312 * 974 = 842813888
965421 * 873 = 842812533
963214 * 875 = 842812250
86513 * 9742 = 842809646
97423 * 8651 = 842806373
965412 * 873 = 842804676
86432 * 9751 = 842798432
97512 * 8643 = 842796216

By Another Matt (not verified) on 30 Oct 2014 #permalink

Impressive dedication! Exhaustive search is certainly a legitimate proof technique, but it is not very illuminating.

There's a basic principle that says that among pairs of numbers with the same sum, the product will be maximized when the numbers are as close together as possible. This is easily shown with calculus, though you can actually do it just with algebra as well.

So the idea is to build up the two numbers sequentially. It is clear we will want to put the larger digits to the left. So, if we were only going to use two digits, then 9 and 8 would give the largest product. Now we want to tack on the 6 and the 7, and using our principle we see that 96 and 87 will maximize the product. (Of course, you could also just compare the two possibilities. The next step would produce 964 and 875. Then 9642 and 8753. Finally, the 1 gets placed with the smaller number (to keep the two numbers as close as possible) giving us the answer of 9642 and 87531.

Yeah, that's basically how I arrived at my answer. I wasn't sure about the last step at first, but clearly we want one extra 9642 more than one extra 8753.

For someone who knows the principle but isn't sure if it applies to the 5-digit and 4-digit number after you've already constructed the two 4-digit numbers, you can use the 0 temporarily. We know that putting the larger digits on the left and going down to 0, the sum will always be 183,951. Then it's easy to apply the principle and divide by 10. But if you can just divide by 10 at the end anyway, it's clear that the principle holds after all. And I think with the 0, more people might have remembered the principle from their pre-calc days, so leaving it out was a good way to disguise the problem (aside from the non-uniqueness of correct answer).

By Another Matt (not verified) on 30 Oct 2014 #permalink

I completely agree Jason, my technique gets the answer but hardly "shows my work".

My logical approach is essentially trying to build up a proof by induction, which seems similar to your comment. My initial approach was to attempt a proof by contradiction but I didn't seem to be able to get that off the ground (ie "this is the answer; assume that there was a better possibility by moving the digits or rearranging them, and then showing that this led to a smaller result" - I just found that I could find it a particularly elegant construction).

Since answers are being posted, I'll post mine.

I started by noting that in the two numbers, the digits must be in descending order. Thus 21 is larger than 12, 1243 is larger than 1234, etc.

When a single digit is appended onto a number in string form, it is equivalent in numerical form to multiplying the original number by 10 and adding the value of the appended digit. Thus "865" .. "4" (".." is the concatenation operator) gives "8654", which vas a value of 865*10 + 4 of 8654. Since we are disallowing leading 0's, the null string "" goes to 0, that is, "" .. "5" = "5" and 10*0 + 5 = 5.

Assume two different numbers, a and b, and a single digit d, which is to be appended onto one of a or b. Since we are looking for maximal values of the product, we ask which of a .. d or b .. d produces the larger product. This gives the equation
(10*a + d)*b > a*(10*b + d), which solves to b > a. That is, to produce the larger product we append the digit to the smaller of a and b. Thus, for example, if our two numbers are 65 and 43, appending 2 to the smaller gives 65*432 = 28080, which is larger than 652*43 = 28036.

If a = b, then the it doesn't matter which one d is appended to, the product will be the same.

We finally note that, since the digits are in descending order, one of our two resulting numbers must start with the digit with the largest value, here "9". So we now have what we need to proceed.

We start with "9" and "" in string form, 9 and 0 in numerical form, and append the next largest digit, 8. Since 0 is smaller than 9, we append the "8" to the "", giving our two numbers 9 and 8. The next digit is 7, and 8 is smaller than 9, so our numbers are now 9 and 87. continuing with the 6, 9 is less than 87, so we have 96 and 87. And so forth. down to 9642 and 87531. Which gives the product 843,973,902.

Or, is a code form:
--
d = {9,8,7,6,5,4,3,2,1} -- digits we are using in descending order
a = d[1] -- the first (largest) digit in the list d
b = 0
for i = 2,#d do -- for the rest of the digits (#d is the length of the list d)
if a < b then
a = 10*a + d[i] -- a is smaller, so append to a
else
b = 10*b + d[i] -- b is smaller, so append to b
end
end
print( a,b,a*b)
--

Similar logic to some of the others: It is clear that a 5 digit x a 4 digit number is needed to give the correct answer. We can represent a 5 digit number as
a * 10^4 + b*10^3 + c*10^2 + d*10 + e and the four digit number as f*10^3 + g*10^2 + h*10 + i where a through i are the digits 1-9. Algebraically multiplying shows that the product will be
af*10^7 + (bf+ag)*10^6 + (cf+bg+ah)*10^5 + (df+cg+bh+ai)*10^4 + further terms involving 10^3 to 10^0 that are irrelevant to the problem. Now maximizing the coefficients of the powers of ten in the product starting with the highest and working down will yield the answer. For the 10^7 term, there are two possibilities, either a=8 and f=9 or vice-versa. I'll illustrate this case only, since it's the one that leads to the right answer - the logic for the a=9, f=8 case is similar. Since a=8 and f=9, the coefficient of the 10^6 term is 8b+9g. We need to maximize this term. The highest remaining digits are 7 and 6. It's easy to see that g=6 and b=7 does the trick since 9*6 + 8*7 = 110 and 9*7 + 8*6 = 111. In turn, that makes the 10^5 term 8h+9c+42. The highest digits left are 5 and 4, and by similar logic, c=5 and h=4. That makes the 10^4 term 9d+8i+58. The highest remaining digits are 3 and 2. We assign d=3 and i=2. That leaves e=1, and thus 9642 * 87531 = 843,973,902 is the answer.

A couple of folks here have noted that the answer must be a four-digit and a five digit number.

We know from the argument above that the product is larger if a non-zero digit is appended to the smaller number than if it is appended to the larger.

Assume that a and b are the best possible 6-digit and 3-digit numbers, that is, the product is the largest possible for a 6-digit times a 3-digit number.

Take the trailing (non-zero) digit off the 6-digit number, leaving a 5-digit and a 3-digit number. Since there are no leading zeros. the 3-digit is smaller that the 5-digit number. Thus appending the digit removed to the 3-digit number (resulting in a 5-digit and 4-digit number) will have a larger product than appending it back onto the 5-digit number (which restores the original numbers). Thus the maximal product cannot be a 6-digit number times a 3-digit number, since we can, by this procedure, find a 5-digit and 4-digit pair of numbers whose product is larger.

This argument can easily be extended to (8-digit, 1-digit) and (2-digit, 7-digit) cases.

If you assume that the largest possible result must be a 5 digit number multiplied by a 4 digit number – which isn’t difficult to show – and that each of the numbers is going to be sorted in descending order of digits – which is again easy to show

My technique was similar.

Step 1: Start with the assumption that you want the high digits in the high places, so you're going to alternate them: 9753*86421. Also try 97531*8642.

Step 2: take the higher of the two above and then start flipping digits between the two numbers to test.

I reached my initial 'top answer' after about 8 tries. It was wrong, but within 1% of the real top answer. Once this board posted the top value, it took me two more flips to find the right combo, because I was that close.

Not ideal, but I'm okay with that. :)

I noticed I left couple or sentences out of the second paragraph of by comment #44, which leaves the argument that the digits are n descending order incomplete.

I started by noting that in the two numbers, the digits must be in descending order. Thus 21 is larger than 12, 1243 is larger than 1234, etc. In the product between two positive numbers, a*b, if eiterh of a and b is made larger, then the product is also made larger. So it there are two digits not in descending order in either a or b, then swaping those numbers into descending order will make a or b larger, and thus make the product larger.