Fireworks – Project Euler 317

March 19, 2017 Leave a comment

You can read the text of the problem here. The idea is that we have an explosion at a given height in a uniform gravitational field (no friction/wind). Supposing that all particles go outwards from the explosion point with a constant initial speed, what is the shape of the body formed by these particles? A hint is given in the picture below with a nice Matlab simulation.

euler317

Now what happens if we add a little bit of wind? Here’s the perturbation obtained when adding a 10m/s uniform wind speed vs the initial configuration. Something like this would be a lot more challenging 🙂

pb317_wind

SEEMOUS 2017 Problems

March 5, 2017 1 comment

Problem 1. Let {A \in \mathcal M_2(\Bbb{R})}. Suppose

\displaystyle A =\begin{pmatrix} a& b\\ c & d \end{pmatrix}

satisfies

\displaystyle a^2+b^2+c^2+d^2<1/5.

Show that {I+A} is invertible.

Problem 2. Let {A,B \in \mathcal M_n(\Bbb{R})}.

  • a) Prove that there exists {a>0} such that for every {\varepsilon \in (-a,a),\varepsilon\neq 0} the matrix equation

    \displaystyle AX+\varepsilon X = B,\ X \in \mathcal M_n(\Bbb{R})

    has a unique solution {X(\varepsilon) \in \mathcal M_n(\Bbb{R})}.

  • b) Prove that if {B^2 = I_n} and {A} is diagonalizable then

    \displaystyle \lim_{\varepsilon \rightarrow 0} \text{tr}(BX(\varepsilon)) = n-\text{rank}(A).

Problem 3. Let {f: \Bbb{R} \rightarrow \Bbb{R}} be a continuous function. Prove that

\displaystyle \int_0^4 f(x(x-3)^2)dx = 2 \int_1^3 f(x(x-3)^2)dx

Problem 4. a) Let {n \geq 0} be an integer. Compute {\displaystyle \int_0^1 (1-t)^n e^t dt}.

b) Let {k \geq 0} be a fixed integer and let {(x_n)_{n \geq k}} be the sequence defined by

\displaystyle x_n = \sum_{i=k}^n {i \choose k}\left(e-1-\frac{1}{1!}-\frac{1}{2!}-...-\frac{1}{i!}\right).

Prove that the sequence converges and find its limit.

Source: link

Read more…

Categories: Uncategorized

Project Euler Problem 144 – Laser light escaping an ellipse

February 5, 2017 Leave a comment

ellipse

Project Euler – problem 144 – visualization of the solution in Matlab

Panaitopol primes – simple representation

February 4, 2017 1 comment

A prime number {p} is called a Panaitopol prime if {\displaystyle p = \frac{x^4-y^4}{x^3+y^3}}. I stumbled upon these weird prime numbers while working on problem 291 from Project Euler.

While searching a bit about the problem I did a brute force check to find the first such primes and I found the following values:

\displaystyle 5, 13, 41, 61, 113, 181, 313, 421, 613, 761.

Read more…

Categories: Uncategorized

Linear programming #1 – Project Euler 185

January 28, 2017 Leave a comment

I was recently faced with a very nice challenge from Project Euler – Problem 185. The idea is to find a number with a fixed number of digits by making guesses. Each time you are told how many digits you got right. By got right, I mean guessing the right digit on the right position. If you find a digit which is in the number, but on a different position, you don’t know…

There is a test case with 5 digits:

90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct

with unique solution 39542 and the difficult case with 16 digits

5616185650518293 ;2 correct
3847439647293047 ;1 correct
5855462940810587 ;3 correct
9742855507068353 ;3 correct
4296849643607543 ;3 correct
3174248439465858 ;1 correct
4513559094146117 ;2 correct
7890971548908067 ;3 correct
8157356344118483 ;1 correct
2615250744386899 ;2 correct
8690095851526254 ;3 correct
6375711915077050 ;1 correct
6913859173121360 ;1 correct
6442889055042768 ;2 correct
2321386104303845 ;0 correct
2326509471271448 ;2 correct
5251583379644322 ;2 correct
1748270476758276 ;3 correct
4895722652190306 ;1 correct
3041631117224635 ;3 correct
1841236454324589 ;3 correct
2659862637316867 ;2 correct

While the small case could be tackled using a pure brute force approach (only 10^5) cases to check, the second case becomes intractable. Looping through all 10^16 cases would take ages. One could try genetic algorithms or other algorithms based on randomness. Recursive approaches are also possible.

There is however a way to express this problem which makes it solvable right away using a linear programming solver: that is an algorithm which finds valid solutions given some constraints. How do we find these constraints? There are essentially two types of constraints in our case:

  • each of the positions of the result contains one digit from 0 to 9
  • in each of the guesses given above we have a fixed number of correct digits

Read more…

About Problem 587 – Project Euler

January 27, 2017 Leave a comment

I started looking again at some problems on the Project Euler site. It’s not often that I manage to solve a recent problem. Below are a few hints about the math needed to provide an answer to problem 587.

I’ll not repeat the statement of the problem here, so please read it by following the above link. The idea is to find the ratio of the areas of some triangular shapes made of two segments and one circle arc. The breakdown of the problem is the following:

  • Note that the size of the square does not matter, since we need the result as a ratio, so we can consider that the square has side equal to 1. First note that the L-shape in the corner of the triangle has area equal to 1/8-\pi/32. We’ll need this in the end, to compute the ratio.
  • Secondly, the shape whose area we need to compute can be decomposed into a right-angled triangle and a complement of a part of the circle. In order to have precise information about these shapes we compute the intersection of the line y=x/n and the circle (x-0.5)^2+(y-0.5)^2=0.25. It is possible to find the value explicitly.
  • Once we have the coordinates of the point of intersection we can compute the area of the triangle. The area of the rounded part which remains is the difference between a rectangle and the circle portion PQON. In order to do find this difference it suffices to find the angle PSQ.
  • Once the mathematical part is done, the programming job is not that tough, since the numbers involved are not that high. I managed to write a Matlab solution in no time.fig587

Putnam 2016 – A4

December 13, 2016 Leave a comment

Problem A4. Consider a {(2m-1)\times(2n-1)} rectangular region, where {m} and {n} are integers such that {m,n\geq 4}. The region is to be tiled using tiles of the two types shown below  putnam2016_3

(The dotted lines divide the tiles into {1\times 1} squares.) The tiles may be rotated and reflected, as long as their sides are parallel to the sides of the rectangular region. They must all fit within the region, and they must cover it completely without overlapping.

What is the minimum number of tiles required to tile the region?

Read more…

Categories: Uncategorized
%d bloggers like this: