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.

Filter by
Sorted by
Tagged with
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
1
vote
2answers
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$. ...
0
votes
1answer
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} ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
4
votes
0answers
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 ...
1
vote
1answer
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$...
2
votes
2answers
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 ...
7
votes
1answer
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 ...
2
votes
2answers
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. ...
1
vote
1answer
20 views

Least moving-overlapped subset of [1..n] that has the biggest natural density as possible.

Given a natural number n>1. I'd like to find a set $\phi = \{s_1,s_2, \cdots , s_m \} \subset \{1,2,\cdots , n \} $ with $m > 1$ that minimizes the following quantity: $$ S_{\phi} = \frac{\max_{k\...
2
votes
1answer
257 views

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 ...
0
votes
1answer
46 views

Link between two products

Could someone help me to solve this problem : Let's denote by $A_i$ the following product, $$ A_i = \prod_{\substack{k=1 \\ k\neq i}}^n (a_k - a_i) $$ Is there any link or simple formula between $...
8
votes
1answer
648 views

A question on Derangement Combinatorics

Six cards and six envelopes are numbered 1, 2, 3, 4, 5, 6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the ...
3
votes
1answer
53 views

Piecing together full density subsequences

A subset $A$ of $\mathbb{N}$ is said to be of full density if: $$\lim_{n\rightarrow \infty} \frac{|A\cap [1,n]|}{n}=1.$$ Suppose there exists a function $g:\mathbb{N}\rightarrow\mathbb{R}^{\geq 0}$, ...
3
votes
0answers
98 views

Convergence of integers by transformations

Let $x=(a,b)$, where $a,b$ are in $N$ Now we have the transformations: $$T_1(x) = (ka, b+1)$$ $$T_2(x) = (b,a)$$ where $k$ is in $N$. Where the order of choosing a transformation is not fixed. (E.g....
5
votes
4answers
296 views

When a set of consecutive numbers can be covered by differences between distinct integers?

I will start with an example. Suppose that I would like to cover the set $\{1,2,3\}$ by differences between three integers $m_1,\ m_2$ and $m_3$ in the following sense: $$ \{1,2,3\}=\{m_2-m_1,m_3-m_2,...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
7
votes
1answer
889 views

IMO 2015 warm up problem

I get this problem from IMO 2015 facebook page. Let $x_i$ be positive integers for $i=1,2,...,11$. If $x_i+x_{i+1}\geq 100$, $|x_i-x_{i+1}|\geq 20$ for $i=1,2,...,10$. And $x_{11}+x_{1}\geq 100$, $|x_{...
-2
votes
1answer
123 views

Integers Placed On A Circle

My problem is such: On a circle there are $9$ distinct positive integers aranced in such a way that the product of two non-adjacent numbers in the circle is a multiple of $n$ and the product of any ...
3
votes
1answer
24 views

Boundedness of $\gcd(|x-y|,|a_x-a_y|)$ in sequence

Let $a_1,a_2,\ldots$ be an infinite sequence of distinct positive integers, and let $n$ be a positive integer. Does there always exist integers $x,y$ such that $\gcd(|x-y|,|a_x-a_y|)>n$? When $a_x=...
25
votes
3answers
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 ...
1
vote
3answers
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$ "...
6
votes
2answers
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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 ...
3
votes
0answers
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 ...
1
vote
1answer
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 ...
13
votes
2answers
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 ...
13
votes
1answer
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$, ...
2
votes
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
59 views

Combinations problem with 2 contradicted answers!

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 $...
4
votes
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 ...
7
votes
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 \...
8
votes
1answer
330 views

Expectation of a Random Subset of the Roots of Unity.

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 ...
7
votes
0answers
310 views

Uses of Chevalley-Warning

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