Intereting Posts

A subset whose sum of elements is divisible by $n$
On the proof: $\exp(A)\exp(B)=\exp(A+B)$ , where uses the hypothesis $AB=BA$?
Inequality for incomplete Gamma Function
Why is the permanent of interest for complexity theorists?
Testing whether a hypersurface is singular
Reference request: Clean proof of Fermat's last theorem for $n=3$.
How many ways $12$ persons may be divided into three groups of $4$ persons each?
Shortest and most elementary proof that the product of an $n$-column and an $n$-row has determinant $0$
Are there Kirby diagrams for manifolds with boundaries?
How can the Gödel sentence be Pi_1
Is there a measurable set $A$ such that $m(A \cap B) = \frac12 m(B)$ for every open set $B$?
Good math puzzle books
Help to understand the proof of $ \lim \limits_{x\to 0^+} f \left(\frac{1}{x}\right)=\lim \limits_{x\to \infty}f(x)$
Does a monotone function on an arbitrary subset of $\mathbb R$ always have at most countable number of discontinuity?
Is there an Inverse Gamma $\Gamma^{-1} (z) $ function?

Let $v_1=(x_1,y_1),…,v_n=(x_n,y_n)$ be $n$ two dimensional vectors where each $x_i$ and each $y_i$ is an integer whose absolute value does not exceed $2^{n/2}/(100 \sqrt{n})$. Show that there are two disjoint sets $I,J \subset \{ 1,2,…,n\}\ $ such that $ \ \ \sum \limits_{i \in I} v_i = \sum \limits_{j \in J} v_j$

I tried to use the fact that $Pr[X>0] \leq \mathbb{E}[X] \ $ where $X$ is a non negative random variable. In particular I defined $X= \sum \limits_{j \in J} v_i – \sum \limits_{i \in I} v_i$. $\ \ $ But I am not sure about choosing $I,J$ in the right way. Any help on this would be much appreciate.

- Race Problem counting
- Expand $\binom{xy}{n}$ in terms of $\binom{x}{k}$'s and $\binom{y}{k}$'s
- How many ways are there to shake hands?
- Combinations of 6 students among 20, at least one male
- Number of Derangements of the word BOTTLE
- Partitioning $\{1,\cdots,k\}$ into $p$ subsets with equal sums

- Frog on a 3 by 3 matrix
- Number of ways to split a list into consecutive parts
- Prove a combinatoric sum
- Find prob. that only select red balls from $n$ (red+blue) balls
- Is this casino promotion exploitable?
- Prove that determinant of a matrix (with polynomial entries) is non-zero
- Ways to have exactly $n$ nominees out of $2n$ voters
- How many sequences of $n$ tosses of a coin that do not contain two consecutive heads have tails as the first toss?
- combinatorics: The pigeonhole principle
- Traveling salesman problem: a worst case scenario

I remind you, this book is totally systematic, a question from chapter 4 will be solved using the second moment method:

Define the random variables: $\epsilon_i=Ber(\frac1 2)$

Define a random variable $X=\sum_{i=1}^n\epsilon _i v_i$ and compute the mean of each coordinate:

$$\mu_x =\frac1 2 \sum_{i\leq n}x_i\space,\space \mu_y =\frac1 2 \sum_{i\leq n}y_i$$

compute the variances:

$$\sigma_x^2 =\frac1 4 \sum_{i\leq n}x^2_i\space,\space \sigma_y^2 =\frac1 4 \sum_{i\leq n}y^2_i$$

Both of the are bounded by $\frac{2^n}{40000}$. By Chebyshev, we get for any $\lambda$:

$$Pr[|X_x − \mu_x| \geq \frac{λ · 2^{n/2}}{200}] ≤ λ^{−2}$$

$$Pr[|X_y − \mu_y| \geq \frac{λ · 2^{n/2}}{200}] ≤ λ^{−2}$$

The probability that both are false is at least $1 − 2λ^{

−2}$

. In the box delineated by these

two inequalities there are at most $λ^

2 2^

n/10000$ lattice points, so if every value of $ X $ occurs at

most once,

$$(1-2\lambda^{-2})2^n\leq \frac{\lambda^2 2^n}{10000}$$

since there are $2^n$

total values of $X$. Picking $λ = 2$ is enough to see a contradiction. Thus

X takes some vector value twice, i.e. there exist distinct subsets $I, J \subseteq [1, n] $ for which

$$\sum_Iv_i=\sum_Jv_j$$

Removing the intersection $I \cap J$ from both sets we still have equal sums, as desired.

- A determinant coming out from the computation of a volume form
- What is the best book to learn probability?
- To find the range of $\sqrt{x-1} + \sqrt{5-x}$
- Real projective space $\mathbb{R}P^1$ is diffeomorphic to $S^1$?
- Primitive binary necklaces
- Uniform Convergence Implies $L^2$ Convergence and $L^2$ Convergence Implies $L^1$ Convergence
- Lines in the plane and recurrence relation
- Why is $\sin(d\Phi) = d\Phi$ where $d\Phi$ is very small?
- Why square units?
- $\DeclareMathOperator{\tr}{tr}\tr(A)=\tr(A^{2})= \ldots = \tr(A^{n})=0$ implies $A$ is nilpotent
- Riesz's Lemma for $l^\infty$ and $\alpha = 1$
- What does it mean to be an irreducible polynomial over a field? (need clarification on the definition)
- Homomorphism and normal subgroups
- How prove this $\displaystyle\lim_{n\to \infty}\frac{n}{\ln{(\ln{n}})}\left(1-a_{n}-\frac{n}{\ln{n}}\right)=-1$
- Why are the last two digits of a perfect square never both odd?