Consider the fraction, $n/d$, where $n$ and $d$ are positive integers. If $n<d$ and $HCF(n,d)=1$, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for $d\leq 8$ in ascending order of size, we get: \[\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\mathbf{\frac{2}{5}}, \frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8}\]

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper functions for $d\leq 1\,000\,000$?

Taking three different letters from the 26 letters of the alphabet, character strings of length three can be formed.

Examples are ‘abc’, ‘hat’ and ‘zyx’.

When we study these three examples we see that for ‘abc’ two characters come lexicographically after its neighbour to the left. For ‘hat’ there is exactly one character that comes lexicographically after its neighbour to the left. For ‘zyx’ there are zero characters that come lexicographically after its neighbour to the left.

In all there are 10400 strings of length 3 for which exactly one character comes lexicographically after its neighbour to the left.

We now consider strings of $n\leq 26$ different characters from the alphabet. For every $n$, $p(n)$ is the number of strings of length of $n$ for which exactly one character comes lexicographically after its neighbour to the left.

What is the maximum value of $p(n)$?

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.

Every Monday morning, the supervisor opens a new envelope, containing a large sheet of the special paper with size A1.

The supervisor proceeds to cut it in half, thus getting two sheets of size A2. Then one of the sheets is cut in half to get two sheets of size A3 and so on until an A5-size sheet is obtained, which is needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, the supervisor takes from the envelope one sheet of paper at random. If it is of size A5, then it is used. If it is larger, then the ‘cut-in-half’ procedure is repeated until an A5-size sheet is obtained, and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the supervisor finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places using the format x.xxxxxx .

Using a combination of grey square tiles and oblong tiles chosen from: red tiles (measuring two units), green tiles (measuring three tiles), and blue tiles (measuring four tiles), it is possible to tile a row measuring five units in length in exactly fifteen different ways.

How many ways can a row measuring fifty units in length be tiled?

This is related to #116 - Red, green or blue tiles

A row of five grey square tiles is to have a number of its replaced with coloured oblong tiles chosen from red (length two), green (length three), or blue (length four).

If red tiles are chosen there are exactly seven ways this can be done.

If green tiles are chosen there are three ways.

And if blue tiles are chosen there are two ways.

Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of replacing the grey tiles in a row measuring five units in length.

How many different ways can the grey tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used?

This is related to #117 - Red, green, and blue tiles

This is a much more difficult version of #114 - Counting block combinations I

A row measuring $n$ units in length has red blocks with a minimum length of $m$ units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.

Let the fill-count function, $F(m,n)$, represent the number of ways that a row can be filled.

For example, $F(3,29) = 673135$ and $F(3, 30) = 1089155$.

That is, for $m=3$, it can be seen that $n=30$ is the smallest value for which the fill-count function first exceeds one-million.

In the same way, for $m=10$, it can be verified that $F(10, 56) = 880711$ and $F(10, 57) = 1148904$, so $n=57$ is the least value for which the fill-count function first exceeds one million.

For $m=50$, find the least value of $n$ for which the fill-count function first exceeds one million.

A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one grey square. There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?

Although the example does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length you could use red (3), grey (1), and red (4).

Three distinct points are plotted at random on a Cartesian plane, for which $-1000\leq x,y\leq 1000$, such that a triangle is formed.

Consider the following two triangles: \[A(-340, 495), B(-153, -910), C(835, -947) \\ X(-175, 41), Y(-421, -714), Z(574, -645)\]

It can be verified that triangle $ABC$ contains the origin, whereas triangle $XYZ$ does not.

Using triangles.txt (right click and ‘Save Link/Target As…’), a 27K text file containing the coordinates of one thousand “random” triangles, find the number of triangles for which the interior contains the origin.

The first two examples in the file represent the triangles in the example given above.

Let $p_n$ be the $n^{\text{th}}$ prime: 2, 3, 5, 7, 11, …, and let $r$ be the remainder when $(p_n-1)^n + (p_n+1)^n$ is divided by $p_n^2$.

For example, when $n=3$, $p_3=5$, and $4^3 + 6^3 = 280 \equiv 5\mod 25$.

The least value of $n$ for which the remainder first exceeds $10^9$ is 7037.

Find the least value of $n$ for which the remainder first exceeds $10^{10}$.

A bag contains one red disc and one blue disc. In a game of chance a player takes a disc at random and its colour is noted. After each turn the disc is returned to the bag, an extra red disc is added, and another disc is taken at random.

The player pays £1 to play and wins if they have taken more blue discs than red discs at the end of the game.

If the game is played for four turns, the probability of a player winning is exactly 11/120, and so the maximum prize fund the banker should allocate for winning in this game would be £10 before they would expect to incur a loss. Note that any payout will be a whole number of pounds and also includes the original £1 paid to play the game, so in the example given the player actually wins £9.

Find the maximum prize fund that should be allocated to a single game in which fifteen turns are played.