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.
Let $p(n)$ represent the number of different ways in which $n$ coins can be separated into piles. for example, five coins can be separated into piles in exactly seven different ways, so $p(5)=7$. \[\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc \\ \bigcirc\bigcirc\bigcirc\bigcirc\quad\bigcirc \\ \bigcirc\bigcirc\bigcirc\quad\bigcirc\bigcirc \\ \bigcirc\bigcirc\bigcirc\quad\bigcirc\quad\bigcirc \\ \bigcirc\bigcirc\quad\bigcirc\bigcirc\quad\bigcirc \\ \bigcirc\bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc \\ \bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc\]
Find the least value of $n$ for which $p(n)$ is divisible by one million.
It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.
We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.
Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).
If we are presented with the first $k$ terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.
As an example, let us consider the sequence of cube numbers. This is defined by the generating function, $u_n=n^3: 1,8,27,64,125,216,\dots$.
Suppose we were only given the first two terms of this sequence. Working on the principle that “simple is best” we should assume a linear relationship and predict the next term to be 15 (common difference 7). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.
By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:
Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
In the game, Monopoly, the standard board is set up in the following way:
Monopoly board
A player starts on the GO square and adds the scores on two 6-sided dice to determine the number of squares they advance in a clockwise direction. Without any further rules we would expect to visit each square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.
In addition to G2J, and one card from each of CC and CH , that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.
At the beginning of the game, the CC and CH cards are randomly shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH square.
- Community Chest (2/16 cards):
- Chance (10/16 cards):
- Advance to GO
- Go to JAIL
- Go to C1
- Go to E3
- Go to H2
- Go to R1
- Go to next R (railway company)
- Go to next R
- Go to next U (utility company)
- Go back 3 squares
The heart of this problem concerns the likelihood of visiting a particular square. That is, the probability of finishing at that square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing is zero, the CH squares will have the lowest probabilities, as 5/8 request a movement to another square, and it is the final square that the player finishes on that we are interested in. We shall make no distinction between “Just Visiting” and being to sent to JAIL, and we shall also ignore the rule about requiring a double to “get out of jail”, assuming they pay to get out on their next turn.
By starting on GO and numbering the squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of squares.
Statistically it can be shown that the three most popular squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular squares can be listed with the six-digit modal string: 102400.
If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427. \[\begin{pmatrix} \color{red}{\mathbf{131}} & 673 & 234 & 103 & 18 \\ \color{red}{\mathbf{201}} & \color{red}{\mathbf{96}} & \color{red}{\mathbf{342}} & 965 & 150 \\ 630 & 803 & \color{red}{\mathbf{746}} & \color{red}{\mathbf{422}} & 111 \\ 537 & 699 & 497 & \color{red}{\mathbf{121}} & 956 \\ 805 & 732 & 524 & \color{red}{\mathbf{37}} & \color{red}{\mathbf{331}} \end{pmatrix}\]
Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing an 80 by 80 matrix.
