1
vote
1answer
20 views

Distinct elements in the Union and Intersection of A and B

Take a set $x$ with $10$ distinct elements. Rule: Everytime you have two subsets, $A$ and $B,$ you also have $A\cup B$ and $A \cap B.$ What is the maximum number of subsets you can have such ...
1
vote
1answer
80 views

Divide N Hot dogs among M persons

There are N hot dogs and M people and we need to divide the hot dogs equally. Now we need to calculate the minimum number of cuts required to distribute the hot dogs equally. In order to divide the ...
1
vote
1answer
48 views

Count ways to form isosceles triangles

Their are N persons sitting on a table with N vertices.We need to count the number of isosceles triangles formed such that each vertex of the triangle is a vertex of the table and all persons seating ...
4
votes
1answer
52 views

A combinatorial conjecture

I'm trying to prove the following conjecture. Conjecture. Let $p \equiv -1\!\pmod{6}$ be a prime, and let $a,b > p$ be integers with $p \nmid ab(a+b)$. Then $$ \sum_{r=0}^{p-3} ...
1
vote
3answers
73 views

$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}?$ [duplicate]

How do I show that for $n \geq 0$, $$\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}?$$ I know that $\sum_{k=0}^n \binom{n}{k} = 2^n$, but does this really tell me anything? Thanks.
1
vote
1answer
45 views

How many solutions does the equation $2i+j+3k=l$ have in nonnegative integers?

Let $i,j,k$ be nonnegative integers and $l$ be a positive integer. How many solutions does the equation $2i+j+3k=l$ have? For low enough $l$, I can easily find the number of solutions, but is there ...
1
vote
1answer
66 views

Count ways to reach Nth row

Given a N*M grid I need to reach last row with following operations : ...
3
votes
2answers
66 views

partitions and their generating functions and Partitions of n

A partition of an integer, n, is one way of writing n as the sum of positive integers where the order of the addends (terms being added) does not matter. p(n, k) = number of partitions of n with k ...
0
votes
2answers
59 views

Making 24 with given number N

Initially we have a sequence of n integers: 1, 2, ..., n. In a single step, we can pick two of them, let's denote them a and b, erase them from the sequence, and append to the sequence either a + b, ...
1
vote
0answers
37 views

Count the strings with n0 K zeroes together

Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1. Now , the problem is we need to count the number of ways to fill these ...
2
votes
6answers
96 views

Show that ${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$ [duplicate]

Show $${n \choose 1} + {n \choose 3} +\cdots = {n \choose 0} + {n \choose 2}+\cdots$$ A hint is given to consider the expansion $(x-y)^n$ However, when I plug in a number for $n$, I don't get an ...
0
votes
1answer
23 views

Cardinality of the set $A=\left\{\frac{z_x}{z_y}: 1\le z_x \le N_x \text{ and } 1\le z_y \le N_y \right\}$

Cardinality of the set $A=\left\{\frac{z_x}{z_y}: 1\le z_x \le N_x \text{ and } 1\le z_y \le N_y \right\}$ where $z_x,z_y \in \mathbb{Z}$. Basically, the question is how many different fraction can ...
2
votes
2answers
40 views

Square grid , sum of elements

I am trying to solve the following problem : Find all the positive integers $n$ and $k$ such that it is possible to write integers in an $n \times n$ grid so that the sum of all elements in the grid ...
2
votes
1answer
57 views

Count ways to make total coin value [closed]

For any non-negative integer K, suppose we have exactly two coins of value 2^K (i.e., two to the power of K). Now we are given a long N. We need to find the number of different ways we can represent ...
3
votes
0answers
48 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
0
votes
0answers
37 views

Sum of digits of numbers in a range

Given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N we can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... ...
0
votes
1answer
35 views

Value of an iterated sum

I am interested in the number of function evaluations required to numerically evaluate an iterated integral of the form $$ \int_0^t \int_{t_1}^t \cdots \int_{t_{n-1}}^t f(t_1,\ldots,t_n) dt_n\cdots ...
3
votes
4answers
337 views

A consequence of Wilson's Theorem

By Wilson's Theorem we know that $$(p-1)! \equiv -1 \mod p.$$ A consequence of this is apparently $$(p-(k+1))!k! \equiv (-1)^{k+1} \mod p$$ where $0 \leq k \leq p-1$. I was told to think of it like ...
1
vote
4answers
47 views

Subsets of divisors

How many subsets of the set of divisors of $72$ (including the empty set) contain only composite numbers? For example, $\{8,9\}$ and $\{4,8,12\}$ are two such sets. I know $72$ is $2^3\cdot 3^2$, so ...
1
vote
1answer
46 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
4
votes
1answer
90 views

Permutation Partition Counting

Consider the number $n!$ for some integer $n$ In how many ways can $n!$ be expressed as $$a_1!a_2!\cdots a_n!$$ for a string of smaller integers $a_1 \cdots a_n$ Let us declare this function as ...
3
votes
3answers
55 views

Counting the factors of $2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$

Let $n = 2^4 \cdot 3^5 \cdot 4^6 \cdot 6^7$. How many natural-number factors does $n$ have? I'm not quite sure how to go about solving this problem; there seems to be a lot of overcounting involved.
1
vote
1answer
68 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
6
votes
4answers
74 views

$k$-th number in $N \times M$ Table

Given an array $A$ , where $A[i][j] = i\times j$ and $1 \leq i \leq N, 1 \leq j \leq M$ , then what is the best way to find the $k$-th number in this array , if we order them into a single array in ...
5
votes
1answer
120 views

Combinations mod $n$ property

So after some "fooling around" I came across this property in Pascal's triangle (which seems to repeat, and makes a lot of sense): $\begin{pmatrix} n \\ k \end{pmatrix} \mod n = \begin{cases} n ...
7
votes
0answers
134 views

Infinite sum involving $q$-adic representations of whole numbers and $q$-factorial numbers

Let $q \in \mathbb{N}_{\geq 2}$. For $n \in \mathbb{N}_0$, let $$\mathrm{fac}_q(n) := \prod_{i=1}^n (1+q+\dots+q^{i-1}) = \prod_{i=1}^n \frac{q^i-1}{q-1}$$ be the $q$-factorial of $n$. In particular, ...
0
votes
1answer
169 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
-1
votes
2answers
205 views

Count the whistles

Sports Teacher gathered all the players in his garden and ordered them to line up. After the whistle all players should change the order in which they stand. Teacher gave all the students numbers ...
1
vote
1answer
82 views

Count pairs with odd XOR

Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd. Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
0
votes
0answers
58 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
0
votes
1answer
44 views

Game of coins with two players

Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color. Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, ...
1
vote
1answer
77 views

How to calculate the number of lattice points in the interior and on the boundary of these figures with vertices as lattice points?

We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers. Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and ...
-2
votes
1answer
32 views

Counting problems

(a) (f) and (g) are ones im having issues with. Not all.
0
votes
1answer
44 views

Minimum AND operation on subset

Given an array of size N . Let's create all the subsets of this array which contain at least 2 elements. Now, operate AND over the elements of each subset, and store the results in a new array. I ...
2
votes
0answers
222 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
0
votes
0answers
41 views

A sum of powers of binomials

For $n$ and $k$ non-negative integers, let $$F(n,k) = \sum_{i=0}^{n}\binom{n}{i}^k.$$ For example, $F(n,0)=n+1$, $F(n,1)=2^n$ and $F(n,2)=\binom{2n}{n}$. Does there exist a general formula for ...
2
votes
1answer
48 views

Question on numbers modulo $(n+1)!$

I just noticed the following surprising 'fact' (it holds at least for low values of n): Pick any number k < $(n+1)!$ Consider the n products $ki$ with $1 \le i \le n$, i.e. $k, 2k, ... nk$ modulo ...
2
votes
3answers
88 views

Very elementary number theory and combinatorics books.

I know the basics of logic, sets, relations and the like, so studying intros to abstract algebra and real analysis is not that hard. That said, I have a deficiency when it comes to elementary number ...
2
votes
0answers
201 views

How to distribute 5-digit numbers in 5x5 matrices

I have 98000 5-digit numbers, from 00001 to 98000. I need to distribute these 98000 numbers in 14000 5x5 matrices. A matrix cell must contain only a digit from 0 to 9. Each matrix must receive 7 ...
0
votes
0answers
14 views

Question about the poly-Euler preprint

I'm looking over the preprint on poly-Euler numbers, and I think there might be a typographical error on the third line because $j=0$ leads to a discontinuity. Could somebody explain the substation ...
3
votes
1answer
85 views

Number of ways to express $N$ as a sum of consecutive integers

We can write $9$ as $9=4+5=2+3+4$. So the question is , Is there a integer $N$ which can be written as a sum of $1990$ consecutive positive integers, and which can be written as a sum of (More that ...
0
votes
1answer
46 views

number of ways in which the board can be restored to a winning configuration

A game in which there are n*n blocks which can be filled with numbers from 0 to n-1 in some arbitrary way. The rule of the game is that the board should be filled in such a way that the sum of each ...
0
votes
1answer
45 views

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd.

To prove that ${2+i \choose i}\equiv k \mod n$ is not possible that $k=0,1,\ldots,n-1 \forall i\ge 0$ and $i \in \mathbb{Z}$ and $n$ is odd. This is a problem from ISI 2014 written test in a little ...
2
votes
0answers
35 views

Given any integers $a,b,c$ and any prime $p$ not a divisor of $ab$, prove that $ax^2+by^2\equiv c\pmod{p}$ is always solvable.

The fact that there are $\dfrac{p+1}{2}$ quadratic residues seem to me to help solving the question, but I don't know how to go on from that point. Could you give me any hint?
2
votes
1answer
84 views

Going through all Bit Strings with no 11 in it (no consecutive 1s)

My question is very simple: How can i (efficiently) go through all Bitstrings which don't contain two consecutive 1s? So for instance, all Bitstrings of length 3 with no consecutive 1s are: 000, 001, ...
1
vote
1answer
33 views

Polynomial that is surjective $\mod n$ for all $n$?

I was curious about an existence of the following polynomial $f(x) \in \mathbb{Z}[x]$ and $f(x) \not = x$ such that given any $n \in \mathbb{N}$, $f: \mathbb{Z} / n\mathbb{Z} \rightarrow \mathbb{Z} / ...
2
votes
2answers
44 views

Formula for the number of solutions of the congruence equation $xy-wz=0$ over $\mathbb{Z}_p$?

The equation $xy-wz=0$ has 10 solutions over $\mathbb{Z}_2$ and 33 solutions over $\mathbb{Z}_3$ (e.g. $x=y=2 \land w=z=1$ is one of the solutions). Is there any formula for the number of solutions ...
0
votes
0answers
34 views

Number theory digit sum [duplicate]

How many natural numbers less than $10^8$ are there, with sum of digits equal to $7$? My friend told me it is coefficient of $x^7$ in $\frac{(x^{10} - 1)}{(x-1)^8}$ How did he get this result? Can ...
2
votes
1answer
42 views

In how many ways can a number be factorized over the field $\mathbb{Z}_p$ into two numbers?

For example, over the field $\mathbb{Z}_5$, we can factor number 4 into two numbers in three different ways, i.e. 4=4$\times$1, 4=2$\times$2, and 4=3$\times$3. I am looking for a general formula of ...
0
votes
0answers
18 views

Find cardinality of the largest subset defined by some condition

Let $A = \left\{1,2,3,\dots,2^n\right\}$. Find p, such that $p = \mathop{\max\vphantom{p}}_{A'\subset\ A}\left|A'\right|$ where subsets $A'$ of $A$ satisfy such condition: $x=2y \implies x,y \not\in ...