Intereting Posts

Proof of the square root inequality $2\sqrt{n+1}-2\sqrt{n}<\frac{1}{\sqrt{n}}<2\sqrt{n}-2\sqrt{n-1}$
Proof of transitivity in Hilbert Style
Proving an affine set's equivalence to the solution set of $Ax=b$
What is the least value of $k$ for which $B^k = I$?
Computation of the hom-set of a comodule over a coalgebra: $Ext_{E(x)}(k, E(x)) = P(y)$.
Let $f$ be a bounded measurable function on $E$. Show that there are sequences of simple functions converging uniformly on $E$.
Does infinite tetration of negative numbers converge for any value other than -1?
Spectrum of the right shift operator on $\ell^2({\bf Z})$
Plotting graphs using numerical/mathematica method
Is there a cubic spline interpolation with minimal curvature?
Does there exist non-compact metric space $X$ such that , any continuous function from $X$ to any Hausdorff space is a closed map ?
Solve differential equation $f'(z) = e^{-2} (f(z/e))^2$
Preservation of Limit by Hom: Naturality Question.
Results that were widely believed to be false but were later shown to be true
How to express the whole part $\lfloor x \rfloor$ as analytical function or Taylor/Fourier series?

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.

- Tiling of regular polygon by rhombuses
- Variance of the sums of all combinations of a set of numbers
- How this operation is called?
- Find a simple formula for $\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+…+\binom{n}{n-1}\binom{n}{n}$
- In the card game Set, what's the probability of a Set existing in n cards?
- Combinatorial proof of $\sum_{k=0}^n k \cdot k! = (n+1)! -1$

- Counting number of $k$-sequences
- Proof Check: Number of elements of $\mathbb{F}_{p^{n}}$ of the form $a^{p}-a$ for some $a \in \mathbb{F}_{p^{n}}$.
- Is the Law of Large Numbers empirically proven?
- Combinatorial Proof
- How to prove that a connected graph with $|V| -1= |E|$ is a tree?
- Finding the number of solutions to an equation?
- Expected Value of a Continuous Random Variable
- Three points on a circle
- Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$ (Dixon's identity)
- Coloring of an $1\times n$ board using 4 colors?

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.

- General formula for the higher order derivatives of composition with exponential function
- Iterations with matrices over simple fields approximating solutions for more complicated fields.
- Multiplicative norm on $\mathbb{R}$.
- how to find the remainder when a polynomial $p(x)$ is divided my another polynomial $q(x)$
- How to write \mathcal letters by hand?
- How to prove Greatest Common Divisor using Bézout's Lemma
- Prove that $=$
- Prove of inequality under a Hilbert space.
- Confused on a proof that $\langle X,1-Y\rangle$ is not principal in $\mathbb{Q}/\langle 1-X^2-Y^2\rangle$
- For all square matrices $A$ and $B$ of the same size, it is true that $(A+B)^2 = A^2 + 2AB + B^2$?
- Let $X$ be the number of aces and $Y$ be the number of spades. Show that $X$, $Y$ are uncorrelated.
- limit without L'Hôpitale rule or infinity series
- Real definition of “countable set”
- How to prove that $ = $ given $H \le G$?
- Is a proof still valid if only the writer understands it?