0
votes
1answer
27 views

Count ways to sit men women in row of size K

Suppose we are given N men and M women.They are to sit in a row of size K such that no two women sit next to each other.What are the number of ways. Like if suppose their are 3 men and 2 women and ...
0
votes
1answer
59 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
0
votes
1answer
32 views

Counting points in/on cuboid

Given a cuboid that extend in x,y,z axis such that |x|≤N, |y|≤N, |z|≤N where N is given and can have value up to 10^9.Now a shooter is standing at origin (0,0,0).He need to shoot on any of the ...
3
votes
0answers
34 views

Generalization of small set/large set

A small set is a subset of the positive integers, such that the infinite sum of the reciprocals of the members of the set converges. Conversely, the sum of the reciprocals of a large set diverges. ...
1
vote
3answers
53 views

Rational numbers and periodic decimal representation

I'm trying to prove that a number is rational if and only if it has an eventually periodic decimal expansion. One part is simple; without loss of generality we consider $q=0.\overline{d_1\dots d_k},$ ...
1
vote
0answers
59 views

Integer partitions without rotated solutions?

I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of ...
0
votes
2answers
38 views

How many odd numbers are there with one or more even digits within a range?

Imagine you have a range [A,B], how could I know how many odd numbers with even digits are there in the range? Can't figure it out.
3
votes
1answer
81 views

How to prove a duality about partitions of numbers?

I found the following theorem, which I think should be correct but I do not know how to prove it: Consider the set containing sums $A=\lbrace\sum\limits_{i=-a}^a iX_i\rbrace$ where $X_i$ is a ...
0
votes
1answer
57 views

Number theoretical Application of the Pigeonhole Principle

I'm currently working through a paper related to my bachelors thesis and I'm stuck at a point where the author mentions the following result as "a standard application of the pigeonhole principle". ...
0
votes
0answers
275 views

Cleaning minimum tables

Moderator Note: This question is part of the Ongoing August Challenge 2014 CodeChef (problem page). This contest ends on 11 August 2014, and this question will remain locked (with current answers ...
0
votes
0answers
576 views

Count arrangment such that each person wear different tshirt

Few friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts ...
2
votes
2answers
33 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
1
vote
1answer
41 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 ...
6
votes
1answer
125 views

Can the product of $n$ factorials be $n$ factorial?

Are there any solutions to the equation $a_1!\cdot a_2!\cdots a_n!=n!$ with all variables being integers greater than or equal to $2$?
4
votes
1answer
86 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 ...
0
votes
1answer
56 views

Sort of Binomial Expansion

I was trying to find a general formula for expanding the product: $$\prod_{i=1}^k (a+ib)$$ where $a, b \in \mathbb{R}$. The first few expansions are as follows: $$\prod_{i=1}^1 (a+ib) = a + b$$ ...
1
vote
1answer
62 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: ...
0
votes
0answers
53 views

Sums with k dice

I have n dice, each with k sides, numbered from 1 to k inclusive. I want to find in how many ways I can get a sum of x using those dice. Doing some research, I found that what I am looking for is ...
-1
votes
1answer
180 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
0
votes
1answer
26 views

Linear Constraints Solution Existence

how can one decide if $$A*t\ge b$$ $A$ is a Matrix with integer Entries and $t$ is a Vector with integer Entries, $b$ is a fixed Vector with integer Entries exists?
2
votes
1answer
29 views

Number of Orbits of symmetric group acting on $(\mathbb{Z}/n)^{l}$

I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related ...
0
votes
1answer
159 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) ...
0
votes
0answers
50 views

a special function for count

Let be $f:(\mathbb{N} \setminus \left\{0,1 \right\})^2 \rightarrow \mathbb{N}$ function that $f(a,k)=\text{total numbers of }n \in \mathbb{N} \text{ that } \frac{a^n}{n^k} \le 1$ . My question is: ...
0
votes
3answers
2k views

Minimum moves to reach destination [closed]

Given that a person is standing at $(0,0)$ and initially look in direction of $X$-axis. Now he can walk only at right angle to previous move. Like if he has to go to $(3,3)$ then $6$ moves are ...
1
vote
1answer
78 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
2answers
365 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
5
votes
1answer
88 views

Binomial Congruence

How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ for positive integers m and n and p a prime greater than 5? I can do it for mod p^2 but Im stuck here.
6
votes
1answer
47 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{a_i : a_1,\dots,a_k \text{ is a good ...
0
votes
1answer
41 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
212 views

Count swap permutations

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

How many are possibilities to build count $n$ summing $k$ other counts?

I have got an integer $n$. I have to build it by summing $k$, not necessary, different integers. Is there any overall formula to count how many are possibilities to build count $n$ summing $k$ other ...
0
votes
0answers
42 views

Gosper summable

I'd like to know why the following is NOT gosper summable: $$\sum_{k\in \Bbb{Z}} \frac{p(k)}{\prod_{j=0}^{m-1}(k+a+j)}$$ where $m>0, m\in\Bbb{Z}$ and $p(k)$ is a polynomial of degree $k=m-1$.
2
votes
2answers
42 views

Calculating the product of 3 numbers in an iterative way

Let $x,y,z \in \mathbf{N}$ and imagine the following procedure : Initialize $sum = 0$ Choose randomly a number out $x,y,z$ and add to $sum$ the product of the two others, e.g. if $x$ had chosen we ...
0
votes
0answers
31 views

When is it easy to write down the Bhargava S-factorial?

In Manjul Bhargava's The Factorial Function and Generalizations he motivates a new type of factorial $n!_S$ using by generalizing three theorems: For $k, l \in \mathbb{Z}$, we have $k! \times l!$ ...
5
votes
1answer
66 views

Using Plancherel's Theorem to Prove the Gauss Sum

I'm interested in proving the following: Where $p$ is an odd prime and $z$ is a primitive $p$th root of unity, we let $Q(p)=\sum^{p−1}_{k=0}z^{k^2}$. Prove: $|Q(p)|=\sqrt{p}$. Specifically, I want ...
6
votes
2answers
216 views

A problem based on pigeonhole

Numbers 1 to 1994 are divided into 6 sets.Show that at least in one group there will be two numbers whose sum is also in that group ? We can prove that at least one group will contain more than 332 ...
3
votes
0answers
90 views

Sum of product partitions of divisors

Let $M(n)$ be the the set of the multiplicative partitions of $n$, and let $D(n)$ be the set of the sum of the multiplicative partitions of the divisors of $n$. eg $M(30)=\{\{30\},\{2,15\},\{3, ...
1
vote
1answer
37 views

Find the rule of a sequence

I have a sequence $\{x(n), n=0,1,2,\ldots\}$ as follows: $x(0) = 1$ $x(1) = 1- e^{-a}$ $x(2) = \dfrac 12(1 - 4e^{-a} + 3e^{-2a})$ $x(3) = \dfrac{1}{6}(1-12e^{-a}+27e^{-2a}-16e^{-3a}) $ $x(4) = ...
3
votes
2answers
62 views

A combinatorial proof of Euler's Criterion? $(\tfrac{a}{p})\equiv a^{\frac{p-1}{2}} \text{ mod p}$

Euler's criterion states that $ (\tfrac{a}{p}) \equiv a^{\frac{p-1}{2}} (\text{ mod }p \,) $, where $(\tfrac{a}{p})$ is the Legendre symbol. Here is one algebraic proof, since ...
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} / ...
3
votes
2answers
94 views

why generating function $A(z) = 1 + z + z^2 + \cdots$ can be denoted as $\frac{1}{1-z}$

It is easy to see that $1 + z + z^2 + \cdots$ is equal to $\frac{1}{1-z}$ when $1 > z > 0$ and for $z >= 1$, they are not equivalent. So I have thought $\frac{1}{1-z}$ is just a short for the ...
3
votes
1answer
36 views

Number of ways to color such that one color always leads

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes ...
1
vote
1answer
37 views

Number of unique products of two integers of bounded size

If $S,T$ are two sets of integers, define $S*T$ to be the set $S*T = \{st \mid s \in S, t \in T\}$. Let $[1,n]$ denote the set of integers in the range from $1$ to $n$, i.e., $[1,n] = ...
1
vote
0answers
35 views

Simplifying a sum- combinatorics

Hello fellow mathematicians, I have been working avidly as a high school project to prove Legendre's conjecture. The question below and the other questions I have posted are directly linked to a ...
5
votes
1answer
89 views

Number of zeros in Fibonacci sequences mod $p$

We know that Fibonacci sequences are periodic in mod $m$. For example, for $p\equiv \pm 1 \pmod 5$ and $\pm 2 \pmod 5$ the periods for Fibonacci sequences modulo $p$ divide $p-1$ and $2p+2$ ...
2
votes
1answer
86 views

Proof that $(6+\sqrt{37})^{999}$ has at least $999$ zeros after the decimal point

I want to show that the number $(6+\sqrt{37})^{999}$ has at least $999$ zeros after the decimal point. It seems that for $(6+\sqrt{37})^n$ that we have $n$ times $0$ for odd $n$ and $n$ times $9$ for ...
2
votes
2answers
43 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 ...
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
2answers
51 views

If a natural number $x$ is divisible by $3$

Is the sentence If a natural number $x$ is divisible by $3$ then, if it is not divisible by $3$ then it is divisible by $5$ true or false?