Where do you find the ISL Problems? I can't see them on the website.

akasht wrote: Where do you find the ISL Problems? I can't see them on the website. People who took TST have the SL packets with them.

Please make sure its the exact formulation from the shortlist.

Is the version with duck and geese or girls and boys? Anyways I suddenly realized this is just the car and gas station problem... how did no one solve it lol I even solved it if it only looks at the k people to the left.......

What is the gas station problem???

I have a solution to this problem that is too small to fit in the margins of this website

CANBANKAN wrote: Is the version with duck and geese or girls and boys? Anyways I suddenly realized this is just the car and gas station problem... how did no one solve it lol I even solved it if it only looks at the k people to the left....... I think, it's easier, had it been for $k$ people to the left/right. But, of course, it's subjective. In my opinion, the problem is not easy. Taking the right approach it becomes the gas stations problem, but it's far from obvious.

carefully wrote: What is the gas station problem??? https://www.cut-the-knot.org/proofs/GasStations.shtml CANBANKAN wrote: Is the version with duck and geese or girls and boys? The original version used boys and girls. I changed it to duck and geese for the American training camp, mostly for comedic value --- we included the flavor text "No rabbits/ducks/geese were harmed in the making of this test" on the test which featured this problem.

dgrozev wrote: CANBANKAN wrote: Is the version with duck and geese or girls and boys? Anyways I suddenly realized this is just the car and gas station problem... how did no one solve it lol I even solved it if it only looks at the k people to the left....... I think, it's easier, had it been for $k$ people to the left/right. But, of course, it's subjective. In my opinion, the problem is not easy. Taking the right approach it becomes the gas stations problem, but it's far from obvious. I agree. I spent 4 hours being stuck then when I saw the conversion I was like this is trivial.

I think this is the first solution that doesn't directly use the car and gas station problem. Anyways, here it is: Suppose otherwise. Call any girl $G_0$. WLOG we move in a clockwise direction. Let the $k$ people on her left be $l_0$. The first girl after these $k$ people is $G_1$. The $k$ people on her right are $r_1$, and the $k$ on her left are $l_1$. We keep assigning them like this until for some $i<j$, $G_i$ and $G_j$ are the same person. If $i !\neq0 $, then we simply set $G_0$ to be $G_i$. We then have the groups $l_0, r_1, l_1, \dots r_{j-1}, l_{j-1}, r_j$. But since $G_0 = G_j$, $r_j$ is simply $r_0$.(Note: draw everything in a line instead of a circle for easier visualization) We must have $l_x + r_x< k$, $ \forall x<j$ if the problem statement is not true. Suppose we went a total of $z$ rounds. We want to count the total number of boys and girls in these $z$ revolutions. Consider the people between $G_x$ and $G_{x+1}$ where $G_j = G_0$. If $l_x$ and $r_{x+1}$ have a non-zero overlap, there are at least as many boys as girls who are not counted twice between $G_x$ and $G_{x+1}$ (the leftmost few who were not counted twice MUST be all boys). The same is true if there is no overlap. Overall, we can write $$ B = 2nz \geq j(k+1) + p$$$$ G = 2(n+1)z \leq j(k-1) + q + 2j$$ where $p$ and $q$ are the numbers of boys and girls who were not double counted respectively. Since $p\geq q$ it's quite clear that on the right-hand sides $B \geq G$, which is a contradiction. The inequality actually seems quite weak.

Nice problem, but it's so tricky. Idk why it took me so long even though the solution looks very simple. Define the weight $w_i$ as $$w_i = \begin{cases} 1 & \text{if the }i\text{-th person is a girl, and} \\ -1 & \text{if the }i\text{-th person is a boy.}\end{cases}$$Also, extend the weight to positive integers by $w_i=w_{i-(2n+1)}$ for all $i>2n+1$. We also set some notations \begin{align*} s_i &= w_1+w_2+\dots + w_i,\text{ and} \\ t_i &= s_i + s_{i+k}. \end{align*}Notice that $s_{i+2n+1}=s_{i}+1$, so $t_i$ is unbounded. Among all $i$'s such that $t_i < t_{i+1}$, we pick the one that has smallest value $t_i$. If there are many, pick the one with the largest $i$ (possible since $t_{i+x(2n+1)} \geq 2x+t_i$, so $\lim_{i\to\infty} t_i=\infty$). We claim that the $(i+k+1)$-th person works. The proof is in three steps. Step 1: the $(i+k+1)$-th person is indeed a girl. We have $t_{i+1}-t_i = w_{i+k+1} + w_i$. Therefore, $w_{i+k+1}=1$, so the $(i+k+1)$-th person is indeed a girl. Step 2: $t_i < t_{i+k+1}$. Assume not (i.e., $t_i\geq t_{i+k+1}$), then consider the smallest $j\geq i+k+1$ such that $t_j < t_{j+1}$. Clearly, by minimality $t_{i+k+1} \geq t_{i+k+2} \geq \dots \geq t_j$, so $t_j\leq t_i$, a contradiction to what we chose. Step 3: conclude We have $$1\leq t_{i+k+1}-t_i = (s_{i+2k+1}-s_i) + \underbrace{(s_{i+k+1}-s_{i+k})}_{=1}$$implying that $s_{i+2k+1}>s_i$. Therefore, from the $(i+1)$-th person to the $(i+2k+1)$-th person, there are more girls than boys, so there are at least $k+1$ girls. This implies the conclusion.

Can someone share links of other problems with "gas station" flavour?

^^ see this https://artofproblemsolving.com/community/c6h2835400p25099717 ok here is another solution . Consider indices $\mod 2n+1$ I wil pair girls to boys in the following way . First a girl in $g$ is to be paired to a boy from $g+1,g+2,...,g+k$. Perform the following $k$ steps in reverse order first perform step$k$ then $k-1$ etc. In step $j$ if there is a girl at $g$ and a boy at $g+j$ both of which haven't been paired to anyone else (they are single) then pair them. So in step $j$ make all possible pairs of type $(g,g+j)$. In the end (after step $1$) due to the fact that there are $n+1$ girls and only $n$ boys there should be a girl that didn't get a pair in the process. This girl in position $s$ is the one we are looking for: Among $s+1,s+2,...,s+k$ there can only be girls or boys that have a pair , because if we suppose that $s+i$ is a boy that remained single then at step $i$ both $s$, $s+i$ were single so they should have been paired , a contradiction. Furthermore the pair of any boy in $s+1,s+2,...,s+k$ is not among the same set $s+1,...,s+k$ : suppose that a boy in $s+i$ got paired to a girl in $s+j$ for $1\le j\le i\le k$ , this pair was made in step $i-j$ which means that in step $i$ the boy was single so it should have been paired to girl in $s$ a contradiction. In particular this means that any boy $s+i$ in $s+1,...,s+k$ has a pair among $s+i-k,...,s-1$ that are neighboring positions to $s$, conclude that $s$ has at least $k$ girl neighbors.

Here is a bit different approach. Lemma. We have $ n, n\in\mathbb{N}$ numbers $ +1,0$ or $ -1$ written on a circle with positive total sum. Then there exists a number equal to $ +1,$ such that the sum of all its $ k, 0\le k\le n-1$ neighbors on the left and the number itself is positive. Proof. Enumerate the numbers anti-clockwise as $ x_1,x_2,\dots, x_n.$ Consider the sequence of their partial sums $$ \displaystyle s_m:=\sum_{i=1}^m x_i\,,\, m=1,2,\dots$$ where we assume $ a_{i+n}=a_i.$ Suppose, seeking contradiction, that the claim is not true. It means that for any $ x_m=1$ we have $ x_m+a_{m-1}+\dots+x_{m-k}\le 0$, that is, $ s_m\le s_{m-k-1}.$ Let's focus on the behavier of the sequence $ \big( s_m\big)_{m=1}^{\infty}$. At each next step, this sequence may jump one unit up, stay the same or decrease one unit. It converges to $ +\infty$ since $ \sum_{i=1}^n {x_i}>0.$ We also know that the following property holds (i) For any $ m\ge k+2,$ whenever $ s_m$ jumps up one unit (that's, when $ x_m=1$) we have $ s_m\le s_{m-k-1}.$ The point is that (i) rules out the possibility $ \displaystyle \lim_{m\to\infty} s_m=\infty.$ Indeed, if this were the case, then for any positive integer $ N$ larger than $ s_1,s_2,\dots,s_{k+2}$ there is a moment $ m$ such that $ s_m\ge N$ for the first time. But the property (i) prevents this to happen. This leads to contradiction, which completes the proof. $ \blacksquare$ Back to the problem. Let's place $ +1$ and $ -1$ instead of boys respectively girl. Denote the given numbers as $ a_1,a_2,\dots,a_n$ and let $ x_m:=a_m+a_{m-k-1}, m=1,2,\dots,n$ where $ a_{-i}$ means $ a_{n-i}$. Note that $ x_m$ can take values $ 2,0,-2$ and $ \sum_{i=1}^n x_i\ge 2$. By the Lemma, there exists $ x_m>0$ such that $ s:=x_m+x_{m+1}+\dots+x_{m+k}$ is positive. This means two things. First, $ x_m$ must be $ 2$ which means $ a_m=a_{m-k-1}=1$. Second, $ s$ is at least $ 2$ and then $$ \displaystyle \sum_{i=-k}^k a_{m+i}=s-a_{m-k-1}\ge 1.$$We are done. Remark. Some more comments on my blog.

Is the following correct? For each girl $g,$ denote by $f(g)$ the quantity of girls among its neighbors. Since for each girl, each of her neighbors has probability ${1}{/2}$ of being a girl, due to linearity of expectation, the expected value of $f(g)$ is $k,$ so done!

PHSH wrote: Is the following correct? For each girl $g,$ denote by $f(g)$ the quantity of girls among its neighbors. Since for each girl, each of her neighbors has probability ${1}{/2}$ of being a girl, due to linearity of expectation, the expected value of $f(g)$ is $k,$ so done! Wrong. The probability is $1/2$ when we assign students randomly. Certain configurations will achieve different expected values

IAmTheHazard wrote: PHSH wrote: Is the following correct? For each girl $g,$ denote by $f(g)$ the quantity of girls among its neighbors. Since for each girl, each of her neighbors has probability ${1}{/2}$ of being a girl, due to linearity of expectation, the expected value of $f(g)$ is $k,$ so done! Wrong. The probability is $1/2$ when we assign students randomly. Certain configurations will achieve different expected values Oh... I see! Thank you!

Numerate cyclically students counterclockwise as $1,2,...,2n+1.$ Let $a_i$ is $1$ if both $i,i-k$ are girls; $-1$ if they both are boys; $0$ if they are girl and boy. Since there are exactly $n+1$ girls we have $\sum a_i >0$, so by gas station theorem it follows that for some $j$ holds $a_j>0$ and $\sum_{t=0}^k b_{j+t}>0$. From first inequality $j$ is a girl, and from second she has at least $k$ girls among neighbors, so we are done.

title +1

zschess wrote: However, by the gas station problem, there exists $j$ s.t. $b_j>0$ and $b_j+...+b_{j+k}>0$. Did you mean Raney Theorem?

Going clockwise, assign each student a number from $0$ to $2k$ and let $a_i$ be $0$ if the student assigned $i$ is a boy, and $1$ if the student assigned is a girl. Furthermore, if $2k+1\mid i-j$ then let $a_i=a_j$. Let $b_i=a_i+a_{i+k}-1$. Note that since there are $k+1$ ones in the sequence $(a_0,a_1,\dots,a_{2k})$ and each term in that sequence appears twice in the expansion of $b_0+\dots+b_{2k}$, \[b_0+b_1+b_2+\dots+b_{2k}=1\]The zeroes don't matter. By the gas station problem, we can find $b_i=1$ and $b_{i-k}+\dots + b_{i}\ge 1$. In this manner, we have \[a_{i-k}+a_{i-k+1}+\dots + a_{i-1}+2a_i+a_{i+1}+\dots + a_{i+k}\ge k+2.\]Since $b_i=1$, $a_i=a_{i+k}=1$, \[a_{i-k}+a_{i-k+1}+\dots + a_{i-1}+a_{i+1}+\dots + a_{i+k}\ge k.\]Among the $2k$ neighbors of $a_i$, there are $k$ other girls.

welp didnt solve. after reading here i'll try to recreate the entire proof for memorization purposes Few things to notice: (1) Seems like Pigeonhole! (2) Direct global fails. So it makes sense to try an algebraic approach. Write girl is $+1$ and boy is $-1$, we want to use Raney's Lemma to solve this. I actually ended up figuring out the easier case where $2k$ people are in a single direction, and this doesn't actually require Raney's Lemma. I did think of combining $a_1$ and $a_{k+1}$ into a unit, probably just have bad intuition and didn't think much of it In any case, we need to have \[a_i>0\]\[a_{i-k}+\dots+a_{i+k}>0\]now write $b_i=a_{i-k}+a_i$. The point is that the sum (global) of $b_i$ is positive. If \[b_i>0\]\[b_i+\dots+b_{i+k}>0\]for some index $i$ we're done, since then $a_i=1$ and then we have \[a_{i-k}+\dots+a_{i+k}\ge 0\]hence at least as many girls as boys meaning there are $k+1$ girls total. Actually, there are two ways to finish from here. Proof 1: Notice that some index $i$ has $b_i+\dots+b_{i+k}>0$. If $b_i\le 0$ then we take $i\to i+1$ to get another positive value. Obviously we can't do this forever (it would imply $b_i\le 0$ always!) and that means $b_i>0$ at some point. (This is actually the same proof for $2k$ people on the right side, so in essence the original problem is reducible to this easier case, but requires setting numbers/algebra. I might need to remember that.) Proof 2 (Raney's Lemma): Take index $1$ and write \[s_j=\sum_{i=1}^{j} b_i\]with $s_0=0$, with indices of $b$ being periodic (while indices of $s$ are not). Take an index $j$ where $s_j$ is minimal and $j$ is maximal. I claim that for this $j$, all partial sums $b_j,b_j+b_{j+1},\dots$ are positive. This immediately solves the question. This isn't that hard, thankfully. It equates to proving \[s_{j-1+k}-s_{j-1}>0\]for all $k>1$. This is fine since either $j-1+k\le n$ and we are okay or $j-1+k=n+c$ and then $s_n-s_{j-1}+s_c>0$ is okay. Final note: Asking the question: "Why are there an equal number of neighbors on each side?" seems to help. It gave me the idea of trying the case where all neighbors were on one side. I might be missing something, but maybe this can be extended to $c$ on the left and $2k-c$ on the right. ($c=0$ and $c=k$ are the solved cases here.)

For each $1 \le i \le 2n+1$, define $a_i$ to be $1$ if $i$ is a girl and $-1$ if $i$ is a boy. Note that the sum of the $a_i$ is $1$. We want to show that there exists some $j$ such that \[ \mathcal{C}(i) := (\left(\sum_{j-k}^{j+k} a_i\right), a_j) \]has $x$-coordinate at least $1$ and $y$-coordinate equal to $1$. Now, define $b_i = a_i+a_{i+k}$, so that \[ \sum b_i = 2 \]and \[ \mathcal{C}(i) = (\left(\small\sum_{j-k}^j b_i\right), a_j). \]Thus suffices to show that for some index $j$, $b_j>0$ and $\small\sum_{j}^{j+k} b_i > 0$. However, this is well-known by the Gas Station problem, and we conclude.

Failed to solve this problem completely without being hinted to high heaven so here's some musings about motivation. Define $a_i$ as the indicator variable if the $i$th person is a girl. There's around $2 + \varepsilon$ distinct solutions which correspond to the two in the shortlist. The one in post #13 which consists of taking girls which are minimal in distance $> k $and summing to get a global contradiction. The one in the other posts which ends up defining $b_i = a_i + a_{i+k+1} - 1$ and then finishing with Raney's theorem. The solution at #17 ends up being roughly isomorphic to this. Any attempt at a naive probablistic / global solution, which fails and is only strong enough to get around half the desired bound. And here's some (after the fact) heuristics for why these solutions have the form Any solution to this must be pretty global in characteristic. Locally the behavior can be whatever, and for even $k$ there doesn't seem to be that nice of an equality case to reduce to. Any solution to this problem must eventually utilize the fact that the number of girls is larger than the number of boys. This follows because if we have odd $k$ and suppose that instead there were $n$ girls, then by an alternating configuration this ends up not being true. Notably, our first solution ends up using this in the final bound and our second solution uses this implicitly in Raney's theorem (though this is made more clear in #13, where you are actually pairing boys and girls). Both solutions roughly consider the summations $a_j + \dots + a_{j+k}$ and then win. The motivation for defining $b_i = a_{i} + a_{i+k+1} - 1$ can come from the fact that this turns our neighbors into a prefix sum. Then our corresponding motivations can be seen as follows If we assume the problem is false, every girl effectively has a neighborhood where we locally have less girls than we should. If we naively sum over girls with disjoint neighborhoods, then we can by php force around $\frac{n+1}{2(k-1)}$ disjoint runs of length $2k+1$ which have only $k$ girls. If we then consider naively trying to bound $\frac{\# b}{\# g}$, we get \[ \frac{2n+1}{\frac{n+1}{2(k-1)} \cdot (2k+1)} \]We are off by a factor of two and the solution is to strengthen the neighborhoods we consider, where girls only have distance $k$. After defining $b_i$, we can note that $b_1 + b_2 + \dots + b_{2n+1} = 1$. Then whenever $b_1 + \dots + b_t < 0$ this ends up being locally off in a sense. If we assume the problem is false, then $b_i + \dots + b_{i+k-1} < 0$ whenever $a_{i+k} = 1$. This also serves as the motivation for the first solution (where considering $b_i$ effectively does the strengthening by a factor of two). Through previous problems Raney's theorem is motivated, but we assume those aren't known. Then by graphing the prefix sums of $t_i \coloneq b_1 + \dots + b_i$, like comment #3 in the ISL shortlist but weaker, gives a version of Raney's by just taking a "local minimum" of the graph is also motivated, which would be contradicted whenever $b_i + \dots + b_{i+k-1} < 0$. Likewise, if you graph an atttempted counterexample to the problem, a raise $b_i$ is always followed by dropping down, which is related to both solutions and should also go to a finish.