Daniel writes over a board, from top to down, a list of positive integer numbers less or equal to 10. Next to each number of Daniel's list, Martin writes the number of times exists this number into the Daniel's list making a list with the same length. If we read the Martin's list from down to top, we get the same list of numbers that Daniel wrote from top to down. Find the greatest length of the Daniel's list can have.
Problem
Source: Spanish Communities
Tags: combinatorics proposed, combinatorics
24.05.2006 06:14
The answer is 39. we first show the list must be similar, then we prove that there must be only one odd number, and because we're searching for the largest number, we have that the numbers are <= 10 so we consider that the odd number is 9 wich lead us to the sum: 2+4+6+8+10+9 = 39 1)suposse daniel's list's first number is x and martin's is x+y, wich means there are x+y x+y's in martin's lists and it means that in daniel's list's also according to the fact that they must have the same terms, but daniel's last must be x+y and martin's x, this means there are x x+y wich lead us to a contradiction. 2) because the list is simetrical, there must be only one odd number wich may be put in the center of the list and between separating different pairs also. we use 9 so we can reach the largest amount of numbers as possible. 3) the arrangement is like this: 2 9 4 4 9 6 6 6 9 8 8 8 8 9 10 10 10 10 10 9 10 10 10 10 10 9 8 8 8 8 9 6 6 6 9 4 4 9 2
18.09.2010 21:51
@rafaelguedez Your Proof of part 1) wasnt very convincing. to show you why, let me give the following argument - im rewriting the case which you have taken - let daniels list = $D$ Martins list = $M$ let $D_i$ and $M_i$ reresent the ith element of each list suppose daniel's list's first number is $D_1 = x$ and martin's is $M_1 = x+y$, wich means there are $x+y$ $x$'s. but for each $D_i = x$ we know that $M_i = x+y$ hence there must be AT LEAST $(x+y)$ number of $i$ for which $M_i = x+y$ Also, since i have assumed that they are not equal hence $y \neq0$ let $D_n$ and $M_n$ be the last elements of respective lists. from condition of equaity of reverse of $M$ to $D$ we have $M_n = D_1 = x$ and $D_n = M_1 = x+y$ $\implies$ number of $(x+y)'s$ in Daniels list $=x$ since lists are indentical if one is inverted then number of each element in each list must be equal hence, number of $(x+y)'s$ in Martins list $=x$ thus from our previous condition we have $x > x+y \implies y < 0$ you havent really shown that this is impossible ill post the rectification a little later. if you are not convinced by my argument, feel free to discuss. i always love a little discussion.ill let u try till then
11.03.2011 04:53
My argument goes as follows: If some integer $k$ is on David's list, then it is also on Martin's list. This means that another (or maybe the same one) integer $k'$ occurs $k$ times on David's list. So then, the maximum is the sum of the distinct integers on the list. i.e. $1+2+3+...+10=55$. And this is the answer. Note that a simple one of these list is David's list: $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ... ,10$ With Martin's being: $10, 10, 10, 10, 10, 10, 10, 10, 10, 10,..., 1$ Where each $k$ occurs $k$ times.