If she asks for $f(2)$ (or any even $k$), won't she be directly able to tell the parity of $f(0)$? @below But isn't $f(k)$ an integer for every such $k$? @2below Oh, ok. My bad.

Dem0nfang wrote: If she asks for $f(2)$ (or any even $k$), won't she be directly able to tell the parity of $f(0)$? $f$ need not to be an integer coefficient polynomial. A simple example \[ f(x) = \frac{1}{2} x(x - 1) + 1 \]$f(2) = 2$ and $f(0) = 1$ while for \[ f(x) = x(x - 1) + 1 \]$f(2) = 3$ and $f(0) = 1$.

Dem0nfang wrote: If she asks for $f(2)$ (or any even $k$), won't she be directly able to tell the parity of $f(0)$? @below But isn't $f(k)$ an integer for every such $k$? An integer-valued polynomial is different from a polynomial with integer coefficients.

Let's find the answer if we replace $187$ with any positive integer $d$. USJL wrote: Alice and Bob are stuck in quarantine, so they decide to play a game. Bob will write down a polynomial $f(x)$ with the following properties: (a) for any integer $n$, $f(n)$ is an integer; (b) the degree of $f(x)$ is less than $d$. Alice knows that $f(x)$ satisfies (a) and (b), but she does not know $f(x)$. In every turn, Alice picks a number $k$ from the set $\{1,2,\ldots,d\}$, and Bob will tell Alice the value of $f(k)$. Find the smallest positive integer $N$ so that Alice always knows for sure the parity of $f(0)$ within $N$ turns. Lemma: $\mathbb{C}_{d-1}[X]$ is the $\mathbb{C}$-vector space of polynomials with complex coefficients of degree $< d$. Let $d \geq 1$. Given a polynomial $P \in \mathbb{C}_{d-1}[X]$, then $\sum_{k=0}^{d} (-1)^{d-k} {d \choose k } P(X+k)=0$.

Therefore, $\sum_{k=0}^{d} (-1)^{d-k} {d \choose k }P(k)=0$. Let $b=S_{2}(d)$, where $S_2$ is the sum of digits in base $2$. Using Kummer's theorem, we know that there are $2^{b}$ odd numbers among $\left ( {d \choose 0 }, ..., {d \choose d } \right )$. Let these numbers be $0=k_1 < ....<k_{2^b}=d$. Then $\sum_{i=1}^{2^b}P(k_i) \equiv 0 \pmod{2}$. Therefore, we only need to evaluate $P$ at $2^b - 1$ values to get the paritity of $P(0)$. Suppose Alice chooses $0<a_1<...<a_m \leq d$ where $m < 2^b - 1$, then $E=\{k_1, ..., k_{2^b} \} \setminus \{a_1, ..., a_m \}$ contains at least two elements (including $0$), therefore $P(0)$ can take any value modulo $2$. Finaly, the answer for $d=187$ is $63$.

Remark: The number $187$ is chosen because $18763$ is a pun on "starburst stream" in Chinese. We tried $d=87$ and $d=487$ which would give a better pun but they didn't work (.

cazanova19921 wrote: Let's find the answer if we replace $187$ with any positive integer $d$. USJL wrote: Alice and Bob are stuck in quarantine, so they decide to play a game. Bob will write down a polynomial $f(x)$ with the following properties: (a) for any integer $n$, $f(n)$ is an integer; (b) the degree of $f(x)$ is less than $d$. Alice knows that $f(x)$ satisfies (a) and (b), but she does not know $f(x)$. In every turn, Alice picks a number $k$ from the set $\{1,2,\ldots,d\}$, and Bob will tell Alice the value of $f(k)$. Find the smallest positive integer $N$ so that Alice always knows for sure the parity of $f(0)$ within $N$ turns. Lemma: $\mathbb{C}_{d-1}[X]$ is the $\mathbb{C}$-vector space of polynomials with complex coefficients of degree $< d$. Let $d \geq 1$. Given a polynomial $P \in \mathbb{C}_{d-1}[X]$, then $\sum_{k=0}^{d} (-1)^{d-k} {d \choose k } P(X+k)=0$.

Therefore, $\sum_{k=0}^{d} (-1)^{d-k} {d \choose k }P(k)=0$. Let $b=S_{2}(d)$, where $S_2$ is the sum of digits in base $2$. Using Kummer's theorem, we know that there are $2^{b}$ odd numbers among $\left ( {d \choose 0 }, ..., {d \choose d } \right )$. Let these numbers be $0=k_1 < ....<k_{2^b}=d$. Then $\sum_{i=1}^{2^b}P(k_i) \equiv 0 \pmod{2}$. Therefore, we only need to evaluate $P$ at $2^b - 1$ values to get the paritity of $P(0)$. Suppose Alice chooses $0<a_1<...<a_m \leq d$ where $m < 2^b - 1$, then $E=\{k_1, ..., k_{2^b} \} \setminus \{a_1, ..., a_m \}$ contains at least two elements (including $0$), therefore $P(0)$ can take any value modulo $2$. Finaly, the answer for $d=187$ is $63$. I believe that, by looking the questions "What is $f(k)$" as equations in $\mathbb{F} _2$ you concluded that the variable $P(0)$ could not be determined in less than 63 questions. May you elaborate on why is this enough? It may be the case that it is because we are working with linear equations, but how do we prove that we don't "lose information" when we are making this mod 2 reduction? EDIT: Just for clarification, I will give the following example: If we look at mod 2, $x^2+1=y^2$ has solutions $(0,1)$ and $(1,0)$. However, if $x,y$ are integers, we must have $(x,y)=(0,1)$ or $(0,-1)$ , hence $x \equiv 0 \mod 2$.

@above Isn't it this? cazanova19921 wrote: Suppose Alice chooses $0<a_1<...<a_m \leq d$ where $m < 2^b - 1$, then $E=\{k_1, ..., k_{2^b} \} \setminus \{a_1, ..., a_m \}$ contains at least two elements (including $0$), therefore $P(0)$ can take any value modulo $2$.

cazanova19921 wrote: Let $b=S_{2}(d)$, where $S_2$ is the sum of digits in base $2$. Using Kummer's theorem, we know that there are $2^b$ odd numbers among $\left ( {d \choose 0 }, ..., {d \choose d } \right )$. This is not a claim you can simply brush off. You must provide a proof of this statement. Each odd number corresponds to $k$ such that adding $d-k$ to $k$ does not produce any carries. If $d-k$ has any ones where $d$ has zeroes, there will be carries. Thus, $d-k$ must have zeroes where $d$ has zeroes, but can have a $1$ or $0$ in other positions for a total of $2^{S_2(d)}$ choices. cazanova19921 wrote: Suppose Alice chooses $0<a_1<...<a_m \leq d$ where $m < 2^b - 1$, then $E=\{k_1, ..., k_{2^b} \} \setminus \{a_1, ..., a_m \}$ contains at least two elements (including $0$), therefore $P(0)$ can take any value modulo $2$. You did not explain how to choose the parity of $P(0)$ freely after giving up the values of $P(a_1), \dots, P(a_m).$ Your argument only shows that the possibility of choosing $P(0)$ has not been ruled out by the finite difference constraint.

skrublord420 wrote: cazanova19921 wrote: Suppose Alice chooses $0<a_1<...<a_m \leq d$ where $m < 2^b - 1$, then $E=\{k_1, ..., k_{2^b} \} \setminus \{a_1, ..., a_m \}$ contains at least two elements (including $0$), therefore $P(0)$ can take any value modulo $2$. You did not explain how to choose the parity of $P(0)$ freely after giving up the values of $P(a_1), \dots, P(a_m).$ Your argument only shows that the possibility of choosing $P(0)$ has not been ruled out by the finite difference constraint. There is a linear equation that OP deduces, and that equation suffices to show the claim.

If $f(n)\in\mathbb Z(x)$ Alice knows only the value of $f(2)$ to be sure about the parity of $f(0). $ the only deduction Alice could get is that $f(x) $ has every rational coefficients. We could make a robust value of $N$ such that Alice could be sure about the parity of $f(0) $ after $N $ turns. Apply Lagrange interpolation with $f(x) $ be a polynomial and each values from $f(1)$ to $f(187) $ is an integer. $f(x)=\sum f(k)\prod_{k\ne i}\frac{(x-i)}{(k-i)} $ with $k,i $ in each sum satisfies $k,i=\{1,2,\hdots,187\},k\ne i$ Let $x=0$ $$f(0)=\sum f(k)\prod_{k\ne i}\frac {(0-i)}{(k-i)}\mapsto f(0)\equiv\binom{k}{187}f(k)\,(\star)$$We need to count all the even numbers in each binomial. $\binom {k}{187}=\frac {187!}{k!(187-k)!} $ to eliminate all the even summands in $(\star). $ Power of $2$ in $k!$ is $f(x)=\tfrac x2+\frac {x}{4}+\hdots$ $f(187)=\frac {187}{2}+\frac {187}{4}+\hdots+\frac {187}{128} $ Applying the inequality $x+y\le [x+y]$ Consider all the multiples of $128$ below $187$ for each $k\in [60,127];\left [\frac {k}{128}\right]+\left [\frac {187-k}{128}\right]<\left [\frac {187}{128}\right] $ So $f(k)+f(187-k)<f(187). $ For every other power of $2, $ we obtain total power in $f(k). $ $f(187-k)\le \text {the power value in}\,f(187)\implies\binom {k}{187} $ is even. Hence, exclude the range $[60,127] $ in the assessment of $f(0). $ For the multiple sets of $64, $ because $\frac {187}{64}=2. $ Enumerate all the multiples of $64$ in that range $[60,127] $ in previous case. For the multiple sets of $32$ Because $\left [\frac {187}{32}\right]=\left [\frac {160}{32}\right]=5,\left [\frac {187}{32}\right]=\left [\frac {155}{32}\right]+1$ we could exclude the range $[156,159]. $ Similarly for each power of $2\in\{4,8,16,32,64,168\} $ exclude the ranges $$[180,183];[172,175];[164,167];[156,159];[148,151];[140,143];[132,135];[60,127];[4,7];[12,15];[20,23];[28,31];[36,39];[44,47];[52,55]. $$Total number we need $\boxed {63} $

skrublord420 wrote: cazanova19921 wrote: Let $b=S_{2}(d)$, where $S_2$ is the sum of digits in base $2$. Using Kummer's theorem, we know that there are $2^b$ odd numbers among $\left ( {d \choose 0 }, ..., {d \choose d } \right )$. This is not a claim you can simply brush off. You must provide a proof of this statement. Each odd number corresponds to $k$ such that adding $d-k$ to $k$ does not produce any carries. If $d-k$ has any ones where $d$ has zeroes, there will be carries. Thus, $d-k$ must have zeroes where $d$ has zeroes, but can have a $1$ or $0$ in other positions for a total of $2^{S_2(d)}$ choices. Maybe Kummer's theorem is new to you, but it is used widely on this forum, without providing any proof. skrublord420 wrote: cazanova19921 wrote: Suppose Alice chooses $0<a_1<...<a_m \leq d$ where $m < 2^b - 1$, then $E=\{k_1, ..., k_{2^b} \} \setminus \{a_1, ..., a_m \}$ contains at least two elements (including $0$), therefore $P(0)$ can take any value modulo $2$. You did not explain how to choose the parity of $P(0)$ freely after giving up the values of $P(a_1), \dots, P(a_m).$ Your argument only shows that the possibility of choosing $P(0)$ has not been ruled out by the finite difference constraint. Isn't that obvious by Lagrange interpolation?