# Tag Info

12

Consider the sequence of initial sums $S(0),S(1),\ldots,S(55)$ $$S(n)=\sum_{i=0}^na_i.$$ We have $$S(0)=0<S(1)<S(2)<\cdots<S(55)<95,$$ a sequence of 56 distinct integers in the interval $[0,94]$ of $95$ possibilities. Consider also the sequence of numbers $T(i)=S(i)-15$. There are 56 of those as well, all integers in the range $[-15,79]$. ...

11

This result is a special case of the famous EGZ or Erdős Ginzburg Ziv theorem, which states that any set of $2n-1$ integers, must have some subset of size $n$ whose sum is a multiple of $n$. Hence we can even throw out one of the 200 numbers; out of any 199 integers, some 100 must sum to a multiple of 100. You can find some lovely proofs of EGZ on ...

5

The EGZ theorem can be proved through the Cauchy-Davenport theorem: If $A$ and $B$ are subsets of $\mathbb{Z}_{/100\mathbb{Z}}$, $$|A+B| \geq \min(100,|A|+|B|-1)$$ or the Kneser's theorem: If $A,B$ are subsets of $\mathbb{Z}_{/100\mathbb{Z}}$ and $C$ is the restricted sumset $\{a+b:(a,b)\in A\times B, a\neq b\}$, then: $$|C| \geq ... 3 This is inelegant but... For this answer I will use the notation abc to refer to the number a*100 + b*10 + c where a,b,c are positive integers and b and c are between 0 and 9. I will occasionally use a(b+3)c or some such the indicate that b+3 is a single digit between 3 and 9 (presuming that b is a single digit between 0 and 6.) If we have 79 consecutive ... 3 Assuming the problem as it is currently written is written incorrectly and that the intended problem is the following: Given a set of 18 integers x_1,x_2,\dots,x_{18}, there will exist two integers x_i, x_j with 1\leq i<j\leq 18 such that x_i-x_j is divisible by 17. By the quotient remainder theorem, each of the integers x_i can be ... 3 This is essentially the same answer as already given, but from a slightly different point of view. Keep this trick, because it pops up all over the place, for instance in the proof of Chebyshev's Inequality. Instead of writing$$ S = \sum_{i=1}^{55} a_i $$where a_i \in \{1, 2, 3, \cdots\}, let N_k be the number of i \in \{1, \cdots, 55\} such that ... 3 The remainders when 2014 divides a number is given by the set$$S = \{0\} \bigcup \{1007\}\displaystyle\bigcup_{r=1}^{1006}\{r,2014-r\} = \bigcup_{k=0}^{1007} S_k$$where S is written as a union of 1008 mutually disjoint sets, where S_0=\{0\}, S_{1007} = \{1007\} and S_k = \{k,2014-k\}. Since there are 1009 numbers there exists two numbers say ... 3 For the 14 case, we show that there exist at least one number from set \{3,4,5,...,17\} is not obtainable and at least one number from set \{199,198,...,185\} is not obtainable. First consider the set \{3,4,5,...,17\}. Suppose all numbers in this set are obtainable. Then since 3 is obtainable, 1 and 2 are of different color. Then since 4 ... 3 I'm gonna explain it in my own style. The answer is 6(n-1)+1. Why? Clearly if we roll 6(n-1)+1 times, at least one of the six possible outcomes appears n times or more. Otherwise each outcome appears at most n-1 times. So in total there would be at most 6(n-1)rolls, a contradiction, since we rolled 6(n-1)+1 times. What do we conclude? If we ... 2 If you are to avoid a pair adding to 7 you can choose at most one member from each of the "pigeon-hole" sets \{1,6\}, \{2,5\}, \{3,4\}. But then you can only choose at most 3 numbers altogether..... 4 pigeons (choices.)...3 holes. 2 Hint: Think about the possible residues when dividing the integers by 2014 (i.e. 0 to 2013). When do two of these residues sum to 0? When do two of these residues lead to a difference of 0? How many different residues could you have? 2 Every non-negative integer is congruent to exactly one of 0,1, and 2 modulo 3, and every non-negative integer is congruent to exactly one of 0,1,2,3, and 4 modulo 5. Thus, there are 3 congruence classes modulo 3, and 5 congruence classes modulo 5. Now consider an ordered pair \langle a,b\rangle of non-negative integers: a can be ... 2 For x\in{\mathbb N} denote by r(x) the remainder modulo 13 of the decimal representation of x. If x is not divisible by 10 then r(x)=r(x-1)+1. If x is divisible by 10, but not by 100, then$$r(x)=r(x-1)-9+1=r(x-1)+5\ .\tag{1}$$If x is divisible by 100, things are more complicated; see below. Consider a run R:=[a\ ..\ a+78] of ... 1 Look at the smallest number a where the last digit is 0. There are at most nine numbers below a. Now a,a+1,...,a+9 gives you ten distinct modulo class of modulo 13. Now look at the second last digit of a, if it is less than or equal to 6 then we are good as a,a+1,...,a+9,a+19,a+29,a+39 gives you thirteen distinct remainders. If the second last ... 1 Let a_1<a_2<\cdots<a_{78}<a_{79} be the 79 consecutive numbers. Case 1: The digit in the hundreds place is the same for all numbers, i.e., \left\lfloor \dfrac{a_i}{100}\right\rfloor is the same for all numbers. Consider the smallest of the lot, which has 0 as its last digit, say a_k, where k \in \{1,2,\ldots,9\}. Note that ... 1 Set S has 1008 integer elements in the range [1,2014]. Take S' = \{2015-s \mid s \in S\}. This set S' also has 1008 elements. If we we look at S \cap S', this intersection must be nonempty (why? ^{\mathrm{[1]}}). Take some x \in (S \cap S'). For this x there is the element (2015-x) \in S. These values x and (2015-x) are two elements ... 1 You have the right idea, but a lot of the details are wrong. The largest number representable with n bits is 2^n-1, not 2^n. However, the smallest is 0, so there are 2^n different numbers representable with n bits. The smallest 2n are 0 through 2n-1; their sum is$$\frac{2n(2n-1)}2=n(2n-1)\;. The largest $2n$ are $2^n-1$ through ...

1

Every $A_i$ contains ${6\choose 3}$ 3-subsets. Therefore, in total, the $A_i$'s combined contain $13{6\choose 3}=260$ 3-subsets. We now count the number of possible different 3-subsets. In total, there are ${10\choose3}=120$ different possible 3-subsets. Thus, there are 260 3-subsets across the $A_i$'s, of which 120 are different. Now by the pigeonhole ...

1

If you take $50\times 99$ students ($99$ by state), you are sure to have at least $99$ students coming from each state. If you add $1$, whatever the state he comes from, you are sure there are $100$ students coming from the same state (and there is only one state from which $100$ students come).

1

If you enroll $50 \times 99$ students, your goal might still not be reached, because of the extreme case that you have an equal distribution of states up to this point, thus $99$ students from each of the $50$ states. If you enroll one more student he or she must complete one state fraction to at least $100$ students and you can be sure of your goal.

1

It is actually simple. Let the arrangement be $a_1,a_2,...,a_n$ where each $a_i$ correspond to the $i$th element in the circle clockwisely. Consider all the $k$ consecutive elements clockwisely, that is, the set of $(a_1,a_2,...,a_k),(a_2,a_3,...,a_k,a_{k+1}),(a_3,a_4,...,a_{k+2})...(a_{n-k+1},a_{n-k+2},...,a_n)...(a_n,a_1,a_2,...,a_{k-1})$. There are ...

Only top voted, non community-wiki answers of a minimum length are eligible