## Project Euler Problem 285

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.

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…

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)

## Problems of the Miklos Schweitzer Competition 2014

**Problem 1.** Let be a positive integer. Let be a familiy of sets that contains more than half of all subsets of an -element set . Prove that from we can select sets that form a separating family of , i.e., for any two distinct elements of there is a selected set containing exactly one of the two elements.

**Problem 2.** let and let be non-degenerate subintervals of the interval . Prove that

where the summation is over all pairs of indices such that and are not disjoint.

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

**Problem 4.** For a positive integer , let be the number of sequences of positive integers such that and for . We make the convention . Let be the unique real number greater than such that . Prove that

- (i) .
- (ii) There exists no number such that .

**Problem 5.** Let be a non-real algebraic integer of degree two, and let be the set of irreducible elements of the ring . Prove that

**Problem 6.** Let be a representation of a finite -group over a field of characteristic . Prove that if the restriction of the linear map to a finite dimensional subspace of is injective, then the subspace spanned by the subspaces () is the direct sum of these subspaces.

**Problem 7.** Lef be a continuous function and let be arbitrary. Suppose that the Minkowski sum of the graph of and the graph of (i.e. the set has Lebesgue measure zero. Does it follow then that the function is of the form , with suitable constants ?

**Problem 8.** Let be a fixed integer. Calculate the distance

where runs over polynomials of degree less than with real coefficients and runs over functions of the form

defined on the closed interval , where and .

**Problem 9.** Let , and let be a convex body, i.e. a compact convex set with nonempty interior. Define the barycenter of the body with respect to the weight function by the usual formula

Prove that the translates of the body have pairwise distinct barycenters with respect to .

**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 be a random variable that is uniformly distributed on the interval , and let

Show that, as , the limit distribution of is the Cauchy distribution with density function .

## Two examples of Probability applications

**Problem 1.** The probability that an animal reacts positively to an injection is . 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.

## Miklos Schweitzer 2013

**Problem 1.** Let be an integer. Prove that there exists an integer such that for any finite set containing only integers we have

( is the set of integers of the form where )

**Problem 2.** Prove that there is a constant such that the diophantine equation

has no positive integer solutions for . (here I guess needs to be an integer, or else the conclusion is clearly false)

**Problem 3.** What are the numbers for which the alternating group has a permutation which is contained in exactly one -Sylow subgroup of ?

**Problem 4.** Let be an Abelian group with elements. Prove that there are two subgroups in , isomorphic to , whose intersection is isomorphic to the automorphism group of .

**Problem 5.** A subalgebra of a Lie algebra is said to have tha property with respect to a scalar product given on if implies for all . Prove that the maximum dimension of -property subalgebras of a given step nilpotent Lie algebra with respect to a scalar product is independent of the selection of the scalar product.

**Problem 6.** Let be a algebra with a unit element and let be the cone of the positive elements of (this is the set of such self adjoint elements in whose spectrum is in . Consider the operation

Prove that if for all we have

then is commutative.

**Problem 7.** Suppose that is an additive function (that is for all ) for which is bounded of some nonempty subinterval of . Prove that is continuous. [**Solution**]

**Problem 8.** Let be a continuous and strictly increasing function for which

for all ( denotes the inverse of ). Prove that there exist real constants and such that for all . [**Solution]**

**Problem 9.** Prove that there is a function which is nowhere continuous and for all and any rational we have

Is there such a function if instead the above relation holds for every and for every irrational .

**Problem 10.** Consider a Riemannian metric on the vector space which satisfies the property that for each two points there is a single distance minimising geodesic segment . Suppose that for all , the Riemannian distance with respect to , is convex and differentiable outside of . Prove that if for a point we have

then is a point on and conversely.

**Problem 11.** (a) Consider an ellipse in the plane. Prove that there exists a Riemannian metric which is defined on the whole plane, and with respect to which the ellipse is a geodesic. Prove that the Gaussian curvature of any such Riemannian metric takes a positive value.

(b) Consider two nonintersecting, simple closed smooth curves in the plane. Prove that if there is a Riemmanian metric defined on the whole plane and the two curves are geodesics of that metric, then the Gaussian curvature of the metric vanishes somewhere.

**Problem 12.** There are tokens in a pack. Some of them (at least one, but not all) are white and the rest are black. All tokens are extracted randomly from the pack, one by one, without putting them back. Let be the ratio of white tokens in the pack before the -th extraction and let

Prove that , where .

(Thanks again to Eles Andras for the translation of the problems from Hungarian to English)

## How can everybody (probably) get the right change?

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 people wait in line to buy cinema tickets. The price is euros, and the customers all have bills of and euros (to be more precise people have euros bills and people have euros bills). Note that there are more people with euros bills than those with euros bills, so in the end everybody could receive change, even if the cashier has no 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 euro bills in the beginning.

The worst case is when all clients with euros bills are first in line, case in which the cashier would need bills of 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 . How many euros bills would the cashier need to fulfill this goal? How many bills does he need to reach a probability of ?

## Miklos Schweitzer 2012 Problems

**1.** Is there any real number for which there exist two functions such that

but the function which associates to the -th decimal digit of is not recursive?

**2.** Call a subset of the cyclic group *rich* if for all there exists such that are all in . For what is there a constant such that for each odd positive integer , every *rich* subset has at least elements?

**3.** Prove that if a -chromatic graph’s edges are coloured in two colors in any way, there is a subtree with vertices and edges of the same color.

**4.** Let be a convex shape in the dimensional space, having unit volume. Let be a Lebesgue measurable set with measure at least , where . Prove that dilating from its centroid by the ratio of , the shape obtained contains the centroid of .

**5.** Let be four dimensional linear subspaces in such that the intersection of any two contains only the zero vector. Prove that there exists a linear four dimensional subspace in such that all four vector spaces are two dimensional.

**6.** Let be matrices with complex elements such that and , where denotes the commutator of the matrices. Prove that is the identity matrix. **[Solution]
**

**7.** Let be a simple curve, lying inside a circle of radius , rectifiable and of length . Prove that if , then there exists a circle of radius which intersects in at least distinct points.

**8.** For any function consider the function for which for any .

a) Is it true that if is Lebesgue measurable then is also Lebesgue measurable?

b) Is it true that if is Borel measurable then is also Borel measurable?

**9.** Let be the complex unit disk , and a real number. Suppose that is a holomorphic function such that and . Prove that

**10.** Let be a knot in the -dimensional space (that is a differentiable injection of a circle into ), and be the diagram of the knot (that is the projection of it to a plane so that in exception of the transversal double points it is also an injection of a circle). Let us color the complement of in black and color the diagram in a chessboard pattern, black and white so that zones which share an arc in common are coloured differently. Define the black graph of the diagram, a graph which has vertices in the black areas and every two vertices which correspond to black areas which have a common point have an edge connecting them.

a) Determine all knots having a diagram such that has at most spanning trees. (Two knots are not considered distinct if they can be moved into each other with a one parameter set of the injection of the circle)

b) Prove that for any knot and any diagram , has an odd number of spanning trees.

**11.** Let be independent random variables with the same distribution, and let . For what real numbers is the following statement true:

Miklos Schweitzer competition 2012 (many thanks to Eles Andras for the translation of the problems from Hungarian to English)