Problem 280

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
User avatar
Lord_Farin
Posts: 239
Joined: Wed Jul 01, 2009 9:43 am
Location: Netherlands

Problem 280

Post by Lord_Farin » Sat Feb 27, 2010 9:16 pm

Problem 280 (View Problem)

There seems to be some ambiguity. Is 'the upper row' the same as 'the top row'? ie does the ant drop the seed on the 2nd row or on the 5th row (measured from the bottom)?

I am inclined to think it's the 5th, though I would like a definite answer.
Image

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 8:33 pm
Location: Thessaloniki, Greece

Re: Problem 280

Post by harryh » Sat Feb 27, 2010 9:26 pm

Every seed is dropped on the fifth row (counted from the bottom).

x10
Posts: 8
Joined: Sun Jul 19, 2009 7:20 pm

Re: Problem 280

Post by x10 » Sun Feb 28, 2010 9:56 am

Hello, I have a question:

This is a valid starting position:
00000
00000
00000
00000
11111

This is a valid endgame position:
11111
00000
00000
00000
00000

Is this a valid endgame position?
00005
00000
00000
00000
00000

Also, is the answer of the form:
XX.49XXXX
Thanks.
Image

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 8:33 pm
Location: Thessaloniki, Greece

Re: Problem 280

Post by harryh » Sun Feb 28, 2010 10:07 am

x10 wrote:Hello, I have a question:
It seems like you have four questions :)
This is a valid starting position:
00000
00000
00000
00000
11111
Yes.
This is a valid endgame position:
11111
00000
00000
00000
00000
Yes.
Is this a valid endgame position?
00005
00000
00000
00000
00000
No: The problem statement says:
"The ant will drop the seed on the first empty square of the upper row it eventually reaches."


Also, is the answer of the form:
XX.49XXXX
Thanks.
That kind of question has nothing to do with understanding the problem, so it cannot be answered.

YoFrankie
Posts: 2
Joined: Wed Apr 14, 2010 12:34 am

Re: Problem 280

Post by YoFrankie » Wed Apr 14, 2010 12:37 am

my ant always needs between 380 and 480 steps but i just dont know how to enter that result.
"Give your answer rounded to 6 decimal places."
what does that mean?!?!
i think that sentence has nothing to do with understanding the problem - i just want to know how to enter my result - it's annoying me! :?

example of my ant walking around randomly (the last steps)

Code: Select all

11130
00000
00000
00000
00100

11310
00000
00000
00000
00100

11130
00000
00000
00000
00100

11110
00020
00000
00000
00100

11110
00200
00000
00000
00100

11110
00000
00200
00000
00100

11110
00000
00000
00200
00100

11110
00000
00000
02000
00100

11110
00000
00000
00200
00100

11110
00000
00000
00000
00200

11110
00000
00000
00000
00020

11110
00000
00000
00020
00000

11110
00000
00000
00002
00000

11110
00000
00002
00000
00000

11110
00000
00020
00000
00000

11110
00000
00002
00000
00000

11110
00002
00000
00000
00000

11110
00020
00000
00000
00000

11130
00000
00000
00000
00000

11110
00020
00000
00000
00000

11110
00200
00000
00000
00000

11110
00020
00000
00000
00000

11110
00000
00020
00000
00000

11110
00000
00000
00020
00000

11110
00000
00000
00000
00020

11110
00000
00000
00000
00002

11110
00000
00000
00002
00000

11110
00000
00000
00020
00000

11110
00000
00020
00000
00000

11110
00020
00000
00000
00000

11110
00002
00000
00000
00000

11110
00000
00002
00000
00000

11110
00002
00000
00000
00000

11110
00000
00002
00000
00000

11110
00002
00000
00000
00000

11113
00000
00000
00000
00000

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Problem 280

Post by TripleM » Wed Apr 14, 2010 2:33 am

Suppose you flipped a coin 11 times and counted how many heads you got. Most of the time you would get somewhere between 4 and 7 - but the exact average number of heads you would get is exactly 5.5.

You have to specify how many steps the ant would average if you ran the simulation a very large number of times.

YoFrankie
Posts: 2
Joined: Wed Apr 14, 2010 12:34 am

Re: Problem 280

Post by YoFrankie » Wed Apr 14, 2010 5:02 pm

so my solution doesn't work, as i had to run the simulation about 1000000000000000 times, right?

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 10:57 pm
Location: Netherlands

Re: Problem 280

Post by stijn263 » Wed Apr 14, 2010 5:23 pm

1014 simulations would suffice, yes, but that's not feasible within the 1-minute rule (or the 1-year rule ;-))

You need to think of an exact way to calculate the expectation. Good luck!

quilan
Posts: 182
Joined: Fri Aug 03, 2007 10:08 pm

Re: Problem 280

Post by quilan » Thu Jun 10, 2010 12:47 am

Ok, so I think I've got a handle on the maths required for this, but my very very simple brute force simulation is producing some odd values.

So, starting from the middle square:
00000
00000
00X00
00000
11111

would the actual expected value of the number of turns it takes to reach the N'th item on the bottom row be more along the lines of {~27,~24,~19,~24,~27} turns? Because that seems really high to me.

The equivalent 3x3 scenario is giving me the equally odd numbers:
000
0x0
111

E = {~7,~4.5,~7}

Am I wildly off base here & should look into my brute force simulation, or are these close enough to the actual values that I can start delving into formulas & good stuff?
ex ~100%'er... until the gf came along.
Image

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

Re: Problem 280

Post by TripleM » Thu Jun 10, 2010 5:16 am

I haven't checked the numbers exactly, but they don't look strange to me. For example, in the 3x3 case, if you are aiming for the bottom square, three quarters of the time you are moving further away from it in the first turn, so you would expect it would take several more turns before you get back there. For the two corner squares, even after you finally reach something adjacent to the corner, two thirds of the time you move away again.

I think you should be able to trust your brute force program.

Post Reply