Please reply whether the Answer is " 15050"

Mahtarp wrote: Please reply whether the Answer is " 15050" It's not

No the answer in 14950

No "14949"

And its final

"Observation is the key" Let's see the answer for where the rooms capacity are 1,2,3. Then the answer should be 2+3 =5. No matter how you fill the room either the room with capacity one , will be fully occupied or not Case 1: If its fully occupied. Then the no.of guest remaining will be 4, and now no matter how you arrange it there will be one space remaining in 2 or 3.And You shift guest from room 1 to room 2 or 3. Case 2: The 2^nd is easy, as the room is empty. The key is that the room with minimum capacity should be empty. So in our question the answer is "102+103+....+200" And answer is exactly 14949

Hey there , I guess if you leave one room empty , then the VIP guest would have his room , which is a special form , but the question is saying that no matter how rooms are filled , so i guess your answer could be wrong !!! If you are convinced , say so that i tell you my solution .

so owner can only one move ?

My solution: Let rooms with capacities $101,102\ldots,200$ denote $a_{101},\cdots,a_{200}$ and in $a_{101}$ live 101-$l_1$, in $a_{102}$ 102-$l_2$ people and so on. and $x$=max $(l_{101},l_{102}\ldots,l_{200})$ for to find maximum of n he can achieve his goal we will find minimum of n he can not achieve his goal. Then $101$-$l_1$ $\ge {x+1}$, $102$-$l_2$ $\ge{x+1}$ (1) ... because if $101$-$l_1$ <${x+1}$ he can achieve his goal ( just look $a_{101} and $$a_{j}$$ where $$l_{j}$ = $x$ ).n=$101$-$l_1$+...+$200$-$l_{100}$=$15050$-($l_1$+...$l_{100}$) so to find min of n we will find max of S ( S=$l_1$+...$l_{100}$ ). let's denote with nop(k) =$l_{k-100}$ from (1) we have $nop(101)\leq100$-$x$, $nop(102)\leq101$-$x$ ...$nop($2x$) \leq2x$-(${x+1}$);$nop(2x+1)\leq x$ ,$nop(2x+2) \leq x$ ...$nop(200)\leq x$ (because x is max of $l_{i}$) so $$S \leq 100(2x-100)+(2x-100)(2x-99)/2-(x+1)(2x-100)+(200-2x)x =-2x^2+299x-4950$$and this function achieves his maximum when $x=75$ on interval [1,100] so $S\leq6225$ then minimum of N that he can not achieve his goal $101$-$l_1$+...+$200$-$l_{100}$=101+102+...+200-$S \geq15050$-6225=8825 so maximum of N he can achieve his goal is $8825-1=8824$

The answer is $\boxed{8824}$. Define $a_{101},a_{102},\ldots,a_{200}$ such that $a_i$ represents the number of people in the room with capacity $i$. Observe that the owner's goal can be satisfied if and only if there exist $i<j$ such that $a_i+a_j\leq j$, in which case the owner can move the guests from room $i$ to room $j$. Defining a function $f:\{102,102,\ldots,200\} \to \mathbb{N}$ such that $f(k)=\min\{a_{101},a_{102},\ldots,a_{i-1}\}$, the condition becomes equivalent to existing $j \neq 101$ (since if $j=101$ then there is no $i<j$) such that $a_j+f(j)\leq j$. Call some choice of $(a_{101},a_{102},\ldots,a_{200})$ where $0 \leq a_i \leq i$ for all $101 \leq i \leq 200$ sparse if such a $j$ exists, and crowded otherwise, and define the sum of such a tuple as $\sum_{i=101}^{200} a_i$. We wish to find the greatest $n$ such that every such tuple with sum $n$ is sparse. First, to show that $8825$ fails, using the notation shown above let $a_{101}=a_{102}=\ldots=a_{151}=76$ and let $a_k=k-75$ for $51 \leq k \leq 100$. This clearly satisfies $a_j+f(j)>j$ for all $j$, since $f(j)=76$ and therefore $a_j+f(j)=j+1$. This also implies that all $n \geq 8825$ fail too. Now I will show that every tuple with sum $8824$ is sparse. I will first prove that if we have $a_i>a_{i+1}$ for some $i$ and $(a_{101},a_{102},\ldots,a_i,a_{i+1},\ldots,a_{200})$ is crowded, then $(a_{101},a_{102},\ldots,a_{i+1},a_i,\ldots,a_{200})$ must be crowded too. Observe that swapping $a_i$ and $a_{i+1}$ does not change the value of $j+f(j)$ if either $j<i$ or $j>i+1$, hence we only have to show that in this case the following inequalities hold: $$a_{i+1}+\min\{a_{101},a_{102},\ldots,a_{i-1}\}>i,\qquad (1)$$$$a_{i}+\min\{a_{101},a_{102},\ldots,a_{i-1},a_{i+1}\}>i+1,\qquad (2)$$given that the following inequality (from the fact that the original tuple is crowded) holds: $$a_{i+1}+\min\{a_{101},a_{102},\ldots,a_{i-1},a_i\}=a_{i+1}+f(i+1)>i+1,\qquad (3)$$Since $f(i+1)=\min\{a_{101},a_{102},\ldots,a_{i-1},a_{i}\}>\min\{a_{101},a_{102},\ldots,a_{i-1}\}$ and $i+1>i$, from $(3)$ we have that $(1)$ holds. Also, note that: $$\min{a_{101},a_{102},\ldots,a_{i-1},a_i\}=\min\{f(i),a_i\} \text{ and } \min\{a_{101},a_{102}},\ldots,a_{i-1},a_{i+1}\}=\min\{f(i),a_{i+1}\}.$$Note we must always have $\min\{f(i),a_i\} \geq \min\{f(i),a_{i+1}\}$ since $a_i>a_{i+1}$, so $(2)$ also follows from $(3)$ as $a_i>a_{i+1}$. This implies the desired claim. Note that the contrapositive of the claim holds so if $(a_{101},a_{102},\ldots,a_i,a_{i+1},\ldots,a_{200})$ is sparse for $a_i<a_{i+1}$, then $(a_{101},a_{102},\ldots,a_{i+1},a_i,\ldots,a_{200})$ i sparse as well. Since any tuple can be reached by applying such swaps from a tuple where $a_i\leq a_{i+1}$ for all $i$, it suffice to check that for $n=8824$ any tuple that satisfies $a_i\leq a_{i+1}$ for all $i$. Call such tuples increasing. It is clear that for any $i \in \{102,103,\ldots,200\}$, if a tuple is increasing then $f(i)=a_{101}$. Hence we have to show that $a_{101}+a_j\leq j$ for some $102 \leq j \leq 200$. Suppose the contrary, so $a_{101}+a_j>j \implies a_j\geq j+1-a_{101}$ for all $102 \leq j \leq 200$. But since the tuple is increasing, we also need $a_j\geq a_{101}$. Combining these gives: $$a_j\geq \max\{j+1-a_{101},a_{101}\}.$$Observe that $\max\{j+1-a_{101},a_{101}\}=a_{101}$ if and only if $j+1-a_{101}\leq a_{101} \implies j \leq 2a_{101}-1$. Hence we have the inequalities $$a_{102}\geq a_{101},a_{103}\geq a_{101},\ldots,a_{2a_{101}-1}\geq a_{101},$$and: $$a_{2a_{101}}\geq a_{101}+1,\ldots,a_{200} \geq 201-a_{101}.$$Letting $a_{101}=c$ and adding these up (as well as $a_{101}=c$), it follows that the sum of the tuple must be at least: $$\underbrace{c+c+\ldots+c}_{2c-101~c\text{'s}}+(c+1)+\cdots+(201-c)=c(2c-101)+101(201-2c)=2c^2-303c+20301.$$We can easily check that over the positive integers, this quadratic attains a minimum value at $c=76$, at which its value is $8825$, hence the sum of such a tuple must be at least $8825$. This implies that every tuple with sum $8824$ is sparse, as desired. $\blacksquare$ Remark: This problem is actually quite fun, much more so than this writeup makes it appear!

Answer is $\boxed{8824}$. Let $M = n+1$. Let $a_i$ denote number of people in $i$-th room (which has capacity $i+100$). Further assume a VIP cannot be entertained, i.e. $$ a_i + a_j > \max(100 + i, 100 + j) ~~ \forall ~ i \ne j \qquad \qquad (\spadesuit)$$Then $$ M = a_1 + \cdots + a_{100} $$and we want to minimize $M$. Claim: We may assume $a_1 \le a_2 \le \cdots \le a_{100}$. Proof: If $a_i > a_j$ but $i < j$, then we interchange $a_i , a_j$. Note $(\spadesuit)$ is still satisfied: \begin{align*} a_i + a_j &> \max(100 + i, 100 + j) \\ a_k + a_i &> a_k + a_j > \max(100 + k ,100 + j) \\ a_k + a_j &> \max(100 + k, 100 + j) \ge \max(100 + k ,100 + i) \end{align*}This proves our Claim. $\square$ Assume $a_1 \le a_2 \le \cdots \le a_{100}$. Now if $a_1 < a_2$, we then change $(a_1,a_{100}) \to (a_1 + 1, a_{100} - 1)$ .This might possibly make $a_{99} > a_{100}$, but only important thing is that $(\spadesuit)$ is still satisfied, and we would apply our Claim again to ensure $a_{99} \le a_{100}$. We keep doing this until $a_1 = a_2$. Let $a_1 = a_2 = k$. Then $$ 2k = a_1 + a_2 > \max(1 + 100, 2 + 100) = 102 \implies k \ge 53$$Note $M \le 10001$ because of $$a_1 = \cdots = a_{99} = 100 ~,~ a_{100} = 101 $$So we may assume $k \le 100$ (this isn't required actually, but at least this makes our solution more natural looking). Now for each $1 \le i \le 100$ we have $$ a_i \ge k ~~,~~ a_i \ge i + 100 - k + 1 $$Conversely, if both the above conditions are true then it isn't hard to see required conditions are indeed satisfied. Write $k = 50 + r$ with $2 \le r \le 50$. Now it isn't hard to see $M$ is minimized when $$ a_1 = \cdots = a_{2r-1} = k = 50+r ~~,~~ a_i = i + 100 - k + 1 = i + 101 - (50 + r) = i + 51 - r ~~ \forall ~ 2r \le i \le 100 $$Then $M$ equals, \begin{align*} M &= \sum_{i=1}^{2r-1} a_i + \sum_{i=2r}^{100} a_i = \sum_{i=1}^{2r-1} (50 + r) + \sum_{i=2r}^{100} (i + 51 - r) = (2r-1)(50 + r) + (101 - 2r)(101) \\ &= 99r + 2r^2 - 50 + 101^2 - 202r = 2r^2 - 103r + 10051 \end{align*}This is minimized for $r=26$, which gives $$ M = 26(52 - 103) + 10051 = 10051 - 26(51) = 10000 - 25 \cdot 51 = 10000 - 1275 = 8825 $$

Mahtarp wrote: "Observation is the key" Let's see the answer for where the rooms capacity are 1,2,3. Then the answer should be 2+3 =5. No matter how you fill the room either the room with capacity one , will be fully occupied or not Case 1: If its fully occupied. Then the no.of guest remaining will be 4, and now no matter how you arrange it there will be one space remaining in 2 or 3.And You shift guest from room 1 to room 2 or 3. Case 2: The 2^nd is easy, as the room is empty. The key is that the room with minimum capacity should be empty. So in our question the answer is "102+103+....+200" And answer is exactly 14949 No