组合数学 (Fall 2023)/Problem Set 3

From TCS Wiki
Revision as of 15:58, 8 May 2023 by Roundgod (talk | contribs) (Created page with "== Problem 1 == 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 subset of these integers, whose sum is equal to <math> 0 </math>.")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 subset of these integers, whose sum is equal to [math]\displaystyle{ 0 }[/math].
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2023)/Problem_Set_3&oldid=11125"