Imo 2009 q6 - Revision history

Glasser: Minor fix

2013-06-13T19:19:35Z

Minor fix

← Older revision		Revision as of 12:19, 13 June 2013
Line 135:		Line 135:
	and the corresponding partial sums <math>s'_{j}=a_{0}+\sum_{i=1}^{j}a_{\rho(i)}</math>.		and the corresponding partial sums <math>s'_{j}=a_{0}+\sum_{i=1}^{j}a_{\rho(i)}</math>.

	Consider <math>j~~\leq~~\gamma</math>. Then <math>s'_{j}=s_{j}-a_{\phi(1)}+a_{\rho(j)}=s_{j}-a_{n}+a_{\phi(~~\gamma~~)}</math>.		Consider <math>j<\gamma</math>. Then <math>s'_{j}=s_{j}-a_{\phi(1)}+a_{\rho(j)}=s_{j}-a_{n}+a_{\phi(j+1)}</math>.
	And since <math>a_{n}=max(A)</math>, we have <math>s'_{j}<s_{j}\leq m_{1}</math>, and		And since <math>a_{n}=max(A)</math>, we have <math>s'_{j}<s_{j}\leq m_{1}</math>, and
	hence <math>s'_{j}\notin M</math>.		hence <math>s'_{j}\notin M</math>.

Glasser: Minor fix to proof 3: It said phi(0) instead of phi(1)

2013-06-13T19:16:27Z

Minor fix to proof 3: It said phi(0) instead of phi(1)

← Older revision		Revision as of 12:16, 13 June 2013
Line 128:		Line 128:
	\rho(x)=\begin{cases}		\rho(x)=\begin{cases}
	\phi(x+1) & 1\leq x<\gamma\\		\phi(x+1) & 1\leq x<\gamma\\
	\phi(0) & x=\gamma\\		\phi(1) & x=\gamma\\
	\phi(x) & \gamma<x		\phi(x) & \gamma<x
	\end{cases}		\end{cases}
Line 135:		Line 135:
	and the corresponding partial sums <math>s'_{j}=a_{0}+\sum_{i=1}^{j}a_{\rho(i)}</math>.		and the corresponding partial sums <math>s'_{j}=a_{0}+\sum_{i=1}^{j}a_{\rho(i)}</math>.

	Consider <math>j\leq\gamma</math>. Then <math>s'_{j}=s_{j}-a_{\phi(0)}+a_{\rho(j)}=s_{j}-a_{n}+a_{\phi(\gamma)}</math>.		Consider <math>j\leq\gamma</math>. Then <math>s'_{j}=s_{j}-a_{\phi(1)}+a_{\rho(j)}=s_{j}-a_{n}+a_{\phi(\gamma)}</math>.
	And since <math>a_{n}=max(A)</math>, we have <math>s'_{j}<s_{j}\leq m_{1}</math>, and		And since <math>a_{n}=max(A)</math>, we have <math>s'_{j}<s_{j}\leq m_{1}</math>, and
	hence <math>s'_{j}\notin M</math>.		hence <math>s'_{j}\notin M</math>.

Thomas.zeitlhoefler: All right, I finally got it. Your original solution was completely correct and i completely screwed up. I changed it to the original.

2010-09-28T07:38:02Z

All right, I finally got it. Your original solution was completely correct and i completely screwed up. I changed it to the original.

← Older revision		Revision as of 00:38, 28 September 2010
Line 31:		Line 31:
	Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.		Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

	Let I be the set of all <math>1\le i\le n-j</math> such that <math>a_i+a_{n-j+1}+\dots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. ~~Let x be the the greatest element of I.~~		Let I be the set of all <math>1\le i\le n-j</math> such that <math>a_i+a_{n-j+1}+\dots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1} </math> must lie in M, otherwise, we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> in j+1 steps by the induction hypothesis. Similarly, if i is the greatest element of I, <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math> must lie in M for any m equal to either i or n-j+1,...,n-1. But this forces M to contain n distinct elements, a contradiction. Specifically the n distinct elements are as follows:
			# <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> for <math>i\ {\not\in}\ I</math> ;
	For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1} ~~\in S_j~~</math> must ~~be a landmine~~, otherwise, we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> in j+1 steps by the induction hypothesis. Similarly, ~~each~~		# <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for <math>i\in I</math> ; and
	<math>~~a_x~~+a_{n-j+1}+\ldots+a_n - a_m</math> ~~where <math>~~ m ~~\in \{x,~~ n-j+1,~~\dots~~,n~~\}</math> must be~~ a ~~landmine and we can find~~ n distinct elements ~~of M~~ as follows:		# for the biggest <math>i\in I</math>, the numbers <math>a_i+a_{n-j+1}+\ldots+a_{n}-a_{m}</math>.
	# ~~For <math>1 \le i < x</math>, we have (x-1) numbers~~ <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for ~~i in I or~~ <math>~~a_i+a_~~{~~n-j+1}+~~\~~ldots+a_{n}</math> for i~~ not in I ~~(The former are in <math>S_j~~</math> ~~and the latter bigger than the greatest element~~ <math>a_{n-j+1}+\ldots~~+a_{n}</math> of <math>S_j</math>).~~
	~~# All j numbers <math>a_x~~+a_{n-j+1}~~+\ldots+a_n - a_m~~</math> ~~where~~ <math> ~~n-j+1 \le m~~ \~~le n</math> (all~~ in ~~<math>S_j~~</math>)
	# ~~The number~~ <math>~~a_{n-j+1}+~~\~~ldots+a_n</math> (~~in ~~<math>S_j~~</math>)
	~~# The are (n-j-x)~~ numbers <math>a_i+a_{n-j+1}+\ldots+a_{n}~~</math> for <math>x < i \le n~~-j</math> ~~(these i are not in I and greater than all other numbers mentioned before)~~

	~~Together, these are (x-1) + j + 1 + (n-j-x) = n elements of M, but M has only n-1 elements.~~

	~~So M contains at least n elements, a contradiction~~.

	== Proof #2 ==		== Proof #2 ==

Thomas.zeitlhoefler: Sorry for my last edit, the version before that had a little mistake and my attempt to correct it was much worse. I hope I have it now.

2010-09-28T06:34:43Z

Sorry for my last edit, the version before that had a little mistake and my attempt to correct it was much worse. I hope I have it now.

← Older revision		Revision as of 23:34, 27 September 2010
Line 30:		Line 30:

	Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.		Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

			Let I be the set of all <math>1\le i\le n-j</math> such that <math>a_i+a_{n-j+1}+\dots+a_n</math> is not in M. Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, I cannot be empty. Let x be the the greatest element of I.

	~~Since~~ <math>~~M \cap S_j</math> already uses up at least~~ j+1 ~~of the points in M, there must be at least one number~~		For each i in I, <math>a_i+a_{n-j+1}+\ldots+a_{n-1} \in S_j</math> must be a landmine, otherwise, we could safely reach <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> in j+1 steps by the induction hypothesis. Similarly, each
	~~<math>x</math> in <math>~~\{~~1,\dots,~~n-j\}</math> ~~(actually even at least two) such that~~ <math>~~a_x~~+a_{n-j+1}+\ldots+~~a_n~~</math> ~~is not a landmine~~.		<math>a_x+a_{n-j+1}+\ldots+a_n - a_m</math> where <math> m \in \{x, n-j+1,\dots,n\}</math> must be a landmine and we can find n distinct elements of M as follows:
	~~Then each~~ <math>a_x+a_{n-j+1}+\ldots+a_n - a_m</math> where <math> m \in \{x, n-j+1,\dots,n\}</math> must be a landmine and we can find n distinct elements of M as follows ~~(ordered by size)~~:		# For <math>1 \le i < x</math>, we have (x-1) numbers <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for i in I or <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> for i not in I (The former are in <math>S_j</math> and the latter bigger than the greatest element <math>a_{n-j+1}+\ldots+a_{n}</math> of <math>S_j</math>).
	# ~~All~~ (x-1) numbers <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for <math>1 \le i < x</math>		# All j numbers <math>a_x+a_{n-j+1}+\ldots+a_n - a_m</math> where <math> n-j+1 \le m \le n</math> (all in <math>S_j</math>)
	# All j numbers <math>a_x+a_{n-j+1}+\ldots+a_n - a_m</math> where <math> n-j+1 \le m \le n</math>		# The number <math>a_{n-j+1}+\ldots+a_n</math> (in <math>S_j</math>)
	# ~~All~~ (n-j-x) numbers <math>a_i+a_{n-j+2}+\ldots+a_{n}</math> for <math>x < i \le n-j</math>		# The are (n-j-x) numbers <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> for <math>x < i \le n-j</math> (these i are not in I and greater than all other numbers mentioned before)
	~~# The number <math>a_{n~~-j+1}+~~\ldots+a_n</math>~~
			Together, these are (x-1) + j + 1 + (n-j-x) = n elements of M, but M has only n-1 elements.

	So M contains at least n elements, a contradiction.		So M contains at least n elements, a contradiction.

Thomas.zeitlhoefler: In the previous version of proof 1 there is a mistake. Let n=8, k=3, biggest i in I = 3. Then you get the elements a1+a7+a8 and a5+a6+a8 which are not necessarily distinct.

2010-09-27T23:51:34Z

In the previous version of proof 1 there is a mistake. Let n=8, k=3, biggest i in I = 3. Then you get the elements a1+a7+a8 and a5+a6+a8 which are not necessarily distinct.

← Older revision		Revision as of 16:51, 27 September 2010
Line 31:		Line 31:
	Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.		Now suppose instead that <math>M \cap S_j</math> has cardinality at least j+1. Then, by Assumption A, we cannot pass <math>M \cap S_j</math> safely in j+1 or fewer steps. In particular, we cannot safely reach <math>a_i+a_{n-j+1}+\ldots+a_n</math> in j+1 steps for any <math>1 \leq i \leq n-j</math>.

	~~Let I~~ be ~~the set of all~~ <math>1 \~~leq i \leq~~ n-j</math> such that <math>~~a_i~~+a_{n-j+1}+\ldots+a_n</math> is not ~~in M~~. ~~Since~~ <math>M \~~cap S_j~~</math> ~~already uses up at least~~ j+1 of ~~the points in~~ M~~, I cannot be empty. For each i in I,~~ <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> ~~must lie in M, otherwise we could safely reach~~ <math>~~a_i~~+a_{n-j+1}+\ldots+a_n</math> in j+1 ~~steps by the induction hypothesis. Similarly, if i is the greatest element of I,~~ <math>a_i+a_{n-j+1}+\ldots+~~a_n - a_m~~</math> ~~must lie in M~~ for ~~any m equal to either~~ i or n-j~~+1,...,~~n-1~~. But this forces M to contain n distinct elements, a contradiction. Specifically, the n distinct elements are as follows:~~		Since <math>M \cap S_j</math> already uses up at least j+1 of the points in M, there must be at least one number
			<math>x</math> in <math>\{1,\dots,n-j\}</math> (actually even at least two) such that <math>a_x+a_{n-j+1}+\ldots+a_n</math> is not a landmine.
			Then each <math>a_x+a_{n-j+1}+\ldots+a_n - a_m</math> where <math> m \in \{x, n-j+1,\dots,n\}</math> must be a landmine and we can find n distinct elements of M as follows (ordered by size):
			# All (x-1) numbers <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for <math>1 \le i < x</math>
			# All j numbers <math>a_x+a_{n-j+1}+\ldots+a_n - a_m</math> where <math> n-j+1 \le m \le n</math>
			# All (n-j-x) numbers <math>a_i+a_{n-j+2}+\ldots+a_{n}</math> for <math>x < i \le n-j</math>
			# The number <math>a_{n-j+1}+\ldots+a_n</math>

	~~# <math>a_i+a_{~~n~~-j+1}+\ldots+a_{n}</math> for <math>i \notin I</math>;~~		So M contains at least n elements, a contradiction.
	~~# <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for <math>i \in I</math>; and~~
	~~# for the biggest <math>i \in I</math>~~, ~~the numbers <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math>~~.

	== Proof #2 ==		== Proof #2 ==

Neergard at 08:29, 23 August 2009

2009-08-23T08:29:13Z

← Older revision		Revision as of 01:29, 23 August 2009
Line 263:		Line 263:
	Which are the details behind the following claim near the end?		Which are the details behind the following claim near the end?
	"Then we can easily know set C will have at least n - k + m different values."		"Then we can easily know set C will have at least n - k + m different values."
	Also, how are we sure that all these n - k + m numbers are different from all the ~~p_i which are~~ blockers?		Also, how are we sure that all these n - k + m numbers are different from all the
			k - m blockers from p_1, ..., p_k?

	Kai Neergård		Kai Neergård

Neergard at 21:57, 22 August 2009

2009-08-22T21:57:47Z

← Older revision		Revision as of 14:57, 22 August 2009
Line 259:		Line 259:
	n -k + m + k -m = n blcokers, which contracdicts the condition.		n -k + m + k -m = n blcokers, which contracdicts the condition.
	(B) If No, so we can go further from one of m non-blockers, which contradicts k is the maximum assumption.		(B) If No, so we can go further from one of m non-blockers, which contradicts k is the maximum assumption.

			== Comment on Proof #6 ==
			Which are the details behind the following claim near the end?
			"Then we can easily know set C will have at least n - k + m different values."
			Also, how are we sure that all these n - k + m numbers are different from all the p_i which are blockers?

			Kai Neergård

Itempond.com: /* Proof #6 */

2009-08-01T04:57:05Z

Proof #6

← Older revision		Revision as of 21:57, 31 July 2009
Line 199:		Line 199:

	== Proof #6 ==		== Proof #6 ==
			The proof 5 doesn't seem correct. The first step is not qualified for induction:
			How can it make sure b_1,..., b_{n-2} < a_1 + ... + a_{n-1}?

	(Insert proof here)		(Insert proof here)

			By mathematical induction, needless to say about n = 2.
			Let's consider case n.

			Given a set B = {b_1, ..., b_{n-1}}, whose member is between 0 and A_1 + ... + A_n.

			A point in B is called "blocker" if it is a sum of some of A_1, ..., A_n (no duplicates).
			This kind of points will block the grasshopper.

			Assume grasshopper can jump to point A_1 + A_2 + ... + A_k (k >= 1) with maximum k
			(for convenience, we use A_1, ..., A_k. If not the case, we can always rename them).
			if k = n, then done.

			So, we can assume k < n.

			Without loss of generality, we assume A_{k+1} < A_{k+2} < ... < A_n

			Let's consider a group of points:

			A_2, A_3, ..., A_k, A_{k+1}; Let p_1 = A_2 + A_3 + ... + A_k + A_{k+1};
			A_1, A_3, ..., A_{k-1}, A_{k+1}; Let p_2 = A_1 + A_3 + .... + A_{k-1} + A_{k+1};
			...
			A_1, A_2, ..., A_{k_1}, A_{k+1}; Let p_k = A_1 + A_2 + .... + A_{k-1} + A_{k+1};
			A_1, A_2, ..., A_{k-1}, A_k; Let p_{k+1} = A_1 + A_2 + ... + A_{k-1} + A_k;

			Actually, they are k combination of {A_1, ...., A_k, A_{k+1}}, for example, when k = 3,
			the group will be:
			A_2, A_3, A_4;
			A_1, A_3, A_4;
			A_1, A_2, A_4;
			A_1, A_2, A_3;

			Notice that k is the maximum the grasshopper can go, so the following points are
			all blockers off the point p_(k+1):

			p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n

			which are n-k different blockers.

			Obviously, p_1, p_2, ..., p_k, p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n are mutually
			distinct and p_1, p_2, ..., p_k all smaller than p_{k+1} + A_i, where i >= k + 1.
			The total number of the above points is n. If p_i ( 1 <= i <=k) is not blocker,
			then there are at most k - 1 blockers smaller than p_i. By our induction, p_i can
			be reachable by the grasshopper.

			We define another set C = {p_{k+1} + A_{k+1}, ...., p_{k+1} + A_n}.
			This set will be expanded in the following way:

			If p_i is not a blocker (where 1 <= i <= k), then we add p_i + A_{k+2}, ..., p_i + A_n to set C.

			If there are m such p_i (non-blockers) from p_1, ..., p_k. Then we can easily know
			set C will have at least n - k + m different values.
			Can all these different values be blockers?
			(A) If Yes, we know there are k - m blockers from p_1, ..., p_k. In this case, we will have
			n -k + m + k -m = n blcokers, which contracdicts the condition.
			(B) If No, so we can go further from one of m non-blockers, which contradicts k is the maximum assumption.

Alex and Ecki: /* Proof #1 */

2009-07-29T16:00:00Z

Proof #1

← Older revision		Revision as of 09:00, 29 July 2009
Line 35:		Line 35:
	# <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> for <math>i \notin I</math>;		# <math>a_i+a_{n-j+1}+\ldots+a_{n}</math> for <math>i \notin I</math>;
	# <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for <math>i \in I</math>; and		# <math>a_i+a_{n-j+1}+\ldots+a_{n-1}</math> for <math>i \in I</math>; and
	# for the biggest <math>i \in I</math>, the numbers a_i+a_{n-j+1}+\ldots+a_n - a_m.		# for the biggest <math>i \in I</math>, the numbers <math>a_i+a_{n-j+1}+\ldots+a_n - a_m</math>.

	== Proof #2 ==		== Proof #2 ==

Alex and Ecki: /* Proof #5 */

2009-07-29T15:54:41Z

Proof #5

← Older revision		Revision as of 08:54, 29 July 2009
Line 185:		Line 185:

	== Proof #5 ==		== Proof #5 ==
			We order the steps as <math>a_1 < a_2 < \ldots < a_n</math> and the mines as <math>b_1 < b_2 < \ldots < b_{n-1}</math>.

	We remove the largest mine and the largest step ~~a_max~~. We ~~apply induction~~. Two things can happen we hit the largest mine or we reach the sum of all the a_i’s(target) minus the largest step a_max. If we hit the largest mine we swap the last step for the largest step and we skip over the largest mine then we just continue till we are done. If we go to the the sum of all the a_i’s except the largest step and it is not a mine we add one more step and we are done. If it is a mine and we replace the last step with a_max and we don’t land on a mine then we take one more step then we are done.		We remove the largest mine <math>b_{n-1}</math>and the largest step <math>a_n</math> and try to apply induction. We look at the sum <math>t':=\sum_{1\le i\le n-1} a_i</math>.
			Two things can happen:

	~~We have one case left where target – a_max is a mine and there~~ is ~~one or more mines greater than target – a_max call~~ the ~~number of these~~ mines f.		1.
	Then ~~what remains is case one~~ of the ~~dual proof which~~ we ~~solve as follows:~~		<math>t'</math> is not among the first n-2 mines. Then we use the induction hypothesis and get some ordering of the numbers. If we hit the largest mine <math>b_{n}</math> somehow with that ordering we swap the last step for the largest step <math>a_n</math> and skip over the largest mine. Then we just continue until we are done. If we do not hit <math>b_n</math>. we are done anyway.

	~~target-max a~~ is a mine and f is greater 0. ~~In that~~ case, out of the ~~target-a_i that are not max a~~ (n numbers), ~~at least n~~-~~f are not mined (when taken as a first jump). Consider the n double jumps (target–max~~ a_i ~~!= max a~~, ~~target~~-~~max a target). At least~~ n-~~f of those are not mined on first jump. The number of~~ mines in (~~0 target~~ -~~max~~ a) is ~~the number of mines (n) less f less the one for target -max~~ a~~, yielding~~ n-f-1 ~~which is less than n~~-~~f. Thus by counting argument~~, ~~at least one of the double jumps does not hit a mine on both jumps~~. ~~This~~ double jump takes two jumps and jumps over ~~f+1 >=2~~ mines, yielding a problem with n-2 mines and n-1 remaining jumps, which is solved by induction.		2.
			<math>t'</math> is a mine and there is one or more mines greater than <math>t'</math>. Then what remains is case one of the dual proof which we solve as follows:

			Let <math>t:=\sum_{1\le i\le n} a_i</math>. Then out of the <math>2(n-1)</math> numbers <math>t-a_i,t-a_i-a_n,1\le i\le n-1</math> there are at most n-2 mines (because <math>t'=t-a_n</math> is a mine and not among those numbers). Therefore there is a <math> 1\le i\le n-1</math> such that <math>t-a_i,t-a_i-a_n</math> are no mines. The double jump <math>t-a_i-a_n,t-a_i,t</math> takes two jumps and jumps over at least two mines, yielding a problem with at most <math>n-3</math> mines and <math>n-2</math> remaining jumps, which is solved by induction.

	== Proof #6 ==		== Proof #6 ==

	(Insert proof here)		(Insert proof here)