0
votes
0answers
70 views

Counting maximum moves

Given two arrays, each of size N denoted by A1,A2...AN and B1,B2...BN. Let us maintain two sets S1 and S2 which are empty initially. In one move ,Pick a pair of indexes (i, j) such that : ...
0
votes
2answers
350 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 ...
6
votes
1answer
46 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 ...
2
votes
1answer
67 views

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$.

Prove that a sequence of $11$ numbers always contains six numbers summing up to a multiple of $6$. This is a problem from a selection to IMO 2014. I like thinking about this problem, it is ...
2
votes
0answers
55 views

Prove the following : [duplicate]

Prove the following : $$ {{n}\choose{7}}-\left \lfloor{\frac{n}{7}}\right \rfloor $$ is divisible by 7.
0
votes
2answers
50 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?
1
vote
3answers
40 views

How to find exponent of a number in a combination?

How do I find the exponent of $7$ in $^{100}C_{50}$ that is, $\dfrac{100!}{(100-50)!\cdot 50!} =\dfrac{100!}{50!\cdot 50!}$, this question was out of the blue, and I haven't been able to find any ...
3
votes
2answers
65 views

Counting divisibility from 1 to 1000

Of the integers $1, 2, 3, ..., 1000$, how many are not divisible by $3$, $5$, or $7$? The way I went about this was $$\text{floor}(1000/3) + \text{floor}(1000/5) + ...
3
votes
2answers
144 views

Find the number of series

Find the number of series $(a_1,..., a_{2n})$ that have terms from ${\{0,...9\}}$ so that: $$ 11|\sum_{i=1}^{n}a_i-\sum_{i=n+1}^{2n}a_i $$ (this is not a homework) There is a similar problem ...
0
votes
0answers
75 views

How do you justify the PigeonHole principle?

I am working on the problem below and just have two questions pertaining to my answers. 1) Am I clearly and correctly justfying my answers, anything I can improve on or explain better? 2) Are my ...
0
votes
1answer
22 views

Number of positive $n$ s.t. $5|n^4 + 5n^2 + 9$

Find the total number of positive integers $n$ not more than $2013$ such that $n^4 + 5n^2 + 9$ is divisible by $5$. This problem was taken from Singapore Math Olympiad 2013, Open Section, First round. ...
1
vote
2answers
127 views

combinatorics and divisibilty

in how many ways we can form a $8$ digit numbers from $1,2,3,4,5$ with repetition allowed & divisible by $8$. MY APPROACH : to be divisible by 8 : last 3 digit of the no. must be divisible by 8 ...
2
votes
3answers
95 views

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$

Determine the largest 3-digit prime factor of ${2000 \choose 1000}$. I could not approach the problem at all. I have no idea how to try the problem. Please help.
1
vote
2answers
106 views

How many $7$ digits number can be made?

How many $7$ digits number can be made with $1,2,3,4,5,6,7$ so that they are divisible by $11$? (Repetition is not allowed.) I know the divisibility rule of $11$, so the main problem is counting.
0
votes
0answers
44 views

How to find gcd sum for some combination of numbers?

The problem is , Given an n-dimensional hyperrectangle length of each dimension is given. Now the value of each cell is the gcd of its co-ordinates. Now How do we find the sum of all cells ? I have ...
0
votes
1answer
70 views

How to calculate total number of combination having sum divisible by a given number.

I have following code.And i want to calculate value of ans. ...
4
votes
3answers
120 views

How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? " Here is my thinking: (200 Choose 0,1, and 2) are not multiples of 3 but every ...
1
vote
1answer
47 views

Pigeonhole question - divisibility by chosen number

This question should be solved with pigeonhole principle. Let $a,n \in \mathbb N$ such that $a$ is a number whose digits are only $3$'s and $0$'s, and $n$ is an unspecified natural number. Show that ...
2
votes
1answer
67 views

A problem relying on van der Waerden's theorem, and the existence of sums divisible by a given number $n$

Say we are given a sequence of integers $\{a_i\}_{i \in \mathbb{N}}$, as well as a pair of integers $n, m$. How can we show that there always exist positive integers $s, r$ such that the sums $a_s + ...
3
votes
2answers
79 views

Arithmetical proof of $\cfrac{1}{a+b}\binom{a+b}{a}$ is an integer when $(a,b)=1$

When $(a,b)=1$, $\cfrac{1}{a+b}\binom{a+b}{a}$ refers to the number of paths from one corner to its opposite corner of an $a\times b$ lattice that lies completely above (or below) the diagonal. ...
1
vote
1answer
101 views

Divisibility of multinomial by a prime number

What is the condition for divisibility of multinomial $ \dbinom {n}{x_1, x_2, \dots, x_k} $ by a prime $p$? Update: I tried to solve using a generalisation of Lucas Theorem by representing the $n$ ...
0
votes
1answer
69 views

Smallest n digit number that can divide a n digit number

Is there any simple way to find the smallest n digit number that can divide n digit number. For Example: Lets take a two digit number xx. I want to find the smallest two digit(yy) number that can ...
4
votes
3answers
118 views

Combinatorial interpretation of this number?

It is straightforward to show that if $m,n\in\mathbb{Z}$ and $m\geq n$, then $$m\mid \gcd(m, n)\binom{m}{n}.$$ I'm trying to find a combinatorial interpretation of this fact, but I can't seem to come ...
17
votes
4answers
369 views

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$ I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you ...
4
votes
2answers
80 views

Products in a Set

Let: $$S := \{1,2,3,\dots,1337\}$$ and let $n$ be the smallest positive integer such that the product of any $n$ distinct elements in $S$ is divisible by $1337$. What are the last three digits of ...
1
vote
1answer
75 views

Divisibility problem.

In line written squares of natural numbers from 1 to 2012. How many of these numbers have a remainder when divided by 17, which is divisible by 3?
4
votes
2answers
722 views

Trying to prove that $p$ prime divides $\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$

So I'm trying to prove that for any natural number $1\leq k<p$, that $p$ prime divides: $$\binom{p-1}{k} + \binom{p-2}{k-1} + \cdots +\binom{p-k}{1} + 1$$ Writing these choice functions in ...
3
votes
1answer
44 views

Can the coefficients of a given term in this family of power series have a common divisor?

Let $g_m(b)$ be the coefficient of $x^m$ the power series $$\dfrac{1}{1-x-bx^2}$$ (When $b=1$, this is just the generating function of Fibonacci numbers.) Of course, $g_m(b)$ depends on both $m$ and ...
2
votes
2answers
164 views

How do I accurately count the integers(1-1000) that are not divisible by 3,4,5,6?

I have the general algorithm here that my teacher gave us( see full at http://i.imgur.com/pbzQb.png) ) To count we just divide, correct? like - 1000/3 = 333 ? What is the sigma notation used ...
2
votes
2answers
275 views

Sum of Digits divided by 5 and 9?

Using the digits $0,1,2,3,4,5,6,7,8,9$, If five digit numbers is made without the repetition: How many numbers can be made? sum of all the even numbers? sum of all the odd numbers? How many numbers ...