Probability

A hint for Project Euler Pb 613

November 18, 2017 beni22sof Leave a comment

The text for Problem 613 can be found here. The hint is the following picture 🙂

PE613

Categories: Probability, Programming, Uncategorized Tags: Geometry, Probability, project euler

Project Euler Problem 285

March 25, 2017 beni22sof Leave a comment

Another quite nice problem from Project Euler is number 285. The result of the problem depends on the computation of a certain probability, which in turn is related to the computation of a certain area. Below is an illustration of the computation for k equal to 10.

pb285_10

To save you some time, here’s a picture of the case k=1 which I ignored and spent quite a lot of time debugging… Plus, it only affects the last three digits or so after the decimal point…

pb285_1

Here’s a Matlab code which can construct the pictures above and can compute the result for low cases. To solve the problem, you should compute explicitly all these areas.


function problem285(k)

N = 100000;

a = rand(1,N);
b = rand(1,N);

ind = find(abs(sqrt((k*a+1).^2+(k*b+1).^2)-k)<0.5);

plot(a(ind),b(ind),'.');
axis equal

M = k;
pl = 1;

for k=1:M
if mod(k,100)==0
k
end
r1 = (k+0.5)/k;
r2 = (k-0.5)/k;

f1 = @(x) (x<=(-1/k+r1)).*(x>=(-1/k-r1)).*(sqrt(r1^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f1 = @(x) f1(x).*(f1(x)>=0);
f2 = @(x) (x<=(-1/k+r2)).*(x>=(-1/k-r2)).*(sqrt(r2^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f2 = @(x) f2(x).*(f2(x)>=0);

if k == pl
thetas = linspace(0,pi/2,200);
hold on
plot(-1/k+r1*cos(thetas),-1/k+r1*sin(thetas),'r','LineWidth',2);
plot(-1/k+r2*cos(thetas),-1/k+r2*sin(thetas),'r','LineWidth',2);
plot([0 1 1 0 0],[0 0 1 1 0],'k','LineWidth',3);
hold off
axis off
end

A(k) = integral(@(x) f1(x)-f2(x),0,1);

end

xs = xlim;
ys = ylim;

w = 0.01;
axis([xs(1)-w xs(2)+w ys(1)-w ys(2)+w]);

sum((1:k).*A)

Categories: Analysis, Geometry, matlab, Numerical Analysis, Probability, Uncategorized Tags: numerical computations, Probability, project euler, trick

Problems of the Miklos Schweitzer Competition 2014

November 10, 2014 beni22sof 5 comments

Problem 1. Let ${n}$ be a positive integer. Let ${\mathcal{F}}$ be a familiy of sets that contains more than half of all subsets of an ${n}$ -element set ${X}$ . Prove that from ${\mathcal{F}}$ we can select ${\lceil \log_2 n\rceil+1 }$ sets that form a separating family of ${X}$ , i.e., for any two distinct elements of ${X}$ there is a selected set containing exactly one of the two elements.

Problem 2. let ${k \geq 1}$ and let ${I_1,...,I_k}$ be non-degenerate subintervals of the interval ${[0,1]}$ . Prove that

$\displaystyle \sum \frac{1}{|I_i \cup I_j|} \geq k^2,$

where the summation is over all pairs of indices ${(i,j)}$ such that ${I_i}$ and ${I_j}$ are not disjoint.

Problem 3. We have ${4n+5}$ points in the plane, no three of them collinear. The points are colored with two colors. Prove that from the points we can form ${n}$ empty triangles (they have no colored points in their interiors) with pairwise disjoint interiors, such that all points occuring as vertices of the ${n}$ triangles have the same color.

Problem 4. For a positive integer ${n}$ , let ${f(n)}$ be the number of sequences ${a_1,...,a_k}$ of positive integers such that ${a_i \geq 2}$ and ${a_1...a_k = n}$ for ${k \geq 1}$ . We make the convention ${f(1)=1}$ . Let ${\alpha}$ be the unique real number greater than ${1}$ such that ${\sum_{n=1}^\infty n^{-\alpha}=2}$ . Prove that

(i) ${ \sum_{ k = 1}^n f(k)= O(n^\alpha)}$ .
(ii) There exists no number ${\beta<\alpha}$ such that ${f(n)=O(n^\beta)}$ .

Problem 5. Let ${\alpha}$ be a non-real algebraic integer of degree two, and let ${P}$ be the set of irreducible elements of the ring ${\Bbb{Z}[\alpha]}$ . Prove that

$\displaystyle \sum_{ p \in P} \frac{1}{|p|^2} = \infty.$

Problem 6. Let ${\rho : G \rightarrow GL(V)}$ be a representation of a finite ${p}$ -group ${G}$ over a field of characteristic ${p}$ . Prove that if the restriction of the linear map ${\sum_{ g \in G} \rho(g)}$ to a finite dimensional subspace ${W}$ of ${V}$ is injective, then the subspace spanned by the subspaces ${\rho(g)W}$ ( ${g \in G}$ ) is the direct sum of these subspaces.

Problem 7. Lef ${f: \Bbb{R} \rightarrow \Bbb{R}}$ be a continuous function and let ${g: \Bbb{R} \rightarrow \Bbb{R}}$ be arbitrary. Suppose that the Minkowski sum of the graph of ${f}$ and the graph of ${g}$ (i.e. the set ${\{(x+y,f(x)+g(y) : x,y \in \Bbb{R}\}}$ has Lebesgue measure zero. Does it follow then that the function ${f}$ is of the form ${f(x)=ax+b}$ , with suitable constants ${a,b \in \Bbb{R}}$ ?

Problem 8. Let ${n \geq 1}$ be a fixed integer. Calculate the distance

$\displaystyle \inf_{p,f} \max_{0 \leq x \leq 1} |f(x)-p(x)|,$

where ${p}$ runs over polynomials of degree less than ${n}$ with real coefficients and ${f}$ runs over functions of the form

$\displaystyle f(x) = \sum_{ k = n}^\infty c_kx^k$

defined on the closed interval ${[0,1]}$ , where ${c_k\geq 0}$ and ${\sum_{k=n}^\infty c_k =1}$ .

Problem 9. Let ${\rho : \Bbb{R}^n \rightarrow \Bbb{R},\ \rho(x)=e^{-\|x\|^2}}$ , and let ${K \subset \Bbb{R}^n}$ be a convex body, i.e. a compact convex set with nonempty interior. Define the barycenter ${s_K}$ of the body ${K}$ with respect to the weight function ${\rho}$ by the usual formula

$\displaystyle s_K = \frac{\int_K \rho(x) x dx}{\int_K \rho(x)dx}.$

Prove that the translates of the body ${K}$ have pairwise distinct barycenters with respect to ${\rho}$ .

Problem 10. To each vertex of a given triangulation of the two dimensional sphere, we assign a convex subset of the plane. Assume that the three convex sets corresponding to the three vertices of any two dimensional face of the triangulation have at least one point in common. Show that there exist four vertices such that the corresponding convex sets have at least one point in common.

Problem 11. Let ${U}$ be a random variable that is uniformly distributed on the interval ${[0,1]}$ , and let

$\displaystyle S_n = 2\sum_{k=1}^n \sin(2kU\pi).$

Show that, as ${n \rightarrow \infty}$ , the limit distribution of ${S_n}$ is the Cauchy distribution with density function ${f(x) =\frac{1}{\pi(1+x^2)}}$ .

Source: http://www.bolyai.hu/SCH_angol_2014.pdf

Categories: Algebra, Analysis, Olympiad, Probability, Problem Solving Tags: Algebra, Analysis, Combinatorics, Geometry, miklos schweitzer, Probability

Two examples of Probability applications

March 25, 2014 beni22sof Leave a comment

Problem 1. The probability that an animal reacts positively to an injection is ${0.75}$ . Eight random animals have been injected. Calculate the probability of the following events:

a) No animal has a positive reaction;

b) Exactly two animals have a positive reaction;

c) At most two animals have a positive reaction;

d) At least two animals have a positive reaction.

Categories: Combinatorics, Probability Tags: binomial, Poisson, Probability

How can everybody (probably) get the right change?

October 28, 2013 beni22sof Leave a comment

We are all annoyed when we buy something and the seller doesn’t have the right change. You have a few possibilities: leave the change (not a real option…), go change your money yourself, or wait for another buyer. Below a simplistic situation is presented, where ${100}$ people wait in line to buy cinema tickets. The price is ${5}$ euros, and the customers all have bills of ${5}$ and ${10}$ euros (to be more precise ${40}$ people have ${10}$ euros bills and ${60}$ people have ${5}$ euros bills). Note that there are more people with ${5}$ euros bills than those with ${10}$ euros bills, so in the end everybody could receive change, even if the cashier has no ${5}$ euro bills in the beginning. Still, the problem is that each client would like to pay for his ticket and receive the change on the spot, without waiting. In order to do that the cashier would need to have some number of ${5}$ euro bills in the beginning.

The worst case is when all ${40}$ clients with ${10}$ euros bills are first in line, case in which the cashier would need ${40}$ bills of ${5}$ euros for everyone to be happy. We can ask for a more weak condition, namely that the probability that everyone is satisfied is big, let’s say ${95\%}$ . How many ${5}$ euros bills would the cashier need to fulfill this goal? How many bills does he need to reach a probability of ${99\%}$ ?

Categories: Probability Tags: Probability

IMC 2011 Day 1 Problem 4

July 27, 2011 beni22sof 4 comments

Let $A_1,A_2,...,A_n$ be finite, nonempty sets. Define the function

$\displaystyle f(t)=\sum_{k=1}^n \sum_{1\leq i_1 < i_2 <...< i_k\leq n} (-1)^{k-1} t^{|A_{i_1}\cup A_{i_2}\cup ... \cup A_{i_k}|}$

Prove that $f$ is nondecreasing on $[0,1]$ .

Categories: Olympiad, Probability Tags: IMC, Probability

Arithmetic progressions which cover the positive integers

April 1, 2011 beni22sof 1 comment

Suppose we have a family (finite or infinite) of arithmetic progressions of ratios $r_i, i \geq 1$ , and suppose that their union is $\Bbb{N}=\{0,1,2,...\}$ . Prove that $\sum_{ n \geq 1}\displaystyle \frac{1}{r_i} \geq 1$ .

Categories: Algebra, Combinatorics, Probability, Problem Solving Tags: Probability, trick

2 Hunters

March 25, 2010 beni22sof Leave a comment

Suppose $A$ and $B$ are two hunters having the same abilities, which means that the probability that $A$ kills his prey is equal to the probability that $B$ kills his prey. During their hunting sessions $A$ aimed $n+1$ ducks and $B$ aimed $n$ ducks. What is the probability that $A$ shot more ducks than $B$ did?