The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [arithmetic-combinatorics]

Arithmetic combinatorics is the study of combinatorial estimates associated with arithmetic operations. It lies in the intersection of harmonic analysis, combinatorics, ergodic theory, and number theory. This tag is for questions related to arithmetic combinatorics.

41 questions
Filter by
Sorted by
Tagged with
30 views

Regarding the Erdos-Szemeredi Sum/Product Conjecture

Edit: The theorem that was proved is here: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szemer%C3%A9di_theorem , basically a statement that either there can be many unique elements in a sum matrix ...
118 views

Erdos conjecture on arithmetic progression

My motivation for this enquiry is due to interest on Erdos conjecture on arithmetic progression. (https://en.wikipedia.org/wiki/Erd%C5%91s_conjecture_on_arithmetic_progressions) Having come across ...
71 views

Minors of a particular matrix?

Take an $\frac{n(n-1)}2\times n$ matrix $M$ with $0/1$ entries each row distinct each row having two $1$s. Take an $\frac{n(n-1)}2\times \frac{n(n-1)}2$ matrix $N$ with $0/1$ entries each row ...
113 views

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 ...
84 views

Number of non-zero entries of self-convolution

Let $f(k)$ be a function on the integers with the properties $f(k)\geq 0$ $\forall k$ $f(k)\geq p$ for at least $t$ values of $k$ Let $g(k)=\sum_{k'} f(k')f(k-k')$ be the self-convolution of $f$. ...
76 views

∀n ∈ N, ∃w1, w2, . . . , wn ∈ A+ such that w = w1w2 . . . wn and C(w) = C(wi) ∀i ∈ {1, . . . , n}

A is a finite set of letters and A+ denotes the set of all finite length strings formed by letters in A, i.e. ∀w ∈ A+, w is a string, each letter in w belongs to A and len(w) ≥ 1. E.g.- If A = {a, b} ...
186 views

How many natural numbers below 1 million have their sum of digits equal to 18?

How many natural numbers below 1 million have their sum of digits equal to 18? One way to solve this would be to make all possible cases in which the digits of the no. add up to 18 and then permute ...
512 views

How many five-digit numbers can be formed using the digits 1-9 which have at least three identical digits?

How many five-digit nos. can be formed using the digits 1-9 having at least three identical digits? My attempt: Total no. of possible nos. with no restrictions $=9^5$ No. of numbers having two ...
70 views

A conjecture on partitions of $\{1,\ldots,n\}$ [closed]

Conjecture: Let $n$ $∈$ $N$. Then for each factor $m ≥ n$ of $n$($n + 1$)/$2$, one can partition the set $\{1, 2, 3, \ldots , n\}$ into disjoint subsets such that the sum of elements in each subset is ...
44 views

Representing a number as $a^2+db^2$ given $d$

Given integers $n$ and $d$, how can I find integers $a$ and $b$ (or show that they do not exist) such that $n=a^2+db^2$? If it helps, in my present application I know the factorizations of $n$ and $d$...
579 views

Sum and product of k real numbers > 0 is unique?

Can we prove that $\sum_{i=1}^k x_i$ and $\prod_{i=1}^k x_i$ is unique for $x_i \in R > 0$? I stated that conjecture to solve CS task, but I do not know how to prove it (or stop using it if it is ...
135 views

find the least natural number n such that if the set $\{1,2,…,n\}$ is arbitrarily divided into two nonintersecting subsets

Find the least natural number $n$ such that if the set $\{1,2,\dots,n\}$ is arbitrarily divided into two non intersecting subsets then one of the subsets contains three distinct numbers such that the ...
202 views

Combinatorics with a condition.

Jane is giving gifts to 3 sets of cousins who are brother-sister pairs. She gives the gifts one after the other to her 6 cousins on the condition that no brother receives a gift before his sister. ...
20 views

166 views

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 ...
248 views

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 ...
889 views

661 views

Arithmetic Progressions in slowly oscillating sequences

An infinite sequence ($a_0$, $a_1$, ...) is such that the absolute value of the difference between any 2 consecutive terms is equal to $1$. Is there a length-8 subsequence such that the terms are ...
283 views

this is a conjecture or a result? every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?

Writing a little better the previous question: is it true that if we let $a$ and $b$ be coprime integers, then the arithmetic progression : $a + bh: h\in {\mathbb Z}$, contains a sequence of $k$ "...
245 views

Number of sudokus with no consecutive arithmetic progression of length 3 in any row or column.

How many such Sudokus are there? Any reference to papers, books, articles or any insight into the problem will be greatly appreciated. I've tried several search engines, scholarly and not, with no ...
224 views

Circular variation with repetition

I would like to know formula for circular variation with repetition. What I mean is : You have round table with n-spots. On every spot there can be number from 1 to k. So for n = 4 and k = 3 ...
222 views

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 ...
188 views

Efficient way to count number of arithmetic progression on coloring of $\mathbb{N}$.

Consider a coloring of $\mathbb{N}$ with two colors. How many monochromatic arithmetic progressions of a fixed length $m$ (i.e. numbers of the form $a+nd$ are colored the same) are there in the subset ...
85 views

Parity of Partition Function

Let $T(n)$ denote the number of partitions of $n$ into parts not congruent to $3$ mod $6$. Deduce that $T(n)$ is also the number of partitions of $n$ in which odd parts appear at most twice (even ...
236 views

What are Green's almost primes?

In a general-audience talk, Ben Green explains his famous proof with Terence Tao as an application of Szemerédi's theorem, but placing the primes within a smaller set of almost-primes in which they ...
623 views

Narcissistic numbers in other bases

It is well known that $153$ is a narcissistic number; that is, it is equal to the sum of the cubes of its digits since $153=1^3+5^3+3^3$. Other bases have similar numbers. For example, in base $3$, ...
93 views

Numbers not of the form $x^2+My^2$

Why are there only 436 numbers not of the form $x^2+My^2$ for $x>0$, $y>1$ and $M>0$? This is A074885 from OEIS. The last number is 1875902. Can the following argument be fixed up? I ...
244 views

Combinatorics in finite cyclic groups

Discuss the following. I got a good platform to remove all me quarries from my mind by positing the problems like this. Thanks again for support. 1) Find the minimum elements must be selected from ...
59 views

If I have the digits from $0$ up till $9$: $0,1,2,3,\cdots,9$. How many 3-digit number can be made from these set of digits if the number is greater than $600$? My solution was as follows:There are $... 3answers 838 views Multiset Combination in Combinatorics I want to buy a$k$-combination of doughnuts, where$k$is any amount less than or equal to the total doughnuts available. At the bakery there are$n$different types of doughnuts but there are ... 2answers 242 views Given a list of$2^n$nonzero vectors in$GF(2^n)$, do some$2^{n-1}$of them sum to 0? Let$G=(\mathbb{Z/2Z})^n$written additively,$n>1$. (you can think of it as$\mathbb{F}_{2^n}$but I didn't find that useful... yet) Let$v_i$be nonzero elements of$G$for$i \in \{1 \dots 2^n \...
Let $p$ be a prime. If $1_A(x)$ denotes the indicator function of the set $A\subset\mathbb{Z}/p\mathbb{Z}$ and $$\hat{1}_A(t):=\frac{1}{p}\sum_{n=1}^p 1_A(n)e^{2\pi i \frac{nt}{p}}$$ denotes the ...
In the recent IMC 2011, the last problem of the 1st day (no. 5, the hardest of that day) was as follows: We have $4n-1$ vectors in $F_2^{2n-1}$: $\{v_i\}_{i=1}^{4n-1}$. The problem asks : Prove the ...