An Elementary Problem can be Unsolvable.

An Elementary Problem can be Unsolvable.

by 'Literka'.

An open problem we'll discuss on this page is the following:

Problem (Literka). Let {

} be a sequence of real numbers such that Rozmiar: 1672 bajtów

Let us consider

numbers of the form

(We take all possible of sums of elements with plus or minus signs). Show that among them there are at least

numbers such that

(Having absolute value smaller or equal 1).

Notice: Numbers corresponding to different sequences of signs we regard as distinct, although they may have equal values. In other words: we count also multiplicity of occuring numbers.

'Literka' will formulate this problem in a different way to avoid a possibility of misunderstanding:

Problem (Literka). Let {

} be a sequence of real numbers such that the sum of squares of elements is equal 1. Take the first number of this sequence with a sign '+' or with a sign '-'. Hence - we have 2 possibilities. To each of obtained 2 numbers add or subtract second number of the sequence. We'll have 4 numbers created that way. To each of them add or subtract third number….. etc. After the final step we'll have

numbers. Show that an absolute value of at least half of them is smaller or equal 1.

This problem was published by 'Literka' many years ago and still it is an open problem. This is a vicious problem, since sometimes it looks to be easy, many times it looks to be solved by a mathematician, who later realizes that he made a terrible mistake (unfortunately this also includes 'Literka').

This problem can be reformulated the following way:

Problem (Literka). Let {

} be a sequence of real numbers such that Rozmiar: 1672 bajtów

and take any number x>0.
Let M be a set of all numbers of the form

such that

Let N be a set of all numbers of the form

such that

Show that M has at least so many elements as N.
(Counting multiplicity of occuring elements).

All these 3 versions of a problem of 'Literka' are equivalent, although the last version looks to be stronger than others.

There are known and proved weaker forms of this problem. One of them was proved by 'Literka' and it is exactly a solution of a problem in the case that all numbers of a sequence are equal. In that case they are equal

Theorem. (Literka) Let {

} be a sequence of real numbers, all of them equal

Let x>0 be a real number.
Let M be a set of all numbers of the form

such that

Let N be a set of all numbers of the form

such that

Then M has at least so many elements as N.
(Counting multiplicity of occuring elements).

The problem and theorem of 'Literka' can be written in terms of probability. We say that a sequence

of random variables is a Bernoulli sequence of independent random variables if all

are independent and for each i we have

Problem (Literka). Let

} be a Bernoulli sequence of independent random variables. Let {

} be a sequence of real numbers such that Rozmiar: 1672 bajtów

Let us define Rozmiar: 2373 bajtów

Prove that

As before this problem can be reformulated in a seemingly stronger form:

Problem (Literka). Let

} be a Bernoulli sequence of independent random variables. Let {

} be a sequence of real numbers such that Rozmiar: 1672 bajtów

and x>0 be a real number.
Let us define Rozmiar: 2373 bajtów

Prove that

A partial result obtained by 'Literka' is the following:

Theorem (Literka). Let

} be a Bernoulli sequence of independent random variables. Let {

} be a sequence of real numbers all of them equal

Let x>0 be a real number.
Let us define Rozmiar: 2373 bajtów

Then

For those, who do not like hard and unsolved problems, 'Literka' also has something. Take x from the third version of the problem to be less than the sum of all elements. Then the the set N is non-empty. If problem is true, then the set M must be non-empty. We conclude the following:

Remark (Literka). Let {

} be a sequence of real numbers such that Rozmiar: 1672 bajtów

Then there exists a sequence of signs

(i.e. sequence of numbers equal 1 or -1) such that Rozmiar: 3418 bajtów

'Literka' is sure that you can easily prove it.

Remark. Mr. Daniel Kim Murphy, who is a math student of MIT, wrote Literka about partial results of this problem. Weaker inequality was proved by Professor Daniel Kleitman and Professor Ron Holzman (see "Combinatorica" 1992 (volume 2) page 303 ). They proved the conjecture with a constant 3/8 instead of 1/2.

See the list and descriptions of mathematical pages from Mathematical Countryside.

See other pages of 'Literka' from Mathematical Countryside:
Monotonic subsequences.
Weight centers of simple geometrical figures.
Roots of cubic equation. Cardano's formula.
Rudin's Theorem of Complex Analysis.
Exact values of trigonometric functions of angles (n*pi)/17.
Equalities for values of trigonometric functions of angles (n*pi)/17.
Factorization of a polynomial, which defines values of sine function (angles n*pi/17).
Polynomials with roots cos(2*k*pi/n).
Factorization of polynomials with roots cos(2*k*pi/n), where n is Fermat number.
Values of trigonometric functions of angles (n*pi)/257. Part I.
Values of trigonometric functions of angles (n*pi)/257. Part II, Part III, Part IV, Part V, Part VI, Part VII.
Values of trigonometric functions of angles (n*pi)/65537. Part I.
Values of trigonometric functions of angles (n*pi)/65537. Part II, Part III, Part IV and Part V, Part VI, Part VII Part VIII, Part IX, Part X, Part XI, Part XII, Part XIII, Part XIV.
A remarkable monotonic property of the gamma function .
Weierstrass Approximation Theorem. Bernstein's Polynomials.
Construction of a regular pentagon.
Construction of a regular heptadecagon.
Construction of a regular polygon with 257 sides.

Software that you really need.

Return to the list of pages of 'Literka' about polytopes.
Return to the main geometrical page of 'Literka'.
Return to the main page of 'Literka'.