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.

 

Solution of the Week #370 - Points of Rotation

If you draw a lines connecting at least two points on the tilted square with the corresponding points on the upright square, then find the perpendicular bisectors of those two lines, then the point that those perpendicular bisectors cross will be in the exact same place in both shapes, and can therefore be used as the centre of rotation of one square to the position and orientation of the other.

There are two obvious ways to do this in the figure so I would regard these as the two easier solutions to find; since the connecting lines are horizontal and vertical, the perpendicular bisectors will be vertical and horizontal.

The lower point has coordinates (1, sqrt(3)), and the upper point has coordinates (-1,2+sqrt(3)).

The other two points can be found using the same method, but now the perpendicular bisectors are not conveniently parallel to the axes, and so the maths is not so straightforward. Nevertheless, the coordinates of the points can be determined to be: (2*sqrt(3)/3-1,sqrt(3)/3+2) and (2*sqrt(3)-3,4-sqrt(3)).

Numerically, to three decimal places, the four points are, from top to bottom: (-1,3.732), (0.155,2.577), (0.464,2.268) and (1,1.732).

Of course, there’s no particular need for the two corresponding points that you choose to connect, to be corners of the square. If instead you chose the exact centre of the two squares, and construct the perpendicular bisector as before, the rotation point will also lie on this line, and since the four different rotation options will all have the same position as the centre of the square, that explains why the four points are collinear.

Solution of the Week #368 - Eleventh Root

While the question says that it must be solved in your head, I’m obviously having to present it here on paper, but hope you’ll agree that the individual steps can be done mentally.

First of all we want to know how many digits in N. If N was 10, N^11 would be 1 followed by eleven zeroes. If N was 100, N^11 would be 1 followed by twenty-two zeroes. Since the N^11 in the question has 19 digits, N must be between 10 and 100, and so therefore has two digits.

Let’s find the last digit first. The final digit of N^11 is 3. Clearly the digit we seek cannot be even. We can try out each of the odd digits. To do this we can repeatedly multiply by a digit and discard all but the final digit, until we get back to where we started. Powers of 5 always end in 5. Powers of 1 always end in 1. Powers of 9 alternate between 9 and 1. So we are left with 3 or 7. 3 follows the repeating pattern 3 - 9 - 7 - 1, and 7 follows the repeating pattern 7 - 9 - 3 - 1, so both could end in a 3. But we are looking for an eleventh power, and since both these sequences are four in length, it is the third in the repeating sequence that we are interested in. Therefore the final digit of N is 7.

Next, since 11 is prime, we can make use of Fermat’s Little Theorem to find out the divisibility of N with respect to 11. The test for divisibility by 11 is very easy: add and subtract alternate digits, and if the result is a multiple of 11, then the original number was too. Determining modulo 11 is similar but now we must make sure that the final digit is added, so in other words all odd-positioned digits need to be added and all even-positioned digits subtracted.

Working through the given number in order:

2-4+7-2+1-5+9-2+1-5+0-8+4-0+1-2+3-0+3 = 3

Since N^11(mod 11) = N(mod 11), we know that N must be three more than a multiple of 11. Since we already know the final digit is 7, we can tell that the first digit is 4.

Therefore N = 47.

Solution of the Week #367 - Come Close But Don't Touch

It turns out the best approach is a kind of ‘greedy’ algorithm, where each unit fraction is the most it can be, given how much is left of the 1 we are trying to almost fill. This is easily calculated: if there is 1/n remaining, the next biggest unit fraction will be 1/(n+1).

So the first unit fraction will be 1/2, leaving 1/2.

Therefore the second unit fraction is 1/3, leaving 1/6.

Next is 1/7, leaving 1/42.

Next is 1/43, leaving 1/1806.

Finally we add 1/1807, leaving us just 1/3263442 short of the 1.

So our final sum comes to 3263441/3263442 = 0.9999996936…

Solution of the Week #365 - Twenty Coloured Balls

Instead of thinking about probability, think in terms of how many different pairs are possible. Since each pair is equally likely, counting the pairs and comparing them is all we need to do.

There are 20 balls altogether, so there are 20 options for the first ball. There are 19 options for the second ball, but since a pair is the same pair if they are drawn in reverse order, we can halve this product. So the total number of possible pairs is 20 x 19 / 2 = 190.

 

We can perform the exact same calculations for each set of same-coloured balls within the bag. For instance if there were 15 red balls, then there are 15 x 14 / 2 = 105 pairs that would be made up of two red balls. This is already more than half of 190, so there cannot be 15 balls of a particular colour.

 

Instead let’s try 14 red balls. This gives us 14 x 13 / 2 = 91 red-red pairs. This is close to the 190 / 2 = 95 pairs we need, so we are on the right track.

 

If there were 3 balls of a second colour (say, blue) then there would be 3 x 2 / 2 = 3 possible blue-blue pairs. Add these to the 91 red-red pairs and we are almost there.

 

Add in 2 balls of a third colour (say, white) then there is one white-white pair. This makes up all of the 95 pairs we needed, but we have only used 19 balls, so we need a single ball of a fourth colour (say, green) to make it up to 20.

 

14 RED, 3 BLUE, 2 WHITE, 1 GREEN.

 

If you play about with other possibilities you will find that this arrangement, (14,3,2,1), is the only way of exactly achieving the aim of exactly 50% chance of a matching pair.

 

Solution of the Week #363 - Zero to Pi(ish)

The easiest thing is to do the whole procedure in reverse. Action a then become x-1 (action b is unchanged).

So starting with a rational number, to get to 0 in the fewest steps, whenever your number is greater than or equal to 1, perform action a and whenever your number is less than 1, perform action b.

In other words, each time the numerator is less than the denominator, flip the fraction upside down, and in doing so you will successively reduce the denominator until it is 1 and you can then keep subtracting until you get to zero.

 

From 355/113 to 0 will take a total of 28 actions:

 

355/113 = 3 16/113

a, 3 times

16/113

b

113/16 = 7 1/16

a, 7 times

1/16

b

16

a, 16 times

0

 

Reversing the process to go from 0 to 355/133 will clearly also take 28 actions: 16a,b,7a,b,3a.

Solution of the Week #362 - Missing Integers

2^a + 2^10 + 2^13 = b^2

Looking first just at 2^10 + 2^13, since 10 is less than 13 we can take out a factor of 2^10 to get:

2^10(1 + 2^3)

2^10 is obviously (2^5)^2 and (1 + 2^3) is 9, also a square number, therefore, you can replace 2^10 + 2^13 by (3*2^5)^2, or 96^2

2^a + 96^2 = b^2

Moving this to the right-hand side we have:

2^a = b^2 - 96^2

Factoring the difference of two squares gives:

2^a = (b+96)(b-96)

This means that both of the factors on the right-hand side are powers of 2, let’s call them 2^c = b+96 and 2^d = b-96.

If we take their difference to eliminate b we get:

2^c - 2^d = 192

Since d is smaller than c, we can take out a factor of 2^d:

2^d(2^(c-d)-1)=192

which is a product of a power of 2 and an odd number, which must therefore be 2^6 and 3.

d is therefore 6, and c is 8. a, as the sum of c and d, is therefore 14, and b is 2^6 + 96 = 160.

 

So the completed equation is

2^14 + 2^10 + 2^13 = 160^2