MathDB

Problem 4

Part of 2008 VJIMC

Problems(2)

6-coloring [n], set x+y+z=0 mod n and x,y,z have the same/different color

Source: VJIMC 2008 1.4

6/17/2021
The numbers of the set {1,2,…,n}\{1,2,\ldots,n\} are colored with 66 colors. Let S:={(x,y,z)∈{1,2,…,n}3:x+y+z≡0(modn) and x,y,z have the same color}S:=\{(x,y,z)\in\{1,2,\ldots,n\}^3:x+y+z\equiv0\pmod n\text{ and }x,y,z\text{ have the same color}\}and D:={(x,y,z)∈{1,2,…,n}3:x+y+z≡0(modn) and x,y,z have three different colors}.D:=\{(x,y,z)\in\{1,2,\ldots,n\}^3:x+y+z\equiv0\pmod n\text{ and }x,y,z\text{ have three different colors}\}.Prove that ∣D∣≤2∣S∣+n22.|D|\le2|S|+\frac{n^2}2.
combinatoricsinequalitiescombinatorial inequalityColoringnumber theory
game, probabilistically increasing capital

Source: VJIMC 2008 2.4

6/17/2021
We consider the following game for one person. The aim of the player is to reach a fixed capital C>2C>2. The player begins with capital 0<x0<C0<x_0<C. In each turn let xx be the player’s current capital. Define s(x)s(x) as follows: s(x):={xif x<1C−xif C−x<11otherwise.s(x):=\begin{cases}x&\text{if }x<1\\C-x&\text{if }C-x<1\\1&\text{otherwise.}\end{cases}Then a fair coin is tossed and the player’s capital either increases or decreases by s(x)s(x), each with probability 12\frac12. Find the probability that in a finite number of turns the player wins by reaching the capital CC.
combinatoricsgameprobabilitygambler ruinprobability gamesProbability Combinatorics