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.

Solution of the Week #374 - Unit Fractions

1/a + 1/b = 5/391

Change the left-hand side to a single fraction

(a+b)/ab = 5/391

Cross-multiply

391a+391b = 5ab

Move everything to one side

5ab-391a-391b=0

Multiply everything by 5 (so that the coefficient of ab is a square)

25ab-1955a-1955b=0

Add 391^2 to both sides so that the left-hand side can be factorised

25ab-1955a-1955b+391^2=391^2

Factorise the left-hand side

(5a-391)(5b-391)=391^2

Since a and b are positive integers, each of the factors on the left is one less than a multiple of 5, so we must also split the right-hand side into factors that are one less than a multiple of 5. As there are no even factors, this effectively means factors ending in 9. 391 is 17x23, so 391^2 is 17x17x23x23. Numbers ending in 3, when repeatedly multiplied by themselves, end in 1,3,9,7,1,3,9,7, etc. Likewise numbers ending in 7, when repeatedly multiplied by themselves, end in 1,7,9,3,1,7,9,3, etc, moving the opposite way around the same cycle. So the only factors ending in 9 from 17x17x23x23 are 17x17 and 23x23. These equate to 289 and 529.

Let 5a-391=289 and 5b-391=529.

This gives a=136 and b=184. We could just as acceptably assign the factors the other way round to get a=184 and b=136, but these are the only solutions.

Finally, to check:

1/136+1/184 = 23/3128+17/3128=40/3128=5/391

 

Solution of the Week #372 - Totient Trouble

The key to this sequence, and you may have spotted it in the first few terms I gave in the question, are the Fermat numbers: F_n = 2^2^n +1. The first few Fermat numbers are 3, 5, 17, 257, 65537. All five of those numbers are prime, so the totient function of any of them, or any product of a combination of them is as follows:

 

phi(F_a x F_b x F_c) = 2^2^a x 2^2^b x 2^2^c = 2^(2^a + 2^b + 2^c).

 

These first five values cover the subscripts 0 to 4, so by using the properties of binary numbers, we can produce an odd number with a totient function of the for 2^k for any k that can be made by combining different powers of 2.

 

To demonstrate, a selected few are as follows:

 

1 = 2^0

2 = 2^1

3 = 2^1 + 2^0

…

7 = 2^2 + 2^1 + 2^0

8 = 2^3

…

30 = 2^4 + 2^3 + 2^2 + 2^1

31 = 2^4 + 2^3 + 2^2 + 2^1 + 2^0

 

For example, for k=7, the totient function of the number F_2 x F_1 x F_0 = 17 x 5 x 3 = 255 is 2^(2^2 + 2^1 + 2^0) = 2^(4+2+1) = 2^7.

 

So this can give us any power of 2 as a totient of an odd number, as long as the Fermat numbers are prime, however as suggested in the question, this doesn’t continue forever. This is because the next Fermat number F_5 = 4294967297 = 641 x 6700417 and as such is not prime. So when we try to use this method to reach 2^32, the totient function of 4294967297 is not the desired 2^32 = 4294967296, but is in fact 640 x 6700416 = 4288266240. In fact because there are no more known Fermat primes, beyond the first 31 there are no more powers of 2 known to be the totient of an odd number.