Solution of the Week #394 - Coin Paradox

Statements 1, 2 and 3 are true.

Statement 1: HTH and HTT will each happen 1/8 of the time.

Statement 2: at some point HT will come up on consecutive throws. The next throw will be H or T with equal probability and so HTH and HTT will have an equal chance of coming up.

Statement 3: the average number of throws to see HT is 4, and as we have seen, the game will finish on the next throw regardless of what it is, so the average number of flips ending in either HTH or HTT is 5.

Statement 4: this seems like it should be true, but it isn’t. On average it will take me 10 throws to see HTH but my friend only 8 throws to see HTT. This is because if my friend reaches HT, she will either finish on the next throw, or have an H to start off a new attempt at HTT. If I’m on HT I will either finish on the next throw or be back at square one.

 

Interestingly, if we make the target sequences differ earlier, for instance HHH vs HTT, then even statements 2 and 3 will be false. HTT would win 3 times out of 5, and the average number of flips when HHH wins would be 5 2/5, whereas the average number of flips when HTT wins would be 5 11/15.

 

Solution of the Week #393 - Two Point Oh Eight

Let’s begin by seeing what happens with four digits, five digits, etc.

With four digits there are two numbers that work: 5252 and 5772.

Since in each case abcd/dcba is equivalent to 52/25, abcd must be a multiple of 52 and dcba must be a multiple of 25. The same multiple in fact.

Let’s take a look at exactly what that multiple is for the first few:

52/25 = 1

572/275 = 11

5252/2525 = 101

5772/2775 = 111

52052/25025 = 1001

57772/27775 = 1111

You might notice that the length of each of these factors is always one less than the number of digits of the final number, because multiplying by 52 or 25 increases the digits by 1. You might also notice that each number is palindromic, because the denominator needs to be the reverse of the numerator. And that it only uses digits 1 and 0, because if you had any digits greater than 1, there would be carrying, which would disrupt the digits of the numerator and the denominator in different ways.

For the 25-digit numbers of the question, we need to find all palindromic 24-digit numbers that are made up of 1s and 0s.

The first digit needs to be a 1 (otherwise the number would not be 25 digits long). The next 11 digits can be either 0 or 1, and the remaining 12 digits are defined by the fact that it needs to be a palindrome.

So we have 11 binary decisions to make. 2^11 = 2048. Therefore there are 2048 25-digit numbers which, when divided by their reversal, equal 2.08. You’ll forgive me for not listing them all, but I’ll pick one at random by flipping a coin:

100010110010010011010001:

5200525720520520572520052/2500252750250250275250025 = 2.08

 

 

Solution of the Week #392 - Shaded Areas

If we let the dimensions of the rectangle be 2x and 2/x, then whatever the value of x, its area will be 4.

This means that the radii of the three semicircles will be:

x, 1/x and (x+1/x)

The area of a semicircle is (pi*r^2)/2, and we want the area of the larger semicircle, less the area of the smaller two. For simplicity we can take out the pi/2:

Area = pi/2 * ((x+1/x)^2 – x^2 – 1/x^2)

Area = pi/2 * (x^2 + 2(x/x) + 1/x^2 – x^2 – 1/x^2)

x gets cancelled out

Area = pi/2 * (2)

Area = pi

And that’s the answer!

Solution of the Week #391 - Five Towns 2

The original puzzle was solved using Pythagorean triples. It’s impossible to find a Pythagorean triple where none of the numbers is divisible by 3.

Instead we can use the cosine rule, which is a kind of generalised version of Pythagoras theorem.

 

a^2 + b^2 - 2ab*cosC = c^2, where C is the angle opposite the side c. (When C is 90, cosC is zero and that whole term disappears).

 

Clearly if a b and c are integers, 2ab*cosC needs to be too. cosC can be anything from 1 to -1. We don’t care if C is rational (in whatever units: degrees, radians, etc), only that cosC is rational.

We need two adjacent central angles to add to 180 degrees. It turns out, conveniently for our purposes, that if C and C’ add to 180 degrees, then cosC and cosC’ add to zero.

 

So now we just need to find a convenient rational value for cosC, for example 1/13, then find a triple a,b,c that satisfies

a^2 + b^2 - 2ab/13 = c^2

none of which is a multiple of 3, for example 13,20,23

and other triples that satisfy

a^2 + b^2 + 2ab/13 = c’^2

with again, no multiples of 3, for example 10,13,17 and 13,40,43

Making a double size copy of 13,20,23 and also doubling 10,13,17 gives us four triangles of alternating central angles, which fit together as shown:

I thank Philip Morris Jones for this solution.

There is one more solution with a total mileage of less than 400 miles. It is based on a value of cosC of 1/5, and triples of 4,5,7 and 7,10,11, with roads leading from the centre with lengths of 50,40,28 and 35, and around the outside of 70,44,49 and 55, giving a total mileage of 371.

Solution of the Week #389 - Strings

There are two overall cases: the 3 digit in the sum could be made from a 1 in the first number and a 2 in the second number, or vice versa.

In the first case, that means the first four digits of the first number must also be 1s, and so the first four digits of the second number must all be 3s. We have no choice. However for the ‘444’ at the end of the sum, we have some choice. The first of those 4s must be 2+2 (as otherwise the first number wouldn’t have any 2s). The last digit must be made of 3+1. However the middle of those 4s could be either, giving us two possibilities.

If instead the 3 in the sum is made of 2 in the first number plus 1 in the second number, now the second half of the sum is completely determined and we have some choice towards the start of the number, three possibilities in fact.

So altogether the five possibilities are:

 

11111223+

33332221

 

11111233+

33332211

 

11122333+

33321111

 

11222333+

33221111

 

12222333+

32221111

 

Solution of the Week #388 - Ten Pin Bowling

As the letter frames are generated randomly from a scrabble set, I can play along myself. I personally achieved a modest score of 114. I began well with a decent spare on frame 1 but frame 2 was a bit of a horror show. On both frames 4 and 7 I made judicious use of the blank to get spares. On frame 5 I only scored 5+4 but there is a scrabble-legal ten letter word available for a strike: DETOXICANT. I didn’t get that without help, so can’t fairly claim it for my own score. However I did score over 100 so I can be happy with my performance.

Solution of the Week #387 - Five Circles

If you start with the smallest triangle and ensure it is a Pythagorean triple, then the radii of all of the circles is bound to be rational, and so can always be scaled up by an appropriate factor to obtain whole numbers. Beginning with a larger triangle and working backwards will not necessarily ensure this.

The best solution is found by starting with a 5-12-13 Pythagorean triple. The radii of the tangent circles for this are found by the semi-perimeter less each of the triangle edges, so 10-3-2.

Using Pythagoras on the second triangle, (10+3),(3+x),(x+10), we find that x needs to be 39/7. We scale up all the numbers we have by a factor of 7 to maintain whole numbers.

On the third and final triangle we now have (70+39),(39+x),(x+70), we find that x is 4251/31. Scaling everything up by a factor of 31, the five radii are:

2170, 434, 651, 1209 and 4251, for a total of 8715.

We might have used a different triangle to begin the construction, but we would have found that the procedure fails when the ratio between the radii of the zero-th circle and the first circle (2170 and 434 in our figure) is 4 or less. So for instance the 3-4-5 triangle would not have worked.

Solution of the Week #386 - Optimal Cone

The formulas for the surface area and volume of an equal right cone are:

Area = pi*r^2*(sqrt(5)+1)

Volume = 2/3*pi*r^3

We want the difference to be a maximum:

A-V = pi*r^2*(sqrt(5)+1)-2/3*pi*r^3

Let’s differentiate:

pi*2r*(sqrt(5)+1)-2/3*pi*3r^2

2*pi*r*(sqrt(5)+1-r)

The (Area-Volume) will be at a maximum when the above expression is equal to 0, or more specifically, when the term in brackets is equal to 0, which is obviously when r = sqrt(5)+1.

To answer the original question, the surface area will be pi*(sqrt(5)+1)^3 ~ 106.464.

Solution of the Week #385 - Odd Prime Cycle

Believe it or not, there are only two possible starting numbers that eventually returns to themselves, 5 and 13:

 

As we saw in the example:

5+1 is divisible by 3

3+2 is divisible by 5

 

13+1 is divisible by 7

7+2 is divisible by 3

3+3 is divisible by 3

3+4 is divisible by 7

7+5 is divisible by 3

3+6 is divisible by 3

3+7 is divisible by 5

5+8 is divisible by 13

 

Any other starting number will at some point reach a power of 2, which has no odd prime factors, without first getting back to the starting number.

For example, the longest sequence (for at some points you have a choice of odd primes) beginning with 101 is: 101 – 17 – 19 – 11 - 5 – 5 – 11 – 3 – 11 – 5 – 3 – 7 – 19 – (32).

Solution of the Week #384 - Mystery Numbers

Let’s first assume that all a,b,c,d are at least 2.

If they were all exactly 2, the triple sum would be 4x2x2x2=32, and the pair sum would be 6x2x2=24, so the triple sum is greater. If we increase any of the numbers, say we change a to 2+e, the triple sum would be increase to 32 + 12e , but the pair sum would only increase to 24 + 6e. In short, the pair sum can never catch up with the triple sum. So our assumption that all numbers were at least 2 is false. Without loss of generality we can let a=1. The equation then becomes:

 

bc + bd + cd + bcd = b + c + d + bc + bd + cd

 

And so bcd = b + c + d

 

Looking for a trio of positive integers whose sum is the same as their product, the only candidate is 1,2,3.

So if our a,b,c,d are (in some order) 1,1,2,3, the triple sum and the pair sum are both equal to 17.

 

Solution of the Week #383 - Smallest Square

Intuitively it makes sense that the basic shape of inner region to be a square with rounded corners. I’ll leave it to the reader to try to prove this.

We need to know what the radius of the rounded corners needs to be.

We can do this by considering a circle, letting the radius vary, and finding when the value of (perimeter – area) is at a maximum.

Perimeter = 2*pi*r

Area = pi*r*r

Perimeter – Area = r*(2-r)*pi

As pi is a constant, we just need the value of r where r*(2-r) is at a maximum. Clearly this is achieved when r=(2-r), so when r=1.

So now we need to find a square with radius=1 rounded corners, whose area is equal to its perimeter. The best way is to split the shape into regions:

The four quarter circles combine to form an entire circle, and then we have an inner square and four rectangles.

Area = pi + 4x + x^2

Perimeter = 2*pi + 4x

Making these equal tells us that x^2 = pi, so x = sqrt(pi).

The side length of the bounding square is therefore sqrt(pi)+2 = 3.772…

Solution of the Week #380 - Prime Balance

The first thing to do is to establish the minimum number of piles.

Clearly if there was 1 pile it would not be balanced around the centre of the disc. Two piles could be balanced but only if they were equal, which is not allowed. Three piles too can only be balanced if equal. Four can only be balanced if opposite pairs are equal.

Five is a little trickier. As we saw with the star balance puzzle it is in fact possible to have five different weights balanced around the centre. It turns out that it isn’t possible for them all to be rational, so clearly can’t all be primes.

So six piles seems our best bet. If you remember back to the pentadecagon balancing puzzle, we could split the weights into subsets of pentagons and triangles. With our six piles we can do something similar, but with triangles and opposite pairs. If we call our piles a to f, we need to find w,x,y,z such that each of the following is prime:

a=x

b=y+w

c=z

d=x+w

e=y

f=z+w

x, y and z each appear in the weights of opposite pairs, and w appears in an equilateral triangle of positions, so the system will balance whatever we choose for w,x,y,z.

Since x,y and z are all primes, and adding w to each gets new primes, w must be even. Trying 2, we need a trio of primes x,y,z that when each is increased by 2 we get three other primes, with no overlap.

Without any loss of generality we can say that x<y<z. If x=3, y cannot be 5, as x+w is already 5. It can’t be 7 either as 7+2 isn’t prime. We try y=11. z cannot be 13 but could be 17.

So with these values of w,x,y,z we have values of a to f of (3,13,17,5,11,19). These total 68 coins. Try as we might with other values for w,x,y,z, we would always need more than 68. And we can also eliminate the possibility of more than six piles: 7 will not give us a rational solution, for the same reasons that 5 won’t. And any more than that, the total of the first n prime numbers already exceeds 68.

So the minimum solution is 68 coins, in piles of 3, 13, 17, 5, 11, 19.

Solution of the Week #379 - So Many Digits

Glossary: a number which only contains 1s, such as 11 or 11111 is called a repunit. All prime numbers with the exception of 2 and 5 divide exactly into a repunit of p-1 digits, and frequently divide exactly into smaller repunits too (some divisor of p-1).

74 is 37 x 2, but we don’t need to worry about the factor of 2, as 3…374 and 1…13…374 will naturally contain exactly one factor of 2 too.

3…374 can be rewritten as 2(1…1 x 150 + 37).

Since 150 and 37 do not share any factors, we are effectively looking for the smallest repunit that 37 divides into. By inspection 37 x 3 = 111, and so therefore our intermediate number will have three 3s: 33374.

For the second part we need to find the smallest repunit that 16687 (half of 33374) divides exactly into. The first thing we need to do is to decompose 16687 into its prime factors. 16687 = 11 x 37 x 41.

11 itself IS a repunit, specifically the second repunit, so the number of 1s we need must be even. From the fact that 37 divides into 111, the number of 1s must also be a multiple of 3.

We can use modular arithmetic to find the first repunit that 41 divides into:

1(mod41), *10+1=11

11=11(mod41), *10+1=111

111=29(mod41), *10+1=291

291=4(mod41), *10+1=41

41=0(mod41)

Therefore 41 divides into the fifth repunit 11111 (in fact it’s 271 x 41), and so the number of 1s in the final answer will also be a multiple of 5.

Since these 2, 3 and 5 are relatively prime, their lowest common multiple is merely their product: 30. So our number will have 30 1s, followed by 33374, so 35 digits altogether:

 

11,111,111,111,111,111,111,111,111,111,133,374

Solution of the Week #378 - Star Balance

Unlike we saw with the 15-sided shape a couple of weeks ago, 5 is prime and so cannot be broken down into products. But since the five piles need to be different, we do still need to find a way of placing a subset of weights such that they balance. One way would be to have 1kg blocks at two adjacent vertices, and then to calculate what the opposite vertex would need to be to balance.

We can call the distance from the middle to each of the vertices ‘d’. Two 1kg weights on adjacent vertices ‘d’ from the middle would be equivalent to 2kg midway between those two points. That midway point is about 0.8*d from the centre. To balance this with a single weight ‘d’ from the centre on the opposite side, the distance multiplied by the weight needs to come to the same value. 0.8d x 2kg = d x 1.6kg. This lies between 1kg and 2kg as the question dictates.

A bit more precise calculation and this balancing block needs to weigh ‘phi’ kg. Phi is the golden ratio, equal to (sqrt(5)+1)/2 or ~1.618.

A bit more precise calculation and this balancing block needs to weigh ‘phi’ kg. Phi is the golden ratio, equal to (sqrt(5)+1)/2 or ~1.618.

So, we have an arrangement which balances with three blocks: one at ~1.618kg and two at 1kg. How many of these three-block arrangements do we need to make the five piles all different? We can do it with just three of them. Place 1 heavy block on a vertex, 2 heavy blocks to an adjacent vertex, and the 1kg blocks required to balance them will be in piles of 1, 3 and 2.

So, we have achieved a balance using nine blocks in total: six 1kg blocks and three ~1.618kg blocks. The weight at each vertex is: ~1.618kg, ~3.236kg, 1kg, 3kg, 2kg.

How about now, we see what happens if we place two of the heavy weights on adjacent vertices and calculate what we would need in the single opposite vertex to rebalance the star? Since the pair of weights are scaled up by phi from our original (1,1,phi) subset, the balancing vertex will also be, and will equal to (phi)^2. But because phi is such a special number, (phi)^2 is equal to phi+1, which we can achieve by using one of each of our two weights. Now if we combine one (1,1,phi) subset, and one (phi,phi,phi+1) subset, we can have a different weight on each vertex and balance the star, but this time only using seven weights in total, three of 1kg and four of ~1.618kg. The weight at each vertex is: ~1.618kg, ~3.236kg, 0kg, ~3.618kg, 1kg.

Solution of the Week #377 - Cyberpunk Number

The basic way to solve this is to realise that the first 1/9 of letter strings start with B, the next 1/9 start with C, etc. And then within a 1/9 section, the first 1/8 start with the first available letter, and so on.

The most intuitive approach is to discard all those strings that come before CYBERPUNK, counting the discarded strings as we go.

So firstly, because C is 2nd alphabetically, we discard any strings that start with B, which is 1/9 of them, or 40320 (1/9 of 9! is simply 8!). Of the remaining letters Y is 8th, so within the 1/9 that start with C, we want to discard the first 7/8 of them, or 35280 (which is 7*7!), etc.

Mathematically how this works is to express the word CYBERPUNK with numbers detailing where each letter comes alphabetically out of the letters remaining at that point. So C is second out of BCEKNPRUY. Then Y is 8th out of BEKNPRUY, B is first out of BEKNPRU, E is first out of EKNPRU, etc. This gives (2,8,1,1,4,3,3,2,1).

Because we want to discard all of the strings before CYBERPUNK, we subtract 1 from each of those numbers to get (1,7,0,0,3,2,2,1,0), and then we need to multiply each of those numbers by the appropriate factorial, and add them together: 1*8!+7*7!+0*6!+0*5!+3*4!+2*3!+2*2!+1*1!+0*0!

40320+35280+0+0+72+12+4+1+0=75689.

But remember, this is the number of strings before CYBERPUNK, so the actual CYBERPUNK number is the next one: 75690.

To answer the bonus question, we need to the same thing but in reverse. To start with we need to subtract 1 to get 99,999. We then need to express that as the sum of factorials 8! to 0! : (2*8! + 3*7! + 5*6! + 5*5! + 1*4! + 2*3! + 1*2! + 1*1! + 0*0!). Then we need to add 1 to each of these: (3,4,6,6,2,3,2,2,1). Finally, we write out the nine letters in alphabetical order: BCEKNPRUY, and the first of our word string will be the 3rd in alphabetical order: E. Then second in our string will be the 4th in alphabetical order (of those letters than haven’t been used yet), etc. The 100,000th string will therefore be ENUYCPKRB.

Solution of the Week #376 - Balancing Act

It is tempting to think you can exactly mirror the arrangement of weight on the left-hand side, so to have 0 at A, 2kg at B and 1kg elsewhere, however this gives a centre of gravity that is a little way above the centre of the shape, slightly in the direction of A.

Instead, we can use the fact that 15 is the product of 5 and 3. A subset of five weights equally spaced (on a regular pentagon) around the shape will have a centre of gravity at the centre of the shape. Likewise, three weights, equally spaced (on an equilateral triangle) will also be balanced. We are looking to place 16 weights altogether, which suggests we can divide it into two pentagons and two triangles, since 5+5+3+3=16. Since we know O has 2kg, we can place both a pentagon and a triangle on that vertex, but that leaves K, M and N short of a weight. We can then place a pentagon through K and N, and a triangle through M. This completes the given weights on the left-hand side, and also determines the positions of the other eight weights on the right-hand side, such that A, D and G have no weight, B and F have a 1kg weight, and C, E and H have 2kg.

As for the bonus question, with now 17 weights in total, the only way to make this a sum of 3s and 5s is 5+4*3. The only way to do this with five of the positions I to O containing 1kg is to have the pentagon CFILO and the four triangles EJO, AFK, CHM and DIN. This will rearrange the 8 weights on A to H as 10211201, and the positions I and O will have the extra weights on the left-hand side.