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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
mdean
Posts: 165
Joined: Tue Aug 02, 2011 2:05 am

Problem 711

Post by mdean »

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.
Image

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

Re: Problem 711

Post by LilStalker »

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

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

Re: Problem 711

Post by brob26 »

"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.
Image

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

Re: Problem 711

Post by mdean »

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

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

Re: Problem 711

Post by DewayneGunter »

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

Post by DJohn »

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).

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

Re: Problem 711

Post by DewayneGunter »

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.

Post Reply