# Combinatorics

## HackerRank: Connecting Towns

Welcome to the Shire… Well at least welcome to Middle Earth, we don’t actually need to travel through the shire in the next HackerRank problem with Connecting Towns. The problem reads

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4…Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note
Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn.
For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.

Input Format
The first line contains an integer T, T test-cases follow.
Each test-case has 2 lines. The first line contains an integer N (the number of towns).
The second line contains N – 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

Output Format
Total number of routes from T1 to Tn modulo 1234567
http://en.wikipedia.org/wiki/Modular_arithmetic

## Solving the math of Connecting Towns

There are two things we need to get our heads around. There is the first part which is how many paths there are, and then there is the second part of the modulo.

The former problem of the paths is rather simple as it is a simple combinatorics problem and the total number of paths are just the product of the paths of each leg of the journey

The problem of the modulo operator can be treated in different ways. Since we are using Python as implementation language we can completely ignore it, as it can handle arbitrarily large integers. However, we can also solve it as we have done for Project Euler problem 48.

In general we have the formula

Which means that for every time we multiply with the next set of paths we can also take the modulo, which means we will keep the total size of the integer down significantly.  If it actually matters in Python I don’t know.

## Implementing Connecting towns in Python

Let us implement the one with modulo arithmetic. However since we know that both a and b in the previous formula will be smaller than the modulo. Therefore a%c = a and b%c= b, so we only need to take modulo of the result during the iterations. Therefore the function we need to implement is

```def connectingTowns(n, routes):
paths = 1
for i in routes:
paths = (paths * i) % 1234567
return paths
```

and that should solve the problem.

Posted by Kristian in HackerRank, 0 comments

## HackerRank: Maximum Draws

Second round of the fundamental mathematics problems on HackerRank is called Maximum draws.  It asks the following

Jim is off to a party and is searching for a matching pair of socks. His drawer is filled with socks, each pair of a different color. In its worst case scenario, how many socks (x) should Jim remove from his drawer until he finds a matching pair?

Input Format
The first line contains the number of test cases T.
Next T lines contains an integer N which indicates the total pairs of socks present in the drawer.

Output Format
Print the number of Draws (x) Jim makes in the worst case scenario.

Posted by Kristian in HackerRank, 0 comments

## 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.

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.

Posted by Kristian in Project Euler, 12 comments

## 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.

Posted by Kristian in Project Euler, 7 comments

## 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?

Posted by Kristian in Project Euler, 5 comments

## 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?

Posted by Kristian in Project Euler, 5 comments

## 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?

Posted by Kristian in Project Euler, 9 comments

## 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).

Posted by Kristian in Project Euler, 2 comments

## 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.

Posted by Kristian in Project Euler, 6 comments

## 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.

Posted by Kristian in Project Euler, 33 comments