Combinatorics

Project Euler 267: Billionaire

Project Euler 267: Billionaire

It has been a long while since I solved any Project Euler problem. For some reason I read an article about it and someone references Problem 267, so I decided to take a look at it, and it sucked me in. The problem reads

You are given a unique investment opportunity.

Starting with £1 of capital, you can choose a fixed proportion, f, of your capital to bet on a fair coin toss repeatedly for 1000 tosses.

Your return is double your bet for heads and you lose your bet for tails.

For example, if f = 1/4, for the first toss you bet £0.25, and if heads comes up you win £0.5 and so then have £1.5. You then bet £0.375 and if the second toss is tails, you have £1.125.

Choosing f to maximize your chances of having at least £1,000,000,000 after 1,000 flips, what is the chance that you become a billionaire?

All computations are assumed to be exact (no rounding), but give your answer rounded to 12 digits behind the decimal point in the form 0.abcdefghijkl.

 

Continue reading →

Posted by Kristian in Project Euler, 12 comments
Project Euler 121: Investigate the game of chance involving coloured discs

Project Euler 121: Investigate the game of chance involving coloured discs

To be honest, problem 121 of Project Euler scared me a whole lot, since my probability theory is not very strong. However, I do believe that I came up with quite a nice solution after all. The problem reads

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.

Continue reading →

Posted by Kristian in Project Euler, 6 comments
Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Problem 118 have a very short problem description which in all it’s glory reads

Using all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.

How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?

Continue reading →

Posted by Kristian in Project Euler, 4 comments
Project Euler 113: How many numbers below a googol (10^100) are not “bouncy”?

Project Euler 113: How many numbers below a googol (10^100) are not “bouncy”?

In Problem 112 of Project Euler we got an introduction to bouncy numbers. In Problem 113 we will revisit this concept and solve the problem

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below 1010.

How many numbers below a googol (10100) are not bouncy?

Continue reading →

Posted by Kristian in Project Euler, 4 comments
Project Euler 106: Find the minimum number of comparisons needed to identify special sum sets.

Project Euler 106: Find the minimum number of comparisons needed to identify special sum sets.

Unlike Problem 105 which I wasn’t too impressed with Problem 106 of Project Euler has really lead me to gain some insights into the special sum sets. The problem reads

Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

  1. S(B) ≠ S(C); that is, sums of subsets cannot be equal.
  2. If B contains more elements than C then S(B) > S(C).

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.

For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?

Continue reading →

Posted by Kristian in Project Euler, 9 comments
Project Euler 105: Find the sum of the special sum sets in the file.

Project Euler 105: Find the sum of the special sum sets in the file.

Problem 105 of Project Euler is closely related to Problem 103 as has been mentioned in both problem descriptions. The problem formulation for this problem is

Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

  1. S(B) ≠ S(C); that is, sums of subsets cannot be equal.
  2. If B contains more elements than C then S(B) > S(C).

For example, {81, 88, 75, 42, 87, 84, 86, 65} is not a special sum set because 65 + 87 + 88 = 75 + 81 + 84, whereas {157, 150, 164, 119, 79, 159, 161, 139, 158} satisfies both rules for all possible subset pair combinations and S(A) = 1286.

Using sets.txt, a text file with one-hundred sets containing seven to twelve elements (the two examples given above are the first two sets in the file), identify all the special sum sets, A1, A2, …, Ak, and find the value of S(A1) + S(A2) + … + S(Ak).

Continue reading →

Posted by Kristian in Project Euler, 2 comments
Project Euler 103: Investigating sets with a special subset sum property.

Project Euler 103: Investigating sets with a special subset sum property.

Problem 103 of Project Euler is a hard problem if we look at the amount of people who solved it.  And I tend to agree, it took me a while to solve it. The problem reads

Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

  1. S(B) ≠ S(C); that is, sums of subsets cannot be equal.
  2. If B contains more elements than C then S(B) > S(C).

If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

It seems that for a given optimum set, A = {a1a2, … , an}, the next optimum set is of the form B = {ba1+ba2+b, … ,an+b}, where is the “middle” element on the previous row.

By applying this “rule” we would expect the optimum set for n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 and corresponding set string: 111819202225.

Given that A is an optimum special sum set for n = 7, find its set string.

Continue reading →

Posted by Kristian in Project Euler, 5 comments
Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

I really start feeling that the problems become more and more difficult. Problem 93 of Project Euler was not trivial at all. And as we shall see the only solution I found was a brute force solution.  The problem reads

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) – 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

Continue reading →

Posted by Kristian in Project Euler, 31 comments
Project Euler 92: Investigating a square digits number chain with a surprising property.

Project Euler 92: Investigating a square digits number chain with a surprising property.

Problem 92 of Project Euler is one of the more solve puzzles in this range, so based on that parameter this should be a pretty easy thing to chew through. The problem text reads

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

I have found two methods to solve this. One where we  go through all 10.000.000 numbers to check what their cycle will be with a bit of help from some caching. And then a method where we exploit the fact that the order of the digits doesn’t matter and that significantly reduces the cases we need to check. Continue reading →

Posted by Kristian in Project Euler, 12 comments
Project Euler 90: An unexpected way of using two cubes to make a square.

Project Euler 90: An unexpected way of using two cubes to make a square.

In the ninetieth problem of Project Euler  we are back in combinatorics with a problem description that reads

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:

In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?

Continue reading →

Posted by Kristian in Project Euler, 9 comments