Problem 711

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
mdean
Posts: 165
Joined: Tue Aug 02, 2011 2:05 am

Problem 711

Am I missing something here? Let's say n=1. Oscar writes "10". Eric can't write any number without exceeding 2. There is one 1. Oscar wins. Yet in the problem statement, Eric guarantees a win.

LilStalker
Posts: 73
Joined: Thu Nov 03, 2016 4:32 pm

Re: Problem 711

Same here. The number a player can choose is probably limited with n. Not sure though.

brob26
Posts: 5
Joined: Thu Nov 22, 2018 3:48 am

Re: Problem 711

"First, they agree on a positive integer n, and they begin by writing its binary representation on a blackboard."

So for n = 1, they start by writing "1". Then it's Oscar's turn, but his only option is to write another "1", leaving an even number of 1s on the board.

mdean
Posts: 165
Joined: Tue Aug 02, 2011 2:05 am

Re: Problem 711

Got it. That's the part I was missing. Thanks.

DewayneGunter
Posts: 5
Joined: Tue Apr 21, 2020 9:32 pm

Re: Problem 711

Are the values in the example already mod 10^9 + 7?

DJohn
Posts: 63
Joined: Sat Oct 11, 2008 12:24 pm

Re: Problem 711

The value given for S(1234) is. The value for S(12) isn't (it's using = instead of $\equiv$). Although in this case S(12) is much less than 1000000007, so it doesn't make any difference.

It's common for programmers to see mod only as an operator, because that's the way the concept is expressed in programming languages. In that case we'd say S(1234) % 1000000007 = 690421393. Or, with more words, S(1234) modulo 1000000007 is 690421393.

In mathematics the it's usually done differently, and more generally. Saying $a \equiv b$ is saying that a and b are equivalent, for some kind of equivalence. The parenthetical (mod 1000000007) tells us what that equivalence is: values are considered equivalent if they differ by a multiple of 1000000007. We could just as correctly write $S(1234) \equiv 1690421400 \pmod{1000000007}$ or $S(1234) \equiv -309578614 \pmod{1000000007}$.

The problem statement is using both: equivalence for the S(1234) example, then an operator for S(12345678).

DewayneGunter
Posts: 5
Joined: Tue Apr 21, 2020 9:32 pm

Re: Problem 711

Thank you... I may be overthinking it I will come back to it... 2 days I am annoying myself with that one. but like with many things it will come to me when I am doing something else not thinking about it. and a sound will go off in my head like uhh derrrp ... I am going to write me some ASM libs for personal bit use. thanks for the clarification.