A freshman CPS major was practicing octal arithmetic on a problem he made up himself. He eventually exclaimed, "OK, I've got it!" and wrote:
572 + 167 + 434 = 1315 (all numbers octal)
After just a few seconds glance the grad student tutoring him said "Nope, sorry that's still wrong".
Was the grad student right? How could he reach this conclusion without having time to do the arithmetic?
We have a square grid of n rows and n columns, i.e. it contains n*n squares in all. Each square can be either on or off. now we have a toggle operation such that if it is applied on any square it toggles all the squares that have a side common to the square(including the square itself). So, in a 3*3 matrix we have initially all off then when we perform toggle on say (2,2) then (1,2) (2,1) (2,2) (2,3) (3,2) are turned on.So, for any value of n supplied by user, we have to find a sequence of operations so that if all the squares intially are off they are turned on after that sequence.
For example, the sequences for n=1, 2, and 3 are:
n=1 (1,1)
n=2 (1,1) (1,2) (2,1) (2,2)
n=3 (1,1) (1,3) (2,2) (3,1) (3,3)
Taken from here w/0 a solution
^^ Interesting site with a lot of good questions/puzzles.
Don't read too many of them, b/c I will probably use them later :-p
Bonus (from me, not from the original puzzle) is find an algorithm that will produce a sequence that will work for an arbitrarially sized nxn matrix and only turns on a single specified square (e.g. leave a 5x5 matrix, initially off, with only the (1,3) spot on.
Also, what if the matrix was in an arbitrary initial state besides all being off and trying to turn them all on at the same time. What if some were on and others were off .... could an algorithm be devised which could take that board to a given state through a series of actions as described above?
I have no idea if either is possible....
If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?
eight
eighteen
eighteenmillion
eighteenmillioneight
eighteenmillioneighteen
eighteenmillioneighteenthousandand the last is
twothousandtwohundredtwo
The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point? [Bonus points for algorithms that will find the result for an arbitrary position, not just the 51st - Ben]
