组合数学 (Fall 2023)/Problem Set 3: Difference between revisions
Jump to navigation
Jump to search
| Line 3: | Line 3: | ||
Solve the following two existence problems: | Solve the following two existence problems: | ||
* You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' | * You are given <math>n</math> integers <math>a_1,a_2,\dots,a_n</math>, such that for each <math> 1\leq i\leq n</math> it holds that <math>i-n\leq a_i\leq i-1</math>. Show that there exists a '''nonempty''' subsequence (not necessarily contiguous) of these integers, whose sum is equal to <math> 0 </math>. (Hint: Consider <math> b_i=a_i-i </math>) | ||
* You are given two '''multisets''' <math> A </math> and <math> B </math>, both with <math> n </math> integers from <math> 1 </math> to <math> n </math>. Show that there exists two '''nonempty''' subsets <math> A'\subseteq A </math> and <math> B'\subseteq B </math> with equal sum, i.e. <math>\sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y </math> | * You are given two '''multisets''' <math> A </math> and <math> B </math>, both with <math> n </math> integers from <math> 1 </math> to <math> n </math>. Show that there exists two '''nonempty''' subsets <math> A'\subseteq A </math> and <math> B'\subseteq B </math> with equal sum, i.e. <math>\sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y </math> (Hint: The term ``subset'' can be replaced by ``prefixes'' and the statement is still true) | ||
Revision as of 16:10, 8 May 2023
Problem 1
Solve the following two existence problems:
- You are given [math]\displaystyle{ n }[/math] integers [math]\displaystyle{ a_1,a_2,\dots,a_n }[/math], such that for each [math]\displaystyle{ 1\leq i\leq n }[/math] it holds that [math]\displaystyle{ i-n\leq a_i\leq i-1 }[/math]. Show that there exists a nonempty subsequence (not necessarily contiguous) of these integers, whose sum is equal to [math]\displaystyle{ 0 }[/math]. (Hint: Consider [math]\displaystyle{ b_i=a_i-i }[/math])
- You are given two multisets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], both with [math]\displaystyle{ n }[/math] integers from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ n }[/math]. Show that there exists two nonempty subsets [math]\displaystyle{ A'\subseteq A }[/math] and [math]\displaystyle{ B'\subseteq B }[/math] with equal sum, i.e. [math]\displaystyle{ \sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y }[/math] (Hint: The term ``subset can be replaced by ``prefixes and the statement is still true)