Articles of arithmetic combinatorics

Minimum Sum that cannot be obtained from the 1…n with some missing numbers

Given positive integers from $1$ to $N$ where $N$ can go upto $10^9$. Some $K$ integers from these given integers are missing. $K$ can be at max $10^5$ elements. I need to find the minimum sum that can’t be formed from remaining $N-K$ elements in an efficient way. Example; say we have $N=5$ it means […]

Number of non-negative solutions of an equation with restrictions

Q: Find the number of non-negative solutions of the equation $$r_1+r_2+r_3+\ldots +r_{2n+1}=R$$ when $0 \le r_i \le \min(N,R)$ and $0\le R\le (2n+1)N$. My Attempt: I tried the stars and bars method but it did not work properly. If the upper-bound for $r_i$ was not there, then the answer would have been $\binom{2n+1+R-1}{R}=\binom{2n+R}{R}$. But how do […]

Questions on Erdős–Ginzburg–Ziv theorem for primes and understanding related lemmas and their applications.

While trying to prove the prime case of Erdős–Ginzburg–Ziv theorem: Theorem: For every prime number $p$, in any set of $2p-1$ integers, the sum $p$ of them divisible by $p$. I came across with the following lemma: Lemma 1: If $p$ is a prime number and $A,B$ are subsets of $\mathbb{Z}_p$ with $\varnothing\neq A\neq \mathbb{Z}_p […]

Least Impossible Subset Sum

Given a set A which contains natural numbers from 1 to N. Also given another set B which contains p natural numbers between 1 to N. We have to find out the least sum of subset which is not possible in the set A–B One way to do so is to apply subset sum problem […]

How prove that there are $a,b,c$ such that $a \in A, b \in B, c \in C$ and $a,b,c$ (with approriate order) is a arithmetic sequence?

Let $N=\{ 1,2,3,…, 3n \}$ with $n$ is a positive integer and $A,B,C$ are three arbitrary sets such that $A \cup B \cup C = N, A \cap B = B \cap C = C \cap A = \varnothing, |A| = |B| = |C| = n $. How prove that there are $a,b,c$ such that […]