Riddle for u to solve
Riddle for u to solve
There are 100 prison cells. the prison guard passes by and unlocks every cell. then he passes by and toggles every 2nd cell. next he passes by and toggles every 3rd cell, so on an so forth until he has passed by 100 times. So at the end of all this wich cells are unlocked?
- Hero of Canton
- Posts: 98
- Joined: 23 Sep 2007, 16:06
- NachoManLance
- Posts: 442
- Joined: 27 Nov 2007, 07:16
- First Video: The Stages
- Location: San Jose, CA
- Contact:
- AlexanderDitto
- Better Than the First Alexander
- Posts: 4382
- Joined: 28 Nov 2007, 07:41
- First Video: Desert Bus 1: The Original!
- Location: Phailadelphia (Again)
- Contact:
This isn't really a riddle... it's a math problem! Delicious.
You just factor the cell's number, and find out how many possible combinations of numbers can be made by multiplying those numbers. We only want to consider cells that have an even number of possible combinations, since those cells will always be (locked, then unlocked).
Obviously, if the number is prime, it only has one factor. It will be locked.
Note also that if a number can be factored only once (has two factors), that gives you three numbers (x, y, and x*y), which is bad. If the number has two factors that are the same, however, it's good (x, x*x).
If a number can be factored into three distinct parts, you actually have seven possibilities (x, y, z, x*y, x*z, y*z, x*y*z), which means it's bad. If it can be factored into three parts, one of which repeats, we have (x, y, x*x, x*y, x*x*y), which is five, so it's bad. If it can be factored into three parts, all of which repeat, it's bad (x, x*x, x*x*x).
This gets a little more complicated for four factors... since you can have two sets of repeated factors. Look: (C is "choose", ie the combination function)
Four distinct: (4C1+4C2+4C3+4C4) = 4+6+4+1= 15, bad
Two distinct, two repeated: ((4C1-1)+(4C2-2)+(4C3-1)+4C4) = 4+4+3+1 = 12, good
One disctinct, three repeated: ((4C1-2)+(4C2-4)+(4C3-2)+(4C4-0)) = 2+2+2+1 = 9, bad
Four repeated: ((4C1-3)+(4C2-5)+(4C3-3)+(4C4-0)) = 1+1+1+1=4, good
Two sets of two repeated: 2+3+2+1 = 8, good
Five factors makes your eyes bleed. Just... trust me. There's a pattern, I'm thinking it's a difference of combinations that I could write a sum for, letting n be the number of factors, k the number of disctinct factors, and m the number of different sets of repeated factors. Hm...
Well, whatever. I can brute force it, or I could write a computer program that printed the answers if you changed the problem to be 10,000 cells or something. For sake of argument I'll just... erm... do it by hand.
You just factor the cell's number, and find out how many possible combinations of numbers can be made by multiplying those numbers. We only want to consider cells that have an even number of possible combinations, since those cells will always be (locked, then unlocked).
Obviously, if the number is prime, it only has one factor. It will be locked.
Note also that if a number can be factored only once (has two factors), that gives you three numbers (x, y, and x*y), which is bad. If the number has two factors that are the same, however, it's good (x, x*x).
If a number can be factored into three distinct parts, you actually have seven possibilities (x, y, z, x*y, x*z, y*z, x*y*z), which means it's bad. If it can be factored into three parts, one of which repeats, we have (x, y, x*x, x*y, x*x*y), which is five, so it's bad. If it can be factored into three parts, all of which repeat, it's bad (x, x*x, x*x*x).
This gets a little more complicated for four factors... since you can have two sets of repeated factors. Look: (C is "choose", ie the combination function)
Four distinct: (4C1+4C2+4C3+4C4) = 4+6+4+1= 15, bad
Two distinct, two repeated: ((4C1-1)+(4C2-2)+(4C3-1)+4C4) = 4+4+3+1 = 12, good
One disctinct, three repeated: ((4C1-2)+(4C2-4)+(4C3-2)+(4C4-0)) = 2+2+2+1 = 9, bad
Four repeated: ((4C1-3)+(4C2-5)+(4C3-3)+(4C4-0)) = 1+1+1+1=4, good
Two sets of two repeated: 2+3+2+1 = 8, good
Five factors makes your eyes bleed. Just... trust me. There's a pattern, I'm thinking it's a difference of combinations that I could write a sum for, letting n be the number of factors, k the number of disctinct factors, and m the number of different sets of repeated factors. Hm...
Well, whatever. I can brute force it, or I could write a computer program that printed the answers if you changed the problem to be 10,000 cells or something. For sake of argument I'll just... erm... do it by hand.
Last edited by AlexanderDitto on 18 Mar 2008, 14:11, edited 3 times in total.
- scorpkahnpoop
- Posts: 287
- Joined: 02 Oct 2007, 03:48
- Contact:
- AlexanderDitto
- Better Than the First Alexander
- Posts: 4382
- Joined: 28 Nov 2007, 07:41
- First Video: Desert Bus 1: The Original!
- Location: Phailadelphia (Again)
- Contact:
Sieg Reyu wrote:The ones unlocked are those with an odd number of factors. The only numbers that do, are perfect squares.
But you're forgetting several things:
The doors will be "toggled" not only for their factors, but also for any product of their factors. For example, assume everything starts out unlocked (ignore the first "pass"... it's not really a pass, since he doesn't toggle all the cells, he just sets them all to unlocked). 12 will be toggled for the 2 pass (lock), the 3 pass (unlock), the 4 pass (lock), the 6 pass (unlock), and the 12 pass (lock). Note that 12 = 2*2*3, which has an odd number of factors. So your method doesn't work.
Also, you're not taking into account repeated factors, which will throw off your method, since they won't actually be toggled twice, three times, etc.
- Sieg Reyu
- Posts: 2930
- Joined: 16 Oct 2006, 12:24
- First Video: How to Talk Like a Pirate
- Location: State of Confusion
- Contact:
Factor
1. One of two or more numbers or expressions that are multiplied to obtain a given product. For example, 2 and 3 are factors of 6, and a + b and a - b are factors of a2 - b2.
The factors of 12 are 1, 2, 3, 4, 6, 12--- a Total of 6, even locked.
The factors of a perfect square, like 36, are, 1, 2, 3, 4, 6, 9, 12, 18, 36--- 9 Factors, unlocked.
You are thinking of prime factors.
1. One of two or more numbers or expressions that are multiplied to obtain a given product. For example, 2 and 3 are factors of 6, and a + b and a - b are factors of a2 - b2.
The factors of 12 are 1, 2, 3, 4, 6, 12--- a Total of 6, even locked.
The factors of a perfect square, like 36, are, 1, 2, 3, 4, 6, 9, 12, 18, 36--- 9 Factors, unlocked.
You are thinking of prime factors.
- AlexanderDitto
- Better Than the First Alexander
- Posts: 4382
- Joined: 28 Nov 2007, 07:41
- First Video: Desert Bus 1: The Original!
- Location: Phailadelphia (Again)
- Contact:
Sieg Reyu wrote:Factor
1. One of two or more numbers or expressions that are multiplied to obtain a given product. For example, 2 and 3 are factors of 6, and a + b and a - b are factors of a2 - b2.
The factors of 12 are 1, 2, 3, 4, 6, 12--- a Total of 6, even locked.
The factors of a perfect square, like 36, are, 1, 2, 3, 4, 6, 9, 12, 18, 36--- 9 Factors, unlocked.
You are thinking of prime factors.
Yes, that's what I ment. Prime factors. And you're right, it's only for numbers with an odd number of factors, if you include one. I wasn't, so I said even. I see the reason why now: each number's factorization includes only pairs of numbers, UNLESS you're a perfect square, which includes a doubled factor, which isn't included twice.
And since perfect fourth-roots must already be perfect squares, it already applies.
Crap. I concede!
- AndyTheSkanker
- Posts: 483
- Joined: 06 Dec 2007, 13:55
- Location: Scotland =D
- Contact:
- AndyTheSkanker
- Posts: 483
- Joined: 06 Dec 2007, 13:55
- Location: Scotland =D
- Contact:
- scorpkahnpoop
- Posts: 287
- Joined: 02 Oct 2007, 03:48
- Contact:
- scorpkahnpoop
- Posts: 287
- Joined: 02 Oct 2007, 03:48
- Contact:
10 in total:
and 100Sieg Reyu wrote:Cells 1, 4, 9, 16, 25, 36, 49, 64, 81
Last edited by Citin on 18 Mar 2008, 16:23, edited 1 time in total.
"I'll be in Africa. If you need me just phone Africa, I told them to expect your call." - The Pointy Haired Boss
Return to “General Discussion”
Who is online
Users browsing this forum: No registered users and 46 guests