Puzzle of the Week #163 - Flipping Coins Again!

Sorry to still be banging on about this triple coin flip game (see POTW #160 and #161), but the maths behind it is particularly interesting. Today’s puzzle has a very long preamble, but I feel it’s worth the journey and the puzzle itself is quite good fun!

For a given array there will be a particular number of coins, and a particular number of possible moves. For instance, a 4 by 4 grid will have 16 coins and 24 moves.

potw coins 3_1.JPG

There are four directions of moves: Horizontal, Vertical, Downhill and Uphill. For the purposes of notation I will place a letter H, V, D or U at the point in the grid corresponding to the centre of the three coins being flipped. So the grid to the right shows all 24 possible moves.

The solution to POTW #161 is particularly interesting, as the number of coins and the number of moves are the same. This means that for any given starting arrangement, there is exactly one set of moves that will solve it. (We can safely say that performing the same move twice is the same as not performing it at all, so we don’t need to worry about repeating a move; a move is either performed or not).

For any arrangement larger than the solution to POTW #161, there will be some sets of moves, which I will call ‘null sets’, that cancel each other out (the simplest of these to understand would be three horizontal moves and three vertical moves within a 3 by 3 area of the array – each of the 9 coins will be flipped twice and end the same as it began). You can even work out how many ‘null sets’ that will exist:

For example, a 3 by 4 grid has 12 coins, and 14 moves. This means there are 2^12 (4096) possible arrangements and 2^14 (16384) possible sets of moves. This means there are 4 times as many ‘move sets’ as there are arrangements. It follows from that that there are 4 ‘null sets’ (although one of those null sets is the empty set – no moves at all).

I’ll now introduce the concept of an ‘independent null set’. That is a null set that cannot be formed by combining other null sets you’ve already found (so technically any null set might be an independent null set if it happens to be one of the first you find). For the 3 by 4 grid there will be 2 independent null sets (let’s call them a and b), and the total of 4 null sets can be formed by a binary combination of these (that is, ‘a and b’, ‘a only’, ‘b only’, and ‘the empty set’). Below is a possible ‘a’ and ‘b’ for the 3 by 4 grid:

potw coins 3_2.JPG

This actually simplifies things a little, as the number of independent null sets will simply be the difference between the number of moves and the number of coins. So back to the 4 by 4 grid which will be the basis of this week’s puzzle. As mentioned before, there are 16 coins and 24 moves, so there will be 8 independent null sets. I have found six of them for you. It may initially look as if reflections of e and f will also be independent, but in fact they can be formed by combining each of them with all four of a, b, c and d.

potw coins 3_3.JPG

The final two independent null sets are reflections or rotations of each other. Can you find them?

So to recap in case you are a little lost, find a set of moves within the 4 by 4 grid (with no individual move repeated) that cancels itself out, and that cannot be formed by combining any of the other six such sets of moves above.

Addendum: to explain how to 'combine' existing sets of moves: you superimpose all of the moves in the move sets you want to combine. Any moves that occur an even number of times cancel out, any that occur an odd number will be in the combined move set.

Puzzle of the Week #162 - Hypotenuse Connect Four

Some numbers can be the hypotenuse of an integer triangle, and some cannot. For instance, 24 cannot, neither can 27, but 25 and 26 both can (for example 7,24,25 and 10,24,26). In fact 25 and 26 is the first case where two consecutive numbers can each be hypotenuses. The first case of three numbers in a row which can be hypotenuses is 39, 40 and 41 (eg 15,36,39; 24,32,40; 9,40,41).

Which numbers are the first example of four in a row that could each be hypotenuse?

Puzzle of the Week #161 - Coin Flipping part 2

COIN FLIP 2.JPG

Following on from last week’s coin flipping puzzle, where a horizontal or vertical line of three coins could be flipped together, with the object being to end with all the coins heads up. I’ll introduce a new move now – a diagonal (45 degree) line of three coins can also be flipped together. It turns out that with this new rule, as long as the arrangement of coins is big enough, any initial arrangement can be solved. But the question is: how big is big enough?

Find the arrangement with the fewest coins, such that any starting arrangement of heads or tails can be made all heads by a series of three-in-a-row flips in horizontal, vertical or diagonal directions.

(The coins must lie in a rectangular grid pattern. If there are spaces in the grid without coins, then a triplet of coins you wish to flip cannot bridge across the gaps).

Facebook Page

In case you weren't aware: this puzzle blog has a Facebook page:

https://www.facebook.com/elliottlinepuzzles/

Each Friday morning I post the link to the Puzzle of the Week to the Facebook page, and invite people to send me their answers as a message (to avoid spoilers).

Everyone is welcome to follow my page!

 

Puzzle of the Week #160 - Coin Flipping

In this game, the object is to make it so that all the coins are facing heads up, but on each move you must flip three coins together in a line, horizontally or vertically. For instance you could flip the first three coins on the top row, or the last three coins in the second column, or the middle three coins in the fourth row.

As it stands, the game cannot be solved, however if you flip one individual coin from the middle nine before you start, then the game can be solved.

Which of those middle nine coins should you opt to flip?

COIN FLIP.JPG

Puzzle of the Week #159 - Make Primes Finite Again

A President discovered on a TV show that you can generate an infinity of numbers even if you only had a finite number of prime numbers, and so decided that prime numbers beyond a certain size could be dispensed with.

He decreed that only the first ten prime numbers (those up to and including 29) could remain, and any numbers that contained prime factors higher than those would simply be skipped over when counting. So if you had 30 of something, and someone gave you one more, you would now be said to have 32 under this new system.

I recently did some freelance work in that country but when it came time to be paid in gold coins I was dismayed to discover that I only received half the gold coins I had been expecting! The amount I had invoiced them for was a number they didn't recognise, and so I was paid a gold coin for each of the numbers up to that number that they did recognise.

How many gold coins did I actually receive?

Puzzle of the Week #158 - Strip Teaser

I have a thin strip of paper 1 inch wide. I lay it out horizontally in front of me. Along the top edge I mark two points, at five inches and ten inches from the top left corner.

I fold the top left corner down and slightly to the right, such that the fold line passes through the bottom left corner of the strip and the ten inch mark on the top edge.

I then draw a straight line from the bottom left corner of the strip, passing through the new position of the five inch mark, and continuing on its shallow diagonal trajectory until it hits the top edge of the strip.

How far along is the point where the line meets the top edge?

strip teaser.JPG

Puzzle of the Week #154 - Penpals

If someone in Port-au-Prince writes to someone in Zagreb, someone in Bratislava writes to someone in Bishkek, someone in Rabat writes to someone in Yerevan, and someone in Baku writes to someone in Cape Town, where does someone in Sofia send their letters?

Puzzle of the Week #153 - Multiply and Subtract

Here is an interesting mathematical game to play. The idea is to reach a total by multiplying and/or subtracting positive integers, whilst minimising the sum of those integers. Rather than explain I’ll demonstrate:

For example if the target is 99 you could have:

11 x 3 x 3 = 99, giving a score of 17

Alternatively you could save a couple of points thus:

5 x 5 x 4 – 1 = 99, giving 15 points

But even this can be improved upon:

3 x 4 – 1 x 3 x 3 = 99, scoring 14 points.

Note that each calculation, whether multiplying or subtracting, is performed stepwise, rather than using the BODMAS order of operations.

 

So, the target I have chosen for the puzzle is 12345. What is the lowest score you can achieve?

I should point out that I am not confident that the answer that I have is the best achievable (twice before I thought I had the best answer and then found a better one). If your score is higher I’ll be able to tell you that a lower score is achievable, but I am fully prepared to discover that my score is not the best either!

Additionally, if anyone can find an algorithm that finds the best solution in the general case I’d love to hear of it. At present all I have been able to establish is a loose set of rules of thumb.

Puzzle of the Week #152 - Resistance is Futile

To combine resistors in series, you add their resistances together. For example 10 ohms and 20 ohms combined in series gives 30 ohms.

To combine resistors in parallel, you take the reciprocal of the sum of reciprocals of the individual resistors. For example 12 ohms and 24 ohms combined in parallel gives you 8 ohms (1/12 + 1/24 = 1/8).

You have 5 resistors, each with a rating of 120 ohms. Combining them in different ways it is possible to achieve a variety of resistances, for example, the arrangement below results in a 100 ohm resistance (60+40).

5 resistors 100.JPG

One of the following values is NOT possible using the 5 x 120 ohm resistors, which is it?

45 ohms

96 ohms

105 ohms

140 ohms

144 ohms

Puzzle of the Week #151 - Race Numbers

In a recent half marathon with a few thousand runners, the race numbers began at 1 and counted upwards in the usual way.

I happened to notice that the average sum-of-digits of the four digit race numbers was precisely the same as the average sum-of-digits of the three digit race numbers. I also happened to notice that the very highest number was an exact multiple of 17.

How many runners were there?

Puzzle of the Week #150 - Map Matching

I have two identical maps, except that one is printed as A3 and one is A4. I rotate the A4 map 45 degrees anti-clockwise and position it over the A3 such that the top left corner of the A4 map lies on the left edge of the A3 map, and the bottom left corner of the A4 map lies on the bottom edge of the A3 map.

map match.JPG

There will be exactly one point such that if I put a pin through the two maps, they will pinpoint the same place on the map. Where should I put the pin?

Puzzle of the Week #149 - Nazca Polygon

There is a regular 2018-sided polygon engraved in the Nazca Desert in Peru. The corners are alternately coloured red and green. Any pair of opposite corners are exactly 2 miles apart.

You stand on one of the green corners, and measure your straight-line distance to each of the 1009 red corners (in miles). You multiply together all of these distances.

What do you get?

 

(Maths hint: try smaller numbers of sides first to see if you can detect any pattern.)

Puzzle of the Week #148 - Zipline Futoshiki

I’ve combined one of my early puzzle creations, Zipline (see https://www.janko.at/Raetsel/Zipline/index.htm for examples you can play online), with an established Japanese puzzle type, Futoshiki, to create this new type of puzzle.

The numbers 1 to 16 need to be placed in the squares according to the following rules:

The symbols denote that the number in one square is greater (>) or less (<) than the number in an adjacent square.

1 and 2 appear in the same row or column (although not necessarily adjacently), 2 and 3 appear in the same diagonal, 3 and 4 appear in the same row/column, 4 and 5 in the same diagonal, etc. (So, consecutive numbers where the lower number is odd will appear in the same row or column, and consecutive numbers where the lower number is even will appear in the same diagonal).

zipline futoshiki.JPG

Puzzle of the Week #146 - Tetrahedral Ants

Four ants are positioned at the four corners of a tetrahedron (triangular-based pyramid). At once they all move along one of the edges to another corner, each choosing at random from the three other corners available.

What is the probability that the ants will perform this manoeuvre without any of them having to pass another coming the other way along the same edge or ending up at the same corner as another ant?

Solution to Puzzle of the Week #145

The probability of the centre of the circle being within the pentagon is 11/16.

The general formula for an n-sided shape is: 1 - n/(2^(n-1)) 

 

If you're interested, the derivation of the above formula is as follows:

The puzzle asked, for five points positioned at random, what is the probability of the pentagon formed by them containing the centre of the circle.

Let’s switch is round and ask what the probability is of missing the centre. For this to be the case, all of the points must be in the same half of the circle, but that half could be 0 to 180 degrees, or 180 to 360, or 63 to 243, or any of the countless other ways. So let us pick a point, one of the five random points, and (temporarily) call that our zero, our datum. What is the chance of the other 4 points being less than 180 degrees clockwise from the datum? Simply ½ x ½ x ½ x ½, or 1/16.

Each of the five points can be taken as the datum in turn. So is it just a matter of adding together those five probabilities (or, as they are equal, simply multiplying 1/16 by 5)? Well yes, since at most one datum can result in all the other points being less than 180 clockwise from that point, the five cases are mutually exclusive, and it is indeed just a matter of adding them together.

From here it is easy to see what the general equation is. For n points, the probability of not containing the centre is:

n/(2^(n-1))

Giving the sequence ¾, 4/8, 5/16, 6/32, 7/64, 8/128 etc (before simplification, to demonstrate that the numerator increases by one and the denominator doubles with each new term)

Then the probability of containing the centre is merely the complement of this, or 1 – n/(2^(n-1))

Resulting in the sequence ¼, ½, 11/16, 13/16, 57/64, 15/16 etc.