https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Kreisaisjelis&feedformat=atomAoPS Wiki - User contributions [en]2024-03-28T13:51:56ZUser contributionsMediaWiki 1.31.1https://artofproblemsolving.com/wiki/index.php?title=2003_IMO_Problems/Problem_1&diff=1121282003 IMO Problems/Problem 12019-11-24T20:09:56Z<p>Kreisaisjelis: Added the official solution from the shortlist</p>
<hr />
<div><math>S</math> is the set <math>\{1, 2, 3, \dots ,1000000\}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\{a + x_i \mid a \in A\}</math> are all pairwise disjoint.<br />
<br />
==Solution==<br />
<br />
Consider the set <math>D=\{x-y \mid x,y \in A\}</math>. There are at most <math>101 \times 100 + 1 =<br />
10101</math> elements in <math>D</math>. Two sets <math>A + t_i</math> and <math>A + t_j</math> have nonempty intersection if and only if<br />
<math>t_i - t_j</math><br />
is in <math>D</math>. So we need to choose the <math>100</math> elements in such a way that we do not use a<br />
difference from <math>D</math>.<br />
Now select these elements by induction. Choose one element arbitrarily. Assume that<br />
<math>k</math> elements, <math>k \leq 99</math>, are already chosen. An element <math>x</math> that is already chosen prevents us<br />
from selecting any element from the set <math>x + D</math>. Thus after <math>k</math> elements are chosen, at most<br />
<math>10101k \leq 999999</math> elements are forbidden. Hence we can select one more element.<br />
<br />
==See Also==<br />
{{IMO box|year=2003|before=|num-a=2}}<br />
[[Category:Olympiad Combinatorics Problems]]</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2003_IMO_Problems/Problem_1&diff=1121202003 IMO Problems/Problem 12019-11-24T15:04:50Z<p>Kreisaisjelis: Added see also box and a category</p>
<hr />
<div><math>S</math> is the set <math>\{1, 2, 3, \dots ,1000000\}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\{a + x_i \mid a \in A\}</math> are all pairwise disjoint.<br />
<br />
<br />
==See Also==<br />
{{IMO box|year=2003|before=|num-a=2}}<br />
[[Category:Olympiad Combinatorics Problems]]</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2003_IMO_Problems/Problem_1&diff=1121052003 IMO Problems/Problem 12019-11-24T14:39:23Z<p>Kreisaisjelis: Problems in tex formulas</p>
<hr />
<div><math>S</math> is the set <math>\{1, 2, 3, \dots ,1000000\}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\{a + x_i \mid a \in A\}</math> are all pairwise disjoint.</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2003_IMO_Problems/Problem_1&diff=1121042003 IMO Problems/Problem 12019-11-24T14:36:00Z<p>Kreisaisjelis: Problems in tex formulas</p>
<hr />
<div><math>S</math> is the set <math>\set{1, 2, 3, \dots ,1000000}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\set{a + x_i \mid a \in A}</math> are all pairwise disjoint.</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2003_IMO_Problems/Problem_1&diff=1121032003 IMO Problems/Problem 12019-11-24T14:34:21Z<p>Kreisaisjelis: Typed in the problem from official pdf</p>
<hr />
<div><math>S</math> is the set <math>\set{1, 2, 3, . . . , 1000000}</math>. Show that for any subset <math>A</math> of <math>S</math> with <math>101</math> elements we can find <math>100</math> distinct elements <math>x_i</math> of <math>S</math>, such that the sets <math>\set{a + x_i<br />
\mid a \in A}</math> are all pairwise disjoint.</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2017_IMO_Problems/Problem_3&diff=952792017 IMO Problems/Problem 32018-06-18T10:22:58Z<p>Kreisaisjelis: </p>
<hr />
<div>==Problem==<br />
A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, <math>A_0</math>, and the hunter's starting point, <math>B_0</math>, are the same. After <math>n-1</math> rounds of the game, the rabbit is at point <math>A_{n-1}</math> and the hunter is at point <math>B_{n-1}</math>. In the nth round of the game, three things occur in order.<br />
<br />
(i) The rabbit moves invisibly to a point <math>A_n</math> such that the distance between <math>A_{n-1}</math> and <math>A_n</math> is exactly 1.<br />
<br />
(ii) A tracking device reports a point <math>P_n</math> to the hunter. The only guarantee provided by the tracking device is that the distance between <math>P_n</math> and <math>A_n</math> is at most 1.<br />
<br />
(iii) The hunter moves visibly to a point <math>B_n</math> such that the distance between <math>B_{n-1}</math> and <math>B_n</math> is exactly 1.<br />
<br />
Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after <math>10^9</math> rounds she can ensure that the distance between her and the rabbit is at most 100?<br />
==Solution==</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2000_IMO_Problems/Problem_4&diff=952782000 IMO Problems/Problem 42018-06-18T09:42:32Z<p>Kreisaisjelis: /* Solution */</p>
<hr />
<div>==Problem==<br />
A magician has one hundred cards numbered <math>1</math> to <math>100</math>. He puts them into three boxes,<br />
a red one, a white one and a blue one, so that each box contains at least one card.<br />
<br />
A member of the audience selects two of the three boxes, chooses one card from each<br />
and announces the sum of the numbers on the chosen cards. Given this sum, the magician<br />
identifies the box from which no card has been chosen.<br />
<br />
How many ways are there to put all the cards into the boxes so that this trick always<br />
works? (Two ways are considered different if at least one card is put into a different box.)<br />
<br />
==Solution==<br />
Consider <math>1</math>, <math>2</math> and <math>3</math>. If they are in different boxes, then <math>4</math> must be in the<br />
same box as <math>1</math>, <math>5</math> in the same box as <math>2</math> and so on. This leads to the solution where all<br />
numbers congruent to each other mod <math>3</math> are in the same box.<br />
<br />
Suppose <math>1</math> and <math>2</math> are in box <math>A</math> and <math>3</math> in box <math>B</math>. Then <math>4</math> must be in box <math>A</math> or <math>B</math>. In<br />
general, if <math>k\ge 4</math> is in either box <math>A</math> or <math>B</math>, then <math>k + 1</math> also must be in box <math>A</math> or <math>B</math>. Thus box<br />
<math>C</math> is empty which is impossible.<br />
<br />
Similarly, it is impossible for <math>1</math> and <math>3</math> to be in box <math>A</math> and <math>2</math> in box <math>B</math>.<br />
<br />
Thus we are left with the case where <math>1</math> is in box <math>A</math> and <math>2</math> and <math>3</math> in box <math>B</math>. Suppose box<br />
<math>B</math> contains <math>2, . . . k</math>, where <math>k \ge 3</math>, but does not contain <math>k + 1</math> and <math>m</math> is the smallest number in box <math>C</math>. <br />
Then <math>m > k</math>. <br />
<br />
If <math>m > k + 1</math>, then <math>k + 1</math> must be box <math>A</math> and we see that no box can<br />
contain <math>m-1</math>. <br />
<br />
Thus <math>m = k + 1</math>. If <math>k < 99</math>, we see that no box can contain <math>k + 2</math>. Thus<br />
<math>k = 99</math>. It is easy to see that this distribution works. Thus there altogether <math>12</math> ways - <math>2</math> options times permutation of <math>3</math> colors for each of <math>3</math> boxes.<br />
<br />
Taken from: https://sms.math.nus.edu.sg/Simo/IMO_Problems/00.pdf</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2000_IMO_Problems/Problem_4&diff=952772000 IMO Problems/Problem 42018-06-18T09:39:55Z<p>Kreisaisjelis: Added a problem and a solution</p>
<hr />
<div>==Problem==<br />
A magician has one hundred cards numbered <math>1</math> to <math>100</math>. He puts them into three boxes,<br />
a red one, a white one and a blue one, so that each box contains at least one card.<br />
<br />
A member of the audience selects two of the three boxes, chooses one card from each<br />
and announces the sum of the numbers on the chosen cards. Given this sum, the magician<br />
identifies the box from which no card has been chosen.<br />
<br />
How many ways are there to put all the cards into the boxes so that this trick always<br />
works? (Two ways are considered different if at least one card is put into a different box.)<br />
<br />
==Solution==<br />
Consider <math>1</math>, <math>2</math> and <math>3</math>. If they are in different boxes, then <math>4</math> must be in the<br />
same box as <math>1</math>, <math>5</math> in the same box as <math>2</math> and so on. This leads to the solution where all<br />
numbers congruent to each other <math>mod 3</math> are in the same box.<br />
<br />
Suppose <math>1</math> and <math>2</math> are in box <math>A</math> and <math>3</math> in box <math>B</math>. Then <math>4</math> must be in box <math>A</math> or <math>B</math>. In<br />
general, if <math>k\ge 4</math> is in either box <math>A</math> or <math>B</math>, then <math>k + 1</math> also must be in box <math>A</math> or <math>B</math>. Thus box<br />
<math>C</math> is empty which is impossible.<br />
<br />
Similarly, it is impossible for <math>1</math> and <math>3</math> to be in box <math>A</math> and <math>2</math> in box <math>B</math>.<br />
<br />
Thus we are left with the case where <math>1</math> is in box <math>A</math> and <math>2</math> and <math>3</math> in box <math>B</math>. Suppose box<br />
<math>B</math> contains <math>2, . . . k</math>, where <math>k \ge 3</math>, but does not contain <math>k + 1</math> and <math>m</math> is the smallest number in box <math>C</math>. <br />
Then <math>m > k</math>. <br />
<br />
If <math>m > k + 1</math>, then <math>k + 1</math> must be box <math>A</math> and we see that no box can<br />
contain <math>m-1</math>. <br />
<br />
Thus <math>m = k + 1</math>. If <math>k < 99</math>, we see that no box can contain <math>k + 2</math>. Thus<br />
<math>k = 99</math>. It is easy to see that this distribution works. Thus there altogether <math>12</math> ways - <math>2</math> options times permutation of <math>3</math> colors for each of <math>3</math> boxes.<br />
<br />
Taken from: https://sms.math.nus.edu.sg/Simo/IMO_Problems/00.pdf</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2013_IMO_Problems/Problem_2&diff=952762013 IMO Problems/Problem 22018-06-18T08:30:42Z<p>Kreisaisjelis: /* Solution */</p>
<hr />
<div>==Problem==<br />
A configuration of <math>4027</math> points in the plane is called ''Colombian'' if it consists of <math>2013</math> red points and <math>2014</math> blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is ''good'' for a Colombian<br />
configuration if the following two conditions are satisfied:<br />
*no line passes through any point of the configuration;<br />
*no region contains points of both colours.<br />
Find the least value of <math>k</math> such that for any Colombian configuration of <math>4027</math> points, there is a good<br />
arrangement of <math>k</math> lines.<br />
<br />
==Solution==<br />
<br />
We can start off by imagining the points in their worst configuration. <br />
With some trials, we find <math>2013</math> lines to be the answer to the worst cases. <br />
We can assume the answer is <math>2013</math>. We will now prove it.<br />
<br />
<br />
We will '''first''' prove that the sufficient number of lines required for a ''good'' arrangement for a configuration consisting of <math>u</math> red points and <math>v</math> blue points, where <math>u</math> is even and <math>v</math> is odd and <math>u - v = 1</math>, is <math>v</math>. <br />
<br />
Notice that the condition "no three points are co-linear" implies the following: <br />
No blue point will get in the way of the line between two red points and vice versa. <br />
What this means, is that for any two points <math>A</math> and <math>B</math> of the same color, we can draw two lines parallel to, and on different sides of the line <math>AB</math>, to form a region with only the points <math>A</math> and <math>B</math> in it. <br />
<br />
Now consider a configuration consisting of u red points and v blue ones (<math>u</math> is even, <math>v</math> is odd, <math>u>v</math>). <br />
Let the set of points <math>S = \{A_1, A_2, ... A_k\}</math> be the out-most points of the configuration, such that you could form a convex k-gon, <math>A_1 A_2 A_3 ... A_k</math>, that has all of the other points within it. <br />
<br />
If the set S has at least one blue point, there can be a line that separates the plane into two regions: one only consisting of only a blue point, and one consisting of the rest. For the rest of the blue points, we can draw parallel lines as mentioned before to split them from the red points.<br />
We end up with <math>v</math> lines. <br />
<br />
If the set <math>S</math> has no blue points, there can be a line that divides the plane into two regions: one consisting of two red points, and one consisting of the rest. For the rest of the red points, we can draw parallel lines as mentioned before to split them from the blue points.<br />
We end up with <math>u-1 = v</math> lines. <br />
<br />
'''Now''' we will show that there are configurations that can not be partitioned with less than <math>v</math> lines.<br />
<br />
Consider the arrangement of these points on a circle so that between every two blue points there are at least one red point (on the circle). <br />
<br />
There are no less than <math>2v</math> arcs of this circle, that has one end blue and other red (and no other colored points inside the arc) - one such arc on each side of each blue point.<br />
For a line partitioning to be good, each of these arcs have to be crossed by at least one line, but one line can not cross more than <math>2</math> arcs on a circle - therefore, this configuration can not be partitioned with less than <math>v</math> lines!<br />
<br />
Our proof is done, and we have our final answer: <math>2013</math>.<br />
<br />
==See Also==<br />
*[[2013 IMO]]</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=1989_USAMO_Problems/Problem_2&diff=930081989 USAMO Problems/Problem 22018-03-08T09:42:47Z<p>Kreisaisjelis: Alternative solution</p>
<hr />
<div>== Problem ==<br />
The 20 members of a local tennis club have scheduled exactly 14 two-person games among themselves, with each member playing in at least one game. Prove that within this schedule there must be a set of 6 games with 12 distinct players<br />
<br />
== Solution ==<br />
=== Solution 1===<br />
Consider a graph with <math>20</math> vertices and <math>14</math> edges. The sum of the degrees of the vertices is <math>28</math>; by the [[Pigeonhole Principle]] at least <math>12</math> vertices have degrees of <math>1</math> and at most <math>8</math> vertices have degrees greater than <math>1</math>. If we keep deleting edges of vertices with degree greater than <math>1</math> (a maximum of <math>8</math> such edges), then we are left with at least <math>6</math> edges, and all of the vertices have degree either <math>0</math> or <math>1</math>. These <math>6</math> edges represent the <math>6</math> games with <math>12</math> distinct players.<br />
<br />
=== Solution 2===<br />
Let a slot be a place we can put a member in a game, so there are two slots per game, and 28 slots total. We begin by filling exactly 20 slots each with a distinct member since each member must play at least one game. Let there be <math>m</math> games with both slots filled and <math>n</math> games with only one slot filled, so <math>2m+n=20</math>. Since there are only 14 games, <math>m+n \leq 14 \Longrightarrow 2m+n \leq 14+m \Longleftrightarrow 20 \leq 14+m \Longrightarrow m \geq 6</math>, so there must be at least 6 games with two distinct members each, and we must have our desired set of 6 games.<br />
<br />
=== Solution 3===<br />
Assume the contrary. <br />
<br />
Consider the largest set of disjoint edges <math>E</math>. By assumption it has less than <math>6</math> edges, i.e. maximum <math>10</math> vertices. <br />
Call it a vertex set <math>V</math>. <br />
<br />
<math>10</math> vertices remain outside <math>V</math> and each has to be attached to at least one edge. <br />
Now, if any two vertices outside <math>V</math> are connected by, say, edge <math>e</math>, we could have included <math>e</math> in <math>E</math> and gotten a larger disjoint set, so - a contradiction. <br />
Therefore the only option would be that all vertices outside <math>V</math> are connected each by one edge to some vertices inside <math>V</math>. That would take <math>10</math> edges, but <math>E</math> already includes <math>5</math> - again a contradiction. <br />
<br />
All possibilities yield a contradiction, so our assumption can not be correct.<br />
<br />
(Cases when largest set <math>E</math> is smaller than <math>6</math> are equivalent and weaker)<br />
<br />
== See Also ==<br />
{{USAMO box|year=1989|num-b=1|num-a=3}}<br />
{{MAA Notice}}<br />
<br />
[[Category:Olympiad Combinatorics Problems]]</div>Kreisaisjelishttps://artofproblemsolving.com/wiki/index.php?title=2012_IMO_Problems/Problem_3&diff=860052012 IMO Problems/Problem 32017-06-11T15:21:41Z<p>Kreisaisjelis: Created page with "The liar’s guessing game is a game played between two players A and B. The rules of the game depend on two positive integers k and n which are known to both players. At the..."</p>
<hr />
<div>The liar’s guessing game is a game played between two players A and B. The rules of the game depend on two positive integers k and n which are known to both players.<br />
<br />
At the start of the game the player A chooses integers x and N with 1≤x≤N. Player A keeps x secret, and truthfully tells N to the player B. The player B now tries to obtain information about x by asking player A questions as follows: each question consists of B specifying an arbitrary set S of positive integers (possibly one specified in some previous question), and asking A whether x belongs to S. Player B may ask as many questions as he wishes. After each question, player A must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any k+1 consecutive answers, at least one answer must be truthful.<br />
<br />
After B has asked as many questions as he wants, he must specify a set X of at most n positive integers. If x∈X, then B wins; otherwise, he loses. Prove that:<br />
<br />
(a) If n≥2k then B has a winning strategy.<br />
<br />
(b) There exists a positive integer k0 such that for every k≥k0 there exists an integer n≥1.99^k for which B cannot guarantee a victory.</div>Kreisaisjelis