Logic+ 02: UNIZOR.COM - Math+ & Problems - Logic

Notes to a video lecture on http://www.unizor.com

Logic 02

Problem A

The game starts with two sets of stones and two players.
At each turn a player can take any number of stones but only from one of the sets.
The winner is the player who takes the last stones.

The player who should start the game can yield this right of the first move to his opponent. After that to take some stones on each move is the rule.

What is the winning strategy for a person who starts the game?

Solution A

The strategy to win for the first player is on every move to equalize the number of stones in two sets.

If the initial number of stones is different in these two sets, the first move of the player who starts the game is to take a few stones from a bigger set to equalize the number of stones.

His opponent, always facing two equal numbers of stones in two sets, cannot take the last stone and inevitably will make the number of stones in two sets different.

If in the beginning the numbers of stones in these two sets are equal, the player who starts the game should yield the right of the first move to his opponent, achieving the same conditions as above.


Problem B

There is a set of six points, no three points of this set lie on a straight line.
For clarity we can assume that they lie on a circle, though it's not essential.


Consider all subsets of three points of this set of six (we will call these subsets triplets).
Let's call a triplet, that has one or more segments connecting its points, a good triplet.
If all three points of a good triplet are connected by three segments, we will call this triplet a triangle.



For example, on the picture below all triplets have at least one pair connected by a segment (triplet ABC has two segments AB and AC, triplet CDF has two segments CF and DF, triplet ABF has one segment AB etc.)

Let's try to connect some points with segments in such a way that in any triplet there would be a pair of points connected by a segment.
That is, let's try to make all triplets good.

Prove that, no matter how we try to accomplish this task of making all triplets good by connecting our six points, there would inevitably be a triplet with three segments connecting all its three points into a triangle (that is, there will be at least one triangle), like ΔACE or ΔCEF in the example above.

Solution B

First, let's prove the following auxiliary statement (lemma) using the following illustration.


Assume that all triplets are good (as assumed in the Problem B) and some point (for example, A on the picture above) has three segments joining at it and connecting it to three other points (like on the picture above, point A is connected to B, C and E).
Then there exist a triangle.

Proof:
Since a triplet of three connected points (BCE on the picture above) is, as all other triplets, assumed to be good, there exists an additional connecting segment between some of its points (between C and E on the picture above).
With three given segments going from a point with three connections (AB, AC and AE on the picture above) and one additional segment between some connected points (segment CE between C and E on the picture above), there is a triplet (in our example it is ACD) that forms a triangle.

Consequently, to prove that in the process of connecting pairs of points to make all triplets good there would eventually have to be formed a triangle, it's sufficient to prove that there would eventually have to be a point with three segments connecting it to other three points.

The plan is to
(1) count all the triplets that can be formed from the given six points and
(2) show that without connecting three points into a triangle or connecting some point to three others (which, as lemma above proved, leads to forming a triangle) it's impossible to make all counted in (1) triplets good.

The total number of triplets is, obviously, the number of combinations of our six points in groups of three, which is
C₆³ = 6!/(3!·3!) = 20

Now let's proceed to make all triplets good, but obeying the rule of having no more than two segments joining at any single point (since, as we have proved, when three segments join in one point, triangle is unavoidable).

We have to make 20 good triplets, but we will show that we cannot make more than 18 without breaking that rule, which would necessitate the existence of a point with three segments connecting it to three other points, which is sufficient condition for existence of a triangle.

Let's start the process of connecting pairs of points to make good triplets.

In the beginning there are no connecting segments, so we choose any two points (call them A and B) and connect them with a segment.
This is sufficient to make 4 new good triplets: ABC, ABD, ABE and ABF.


Now we have a choice of which points to connect next.
We can either
(a) choose a pair of new points to connect by a segment (for example, D and E) or
(b) choose one new (unconnected) point and one that already has a connecting segment (for example, B and C), or
(c) choose two points that already had connecting segments, which could happen on later steps.

In case (a) we have 4 more good triplets (DEA, DEB, DEC and DEF in our example).

In case (b) only 3 good triplets will be formed (BCD, BCE and BCF in our example).

In case (c) only 2 good triplets will be formed (if segments AB and CD exist, and we connect points B and C with a segment, new good triplets BCE and BCF are formed).

General consideration is that the more segments connect our six points - the more good triplets will be formed.

Let's start with the strategy that assures the maximum number of segments - the one when there are two segments joining at each point, so the rule of not having three segments at any point is preserved.

This can be accomplished if all points are connected into a closed chain:

Obviously, not all triplets are good in this case. For example, ACE or BDF.

Another chained connection
Here triplets ABD or CEF are not good.

Let's count good triplets using the first example of a chained connection above, starting from segment AB and moving clockwise (the order is unimportant, we can connect A-C-B-F-D-E-A, as exemplified on the second picture, and the result will be the same).
Segment AB, being the first, produced 4 good triplets, as was stated above.
Then four consecutive segments BC, CD, DE and EF formed 3 good triplets each.
Final segment FA added 2 more good triplets.
The total number of good triplets is
4+3+3+3+3+2=18
which is short of required 20, which means, to make all triplets good, we need more segments, which will result in some points to be connected by three segments to three other points and forming of a triangle will be guaranteed.

We can try to organize connections differently. Instead of putting all 6 points into a chain, we can do it with only 5 with points A-B-C-D-E, leaving point F outside.

Similar counting of good triplets will result in the following:
Segments AB, as before, created 4 good triplets.
Segments BC, CD, DE, as before, created 3 good triplets each.
Finally, segment EA created two new good triplets: EAC and EAF.
The total number of good triplets is:
4+3+3+3+2 = 15

The last case is to leave two points out of a closed chain as follows.

In this case the number of good triplets is:
from AB - 4,
from BC - 3,
from CD - 3,
from DA - 2 (DAE, DAF),
from EF - 4 (EFA, EFB, EFC, EFD)
The total number of good triplets is:
4+3+3+2+4 = 16
Still less than 20.

There are no logically different cases of connecting the points deserving a consideration, so we came to
CONCLUSION:
to have all 20 triplets as good, we need more that two segments joining at each point; it is impossible to avoid triangles.

Arithmetic+ 02: UNIZOR.COM - Math+ & Problems - Arithmetic

Notes to a video lecture on http://www.unizor.com

Arithmetic 02


Problem

Prove that
S_N = Σ_n∈[2,N]1/n
is not an integer number for any integer N.

Solution 1

Among fractional numbers in the sum S_N there are those of type 1/(2^k).
Let's choose among them the one with the maximum power k. This number is less than any other number of this type in a series and the closest to the end of a series among them. Let's call it the least binary fraction.

For example, in the sum
S₁₀ = Σ_n∈[2,10]1/n
we choose 1/8=1/(2³).

Now let's bring all the numbers in a series to the least common denominator (LCD).
For an example of S₁₀ the LCD=2520 and values of our fractions with this LCD are
1/2 = 1260/2520
1/3 = 840/2520
1/4 = 630/2520
1/5 = 504/2520
1/6 = 420/2520
1/7 = 360/2520
1/8 = 315/2520
1/9 = 280/2520
1/10 = 252/2520

Notice that the numerator of 1/8=315/2520 (a fraction of a type 1/(2^k) with maximum power k) equals 315, which is odd, while all other numerators are even.
That means, the sum of numerators with this common denominator is odd, while the least common denominator 2520 is even, which means that the sum S₁₀ cannot be an integer number.

Actually, this situation will be similar with any number of members in a series, that is for any N.
Here is why (and this is the required proof).

Let's analyze the process of determining the least common denominator (LCD).

Any number in the denominators of our series can be uniquely represented as a product of prime numbers.
Then LCD is formed from all the prime numbers in representation of all denominators with the quantity of each prime number being equal to the largest number of these primes among all denominators.

In our example of S₁₀ we have the following representation of denominators:
2 = 2
3 = 3
4 = 2·2
5 = 5
6 = 2·3
7 = 7
8 = 2·2·2
9 = 3·3
10 = 2·5

As we see, the prime numbers we have to use are 2,3,5,7 and the number of these primes in the LCD should be:
prime 2 should be taken 3 times because of denominator 8.
prime 3 should be taken 2 times because of denominator 9.
prime 5 should be taken once.
prime 7 should be taken once.
Therefore, the LCD is
2³·3²·5·7=2520

In general case, in the representation of LCD the number of 2's is the largest in a member 1/(2^k) with the largest k that we called above the least binary fraction.
Therefore, in the representation of the LCD as a product of prime numbers there are exactly k 2's and, obviously. other prime numbers, which are all odd, of course.

When we transform all the fractions in a series S_N to common denominator, we should multiply numerators (which are all 1's) by all primes in the LCD that are not in a representation of its denominator:

In our example of S₁₀
the numerator of a fraction 1/2 should be multiplied by 2³·3²·5·7/2 =
= 2²·3²·5·7 = 1260
the numerator of a fraction 1/3 should be multiplied by 2³·3²·5·7/3 =
= 2³·3·5·7 = 840
the numerator of a fraction 1/4 should be multiplied by 2³·3²·5·7/2² =
= 2·3²·5·7 = 630
the numerator of a fraction 1/5 should be multiplied by 2³·3²·5·7/5 =
= 2³·3²·7 = 504
the numerator of a fraction 1/6 should be multiplied by 2³·3²·5·7/(2·3) =
= 2²·3·5·7 = 420
the numerator of a fraction 1/7 should be multiplied by 2³·3²·5·7/7 =
= 2³·3²·5 = 360
the numerator of a fraction 1/8 should be multiplied by 2³·3²·5·7/2³ =
= 3²·5·7 = 315
the numerator of a fraction 1/9 should be multiplied by 2³·3²·5·7/3² =
= 2³·5·7 = 280
the numerator of a fraction 1/10 should be multiplied by 2³·3²·5·7/(2·5) =
= 2²·3²·7 = 252

As a result, the only numerator without any 2's in its representation as a product of primes will be the one in the one we called the least binary fraction.
That's why this numerator will be odd, while all others (with one or more 2's in their prime representation) will be even.
Therefore, the sum of all these numerators with the least common denominator will be odd and not divisible by the LCD, which is even.


Solution 2

Among the fractions of our series there are those with prime denominators, which we will call prime fractions.
Let's choose among all prime fractions the one with the largest prime denominator P_max (hence, the smallest in value among all prime fractions) and call it the least prime fraction.
So, P_max is the largest prime number not exceeding N.

At this point it's very important to state that all subsequent members of the series after 1/P_max up to the last one 1/N have denominators not multiple of P_max.
The reason why it is the case is based on so called Bertrand's postulate that states (and can be proven, but not at this moment) that for any integer M there exists a prime number p greater than M and less than 2·M−2.

If there is another fraction with denominator being a multiple of P_max than its denominator is, obviously, not less than 2·P_max and, according to the Bertrand's postulate, there must be another prime number between P_max and 2·P_max, so P_max is not the largest prime number not exceeding N.

In our example with S₁₀ P_max=7 and the least prime fraction is 1/7.

Now let's bring all the numbers in a series to the least common denominator (LCD) in order to sum up all numerators.
Since this least prime fraction has the largest prime denominator, this prime denominator will be represented only once in the LCD.

In our example with S₁₀ LCD is 2³·3²·5·7=2520 and, as we see, number 7 is presented only once.

The next step to calculate S_N is to bring all fractions to the least common denominator by multiplying each numerator (all numerators are 1's) by all prime numbers in the LCD that are not in a prime representation of a corresponding denominator.

Because the largest prime denominator in a series occurs only once in the LCD and does not occur in prime representation of any denominator other than that of the least prime fraction, this largest prime denominator will be represented in all new numerators of all fractions with common denominator except in the numerator of the least prime fraction.

Consequently, all new numerators, except the one of the least prime fraction will be divisible by P_max.

In our example with S₁₀ and P_max=7 the prime number 7 occurs exectly once in every new numerator except for 1/7.
Therefore, the sum of these new numerators will not be divisible by P_max and the result of the summation cannot be an integer number.

Arithmetic+ 01: UNIZOR.COM - Math+ & Problems - Arithmetic

Notes to a video lecture on http://www.unizor.com

Arithmetic 01


Problem A

Given n pieces of rope.
Some of them are cut into n smaller pieces.
Then, again, some of the obtained pieces are cut into n smaller one.
This process is repeated a few times and, as a result, the final number of pieces is N.
Prove that N−n is divisible by n−1.

Solution A

Assume, out of initial n pieces of rope we have chosen k₁ to cut each into n pieces.
Then, after the first cut we will have the total number of pieces equal to
N₁ = n − k₁ + n·k₁ =
= n + (n−1)·k₁
As we see, N₁−n is divisible by n−1.

Assume, out of obtained after the first step N₁ pieces of rope we have chosen k₂ to cut each into n pieces.
Then, after the second cut we will have the total number of pieces equal to
N₂ = N₁ − k₂ + n·k₂ =
= N₁ + (n−1)·k₂ =
= n + (n−1)·k₁ + (n−1)·k₂ =
= n + (n−1)·(k₁+k₂)
As we see, N₂−n is also divisible by n−1.

Obviously, it's easy to prove by induction that after s^th step the number of obtained pieces of rope will be
N_s = n + (n−1)·(k₁+k₂+...+k_s )
and N_s−n will be divisible by n−1, which is what's required to prove.


Problem B

One person thinks about some number from 0 to 1000.
Another person can ask questions about this number to determine it.
What is the minimum number of questions needed to find this number, if the answers can be either YES or NO?

Solution B

Considering the answers are YES or NO, one of the ways is to find the binary expression for the number.
Since the number is less than 1024=2¹⁰, it's sufficient to ask 10 questions about each binary digit.

So, the first question is: "Is the first digit in a binary representation of your number as 10 binary digits (including leading zeros) equal to 1? Based on the answer, we determine this first digit to be 1 or 0.
Then we repeat the same for the second binary digit etc.

Alternatively, the number can be guessed by multiple steps of dividing the group of all possible numbers into two approximately equal parts.
Then the first question should be: "Is your number greater than 500?".
If the answer is YES, the next question is "Is it greater than 750?", but if the answer is NO, the next question is "Is it greater than 250?".
And so on.


Problem C

There is a set of 100 numbers, each from 1 to 9.
The sum of these numbers is 789.
Is it possible to choose 70 numbers out of this set with a sum less than 500?

Solution C

If we select 70 numbers with a total sum of less than 500, the remaining 30 numbers must have sum not less than 789−500=289.
But the maximum sum of 30 numbers, each of which is from 1 to 9, is 9·30=270, which is insufficient to cover 289 needed to complete the total sum to 789.

Answer C
It is impossible to choose 70 numbers out of this set with a sum less than 500.


Problem D

A regular clock with large round face and 12 numbers for 12 hours is used for this problem.
A coin is placed onto each number of this clock - a total of 12 coins.
In one move two coins should be moved from their numbers into a neighboring ones, but one of these coins should move clockwise, while another - counterclockwise.

Is it possible to collect all coins on one number on the clock by performing th described moves?

Solution D

Assign a value to each position of coins as follows.
If there are n_i coins on number i, the value of this coin position is
V = Σ_i∈[1,12] i·n_i

Initially, when there is one coin per number on a clock, the total value is
V=1+2+3+4+5+6+
+7+8+9+10+11+12=78.

In one step one coin that is on number n and steps clockwise will increase the value V of a position by 1 except when it moves from number n=12 to n=1, in which case the value of a position will decrease by 11.

In one step one coin that is on number n and steps counterclockwise will decrease the value V of a position by 1 except when it moves from number n=1 to n=12, in which case the value of a position will increase by 11.

The combination of these two steps, which constitutes a single move, will either retain the same value of a position (for example, 3→4, 10→9) or increase the value by 12 (for example, 3→4, 1→12) or decrease the value by 12 (for example, 4→3, 12→1).

In any case, no matter how many moves we make, the value of a position V is changing by a number that is a multiple of 12.

But, if we consider the value of a position when all 12 coins are on the same clock number n, the value of a position is V=12·n - a multiple of 12.

Starting from an initial position value of 78 (not a multiple of 12) and changing this value by a number that is a multiple of 12 on each move, we will never come to a position whose value is a multiple of 12.

This proves the impossibility to gather all coins on the same clock number.

Logic+ 01: UNIZOR.COM - Math+ & Problems

Notes to a video lecture on http://www.unizor.com

Logic 01

Problem A

Given a rectangular matrix with m rows and n columns.
It's filled with real numbers, and all m·n numbers are different.

First, we go through all rows and choose the smallest number in each row, getting m numbers.
Then we choose the largest among these chosen m numbers X and call it minimax.

Similarly, we go through all columns of this matrix and choose the largest number in each column, getting n numbers.
Then we choose the smallest among these chosen n numbers Y and call it maximin.

Which number is larger, maximin Y or minimax X?

Solution A

Assume. X is from row i and Y is from column j If X and Y happened to be from the same row i, X≤Y, because X is chosen as the smallest number in this row.

If X and Y happened to be from the same column j, X≤Y, because Y is chosen as the largest number in this column.

If X and Y do not share the same row nor the same column, consider an element Z from the same row iY as X and the same column j as Y.

X is smaller than Z, because they share a row i and X is the smallest in this row.
Y is larger than Z, because they share a column j and Y is the largest in this column.
Since X≤Z≤Y, X is smaller or equal to Y.

Answer A
Under any circumstances X≤Y.

Examples A
A case when MaxiMin equals to MiniMax.

	Col1	Col2	MaxiMin
Row1	1	2	1
Row2	3	4	3
MiniMax	3	4

A case when MaxiMin is larger than MiniMax.

	Col1	Col2	MaxiMin
Row1	1	3	1
Row2	4	2	2
MiniMax	4	3

Problem B

There was a crime committed by someone and three suspects, X, Y and Z are interrogated. One of them was the person who committed this crime.

Here is the protocol of interrogations.
X stated:
(a) I did not do it and
(b) Y did not do it.
Y stated:
(a) X did not do it and
(b) Z did it.
Z stated:
(a) I did not do it and
(b) X did it.

Subsequent interrogations found that one of the suspects lied twice, another told truth twice and yet another one told one truth and one lie.

Who committed the crime?

Solution B

To solve this problem, we have to consider different cases.

Case 1: X said the truth twice.
It follows then that Z is the criminal. But that means that Y said the truth twice, which cannot be because the problem specifies that only one suspect said truth twice.
So, Case 1 is not what really took place.

Case 2: X lied twice.
This is impossible because it means that both X and Y committed this crime, but there should be only one criminal.

Therefore, what really took place was: X said one lie and one truth.
But which is which?

Assume, his (a) statement was the truth. Then his (b) statement is the lie and Y is a criminal.

Both statements of Y must be either truths or lies.
But both Y's statements being truths implies that Z committed a crime, not Y, which contradict our last assumption.
And both Y's statements being lies implies that X committed a crime, not Y, which also contradicts that same assumption.

The only remaining choice is that X's (a) statement was a lie and his (b) statement is the truth.
That implies that X committed a crime.
Now from this follows that both statements of Y are lies and both statements of Z are the truth.
It fully corresponds to conditions of the problem.

Answer B
X has committed a crime.


Problem C

After work one person likes to have dinner in one of two of his favorite restaurants, let's call them A and B.
These restaurants are located on opposite ends of the city from this person's place of work.

His work ends at some random time between 5 and 6 o'clock. Then he goes down to a train station, where on the same platform two trains going in opposite directions stop.

When this person is at the platform, he takes the first train that comes and, subsequently has dinner in either restaurant A or B, depending on which train came first.

Trains in each direction come with periodicity of 5 minutes.

At the end of a year this person discovers that he attended restaurant A 4 times more than restaurant B.
What is an explanation for such a significant discrepancy?

Solution C

The timing between trains coming in the same direction is 5 minutes, but the timing between trains going in opposite direction is not specified.
Apparently, the timing between train going in the direction of restaurant A and that going towards B is a quarter of the time between a train towards B and towards A.

Assume the following train schedule.
Trains towards A come at 5:00, 5:05, 5:10, 5:15 etc.
Trains towards B come at 5:01, 5:06, 5:11, 5:16 etc.

If our person comes after 5:00 but before 5:01, he would take the train towards B, but after 5:01 but before 5:05 he would go to restaurant A.
Analogously, between 5:05 and 5:06 he would take the train towards B, but from 5:06 to 5:10 he would go to A.

As we see, he has an opportunity to go to B during 1 minute intervals, after which he would go to A during the next 4 minutes intervals.
That's the explanation of such a significant discrepancy in attendance of these two restaurants.

Who Needs Problems? UNIZOR.COM - Math+ & Problems

Notes to a video lecture on http://www.unizor.com

Who Needs Problems?

Nobody.
Nobody needs problems.
People need solutions.

But how to derive with a solution for a problem that nobody before you had solved?

To answer this really difficult and complicated question is the purpose of Math+ & Problems part of this Web site.

First of all, let's clarify what we mean saying "Math+".
We all know what Math is - a set of subjects like Algebra, Geometry, Combinatorics etc.
Math+ is, basically, all of these and some less typical, unusual, tricky, unexpected aspects of all these subjects, usually presented in a form of problems that require less typical approach to solving them.

The purpose of presenting these less typical and often more difficult problems is to introduce students to thinking outside the box, when it comes to solving problems. This quality will be extremely helpful in practically all aspects of real life.

Stepping outside the usual approaches to solving practical problems is how real progress is achieved.
Math+ & Problems is a training ground for students' minds to develop the ability to invent, find, connect different pieces of information into a solution of important problem.

The problems presented in Math+ & Problems part of this Web site are, mostly, taken from books mentioned in the References page of this site. Major sources are books by Shklyarsky, Yaglom and Chentsov and also from a book by Modenov.