Sip Posted March 3, 2002 Report Share Posted March 3, 2002 I know it is a very strange problem to figure out and there is probably no way anyone would even think about it without the hint (computer program) So the big hint is this ... if you compile and run this program, you will get the answers I said above (30000+35546=10 and 150+150=44) :code:#include int main() { short a=30000, b=35546; unsigned char c=150+150; cout << 30000 << " + " << 35546 << " = " << a+b << endl; cout << 150 << " + " << 150 << " = " << (int)c << endl; return 0;} Quote Link to comment Share on other sites More sharing options...
Garo Posted March 3, 2002 Report Share Posted March 3, 2002 quote:Originally posted by Sip:I know it is a very strange problem to figure out and there is probably no way anyone would even think about it without the hint (computer program) So the big hint is this ... if you compile and run this program, you will get the answers I said above (30000+35546=10 and 150+150=44) :code:#include int main() { short a=30000, b=35546; unsigned char c=150+150; cout << 30000 << " + " << 35546 << " = " << a+b << endl; cout << 150 << " + " << 150 << " = " << (int)c << endl; return 0;}Actually the explanation is very simple - register overflow. And it will happen only when the computer stores the number in 2 byte register (16 bit). When the register has 16 bits it's capable of storing up to 2^16=65536. After you add 1 the computer needs 17 bits to store the number 65536 in the register (it's one '1' and sixteen '0's); Because it has only 16 bits, the leftmost bit gets lost and we have 0 - sixteen '0's in the register. This is true for unsigned integer case (0-65535) only. In case of signed integers, to store the negative numbers the computer uses the high bit of the register to store the sign (+ or -).When you overflow this register the result is not the same as with unsigned integer. And I think this kind of problems happens with C programs more often than with Pascal programs.Pascal has very strong built-in range chacking features compared to C. Quote Link to comment Share on other sites More sharing options...
Sip Posted March 4, 2002 Report Share Posted March 4, 2002 Very nice Garo Computer (or calculator) math is often very different than pure math! This is because inside your computing device, you only have a fixed amount of "bits" to represent numbers. In pure math, precision is infinite. This is what gets many brilliant scientists in trouble ... they don't realize that you really can't trust what the computer is telling you as the answer to your calculations! The answers can often be very very wrong. The above are just examples of "range" errors. As Garo said, with 16-bit numbers, you can only represent 65536 different things. That means you can have numbers between -32768 ... 32767 (including 0). When you add 30000 and 35546, your numbers "wrap around" and you end up at +10 !!! Same way with 8-bit numbers. With 8 bits, you can only represent 256 things, that means numbers from 0 to 255. When you add 150+150 you should have 300 but that result "wraps around" and you end up at 44 !!! There are a whole bunch of other problems when you do "floating point" calculations (i.e. involving fractions). If interested, I can explain more (maybe in the computer section ) For example, if you are trying to evaluate an n-degree polynomial with cooeficients a0 ... an: an x^n + an-1 x^(n-1) + ... a2 x^2 + a1 x + a0 You could either write a program which just does that (as above) or you could do: (((((an * x) + an-1)*x + ...) + a2)*x + a1) * x + a0 In pure math, they are both equivalent but in computers, the second one will be much much much more accurate than the first one! Not to mention that the second one will be much much faster than the first one (if anyone can say the reason for both, I'll be impressed ) So computer math is very different than pure math ... it's definitely much more fun in my opinion but I am sure there are people that will disagree. Quote Link to comment Share on other sites More sharing options...
Azat Posted March 4, 2002 Report Share Posted March 4, 2002 quote:Originally posted by Sip:I know it is a very strange problem to figure out and there is probably no way anyone would even think about it without the hint (computer program) So the big hint is this ... if you compile and run this program, you will get the answers I said above (30000+35546=10 and 150+150=44) smilies/confused.gif :code:#include int main() { short a=30000, b=35546; unsigned char c=150+150; cout << 30000 << " + " << 35546 << " = " << a+b << endl; cout << 150 << " + " << 150 << " = " << (int)c << endl; return 0;}Duhhhhhhhh. I should have beeen able to figure this one out. Quote Link to comment Share on other sites More sharing options...
Garo Posted March 4, 2002 Report Share Posted March 4, 2002 I think even with 8 bit register computer you can do very precise calculations, espacially with integer numbers. You interpret the numbers as characters and do the calculations. If I'm not mistaken someone has calculated the longest value of 'Pi' (3.14....) using this method. Quote Link to comment Share on other sites More sharing options...
Garo Posted March 4, 2002 Report Share Posted March 4, 2002 quote:Originally posted by Sip:For example, if you are trying to evaluate an n-degree polynomial with cooeficients a0 ... an: an x^n + an-1 x^(n-1) + ... a2 x^2 + a1 x + a0 You could either write a program which just does that (as above) or you could do: (((((an * x) + an-1)*x + ...) + a2)*x + a1) * x + a0 In pure math, they are both equivalent but in computers, the second one will be much much much more accurate than the first one! Not to mention that the second one will be much much faster than the first one (if anyone can say the reason for both, I'll be impressed ) With recursive calls to a subroutine?If yes then you need to be careful with stack overflows. Quote Link to comment Share on other sites More sharing options...
Sip Posted March 4, 2002 Report Share Posted March 4, 2002 quote:Originally posted by Garo:[With recursive calls to a subroutine?If yes then you need to be careful with stack overflows.No, not recursive. But instead of computing x^n then mutiplying with an, then computing x^(n-1), multiplying with an-1 and adding to previous value etc, just computing an * x, add the next a, *x, add next a, *x (like a simple loop). It's called "Horner's method of polynomial evaluation" and it basically requires n multiplications and n additions. The other naive method, requires n multiplications just to find x^n !!! Quote Link to comment Share on other sites More sharing options...
Sip Posted March 7, 2002 Report Share Posted March 7, 2002 quote:Originally posted by Edita:DE karaq aseq,e.......Ten people can paint 60 houses in 120 days, so five people can paint 30 houses in how many days?10 people, 60 houses, 120 days ... that means 1 person, 6 houses, 120 days ... that means 1 person, 1 house, 20 days. If that's true, then we have 5 people, 30 houses ... 5 people, 6 houses each, meaing 120 days again. Assuming that is correct ... here's the next problem. It is fairly well known in certain crowds these days as it has been known to appear on Microsoft internship interiew tests. It's a cool problem (not really math but I guess math has many meanings!): Question: There are 3 light bulbs in a room. There is another room with 3 switches with ON/OFF positions. Each switch controls one of the lights. How many times do you have to go from room to room to figure out which switch controls which light? (the goal is to figure out the switches with as few trips between rooms as possible). [ March 06, 2002, 11:43 PM: Message edited by: Sip ] Quote Link to comment Share on other sites More sharing options...
Sip Posted March 7, 2002 Report Share Posted March 7, 2002 Ok I'll give another hint and PM you the answer. Check your personal messages when you really give up I am assuming that you are probably thinking computer science-ish (like I did) ... i.e. you are thinking that with each trip you can figure out 2 lights (on/off) ... since there are 3 lights, you have to have at least 2 trips. So clearly pure "logic" (1/0) analysis will not work Of course, I did NOT get the answer to this problem myself. Some one had to tell me! Quote Link to comment Share on other sites More sharing options...
hasmiek Posted March 7, 2002 Report Share Posted March 7, 2002 Well, it does make me feel better that you didn't know the answer either... Quote Link to comment Share on other sites More sharing options...
Azat Posted March 7, 2002 Report Share Posted March 7, 2002 It depends if these light bulbs get hot or not? (oh, I guess that is a hint, is it not?) Quote Link to comment Share on other sites More sharing options...
Sip Posted March 7, 2002 Report Share Posted March 7, 2002 Ok for those who figured out the light thing (Azat, Hasmiek, etc) already ... do you want another one? This one is actually one of my favorites... Question How can two people do a "coin toss" on the phone (or by email, fax, etc) if they can't trust each other? As you know with a coin toss, someone calls heads, the other calls tails, you flip a coin and then whoever called the right thing wins. The problem here is that the 2 people can't trust each other but they still need to do a coin toss. To make matters worse, is that one will do the toss but the other is not physically there to make sure everything is ok. So, any ideas on how it can be done? [ March 07, 2002, 10:23 AM: Message edited by: Sip ] Quote Link to comment Share on other sites More sharing options...
Azat Posted March 7, 2002 Report Share Posted March 7, 2002 Sip,I sort of remember reading this puzzle and thinking that it was very clever, but do not remember the answer completely. I however do think I can compose my own answer based on my memory. I remember it as choosing a number, taking the square root 3 times giving the last 5 digits and asking if the initial number was even or odd. Am I in the ball park? Quote Link to comment Share on other sites More sharing options...
Sip Posted March 7, 2002 Report Share Posted March 7, 2002 hmmmm that's very interesting Azat jan. The thing is that if I know you are taking square roots 3 times, then when you give me the number I can work it backwards, determine if the original number was odd or even and then base my decision on that. So can you come up with a "function" where going backwards would be very very hard to do. I don't think square root would work but I am not 100% sure. Edit: On second thought, since you said you are giving the last 5 digits (I had assumed least significant, but I am thinking maybe you meant most significant) then it could maybe work. The think is that maybe there are two numbers which have the same "last 5 digits" that work out to odd and even things initial numbers ... [ March 07, 2002, 11:59 AM: Message edited by: Sip ] Quote Link to comment Share on other sites More sharing options...
Sip Posted March 7, 2002 Report Share Posted March 7, 2002 Oh and I forgot to say that the answer I have in mind basically comes from cryptography. It uses the same principles as what your browser does to do public key encryption But to those who have no idea what I am saying, don't worry, you don't have to know cryptography to understand the answer. Quote Link to comment Share on other sites More sharing options...
hasmiek Posted March 7, 2002 Report Share Posted March 7, 2002 the lightbulb question.....2 times? Quote Link to comment Share on other sites More sharing options...
Sip Posted March 7, 2002 Report Share Posted March 7, 2002 Are you sure Hasmik jan? Some of us are really lazy and only want to do it with 1 trip Is it possible? (hint, it is!) Quote Link to comment Share on other sites More sharing options...
hasmiek Posted March 7, 2002 Report Share Posted March 7, 2002 ? 0ne? tell me tell me! ?( i hate to admit this...but i don't get it....) [ March 07, 2002, 12:55 AM: Message edited by: hasmiek ] Quote Link to comment Share on other sites More sharing options...
Azat Posted March 7, 2002 Report Share Posted March 7, 2002 quote:Originally posted by Sip:Edit: On second thought, since you said you are giving the last 5 digits (I had assumed least significant, but I am thinking maybe you meant most significant) then it could maybe work. The think is that maybe there are two numbers which have the same "last 5 digits" that work out to odd and even things initial numbers ...That is exacly what I was thinking. But you are correct. I am sure there are many numbers where the last 5 digits are the same after it has been squarerooted 3 times. Quote Link to comment Share on other sites More sharing options...
Sip Posted March 8, 2002 Report Share Posted March 8, 2002 I am thinking that maybe it's time for another hint ... sorry if it is annoying to give slow hints but I always think once a problem is "solved" it is not fun anymore The hint from cryptography is about prime number factorization (it is VERY hard to do). ---Light bulb solution as Azat mentioned ... The key is to use another piece of information that physical light bulbs provide! What you do is: turn 2 lights on. Wait a while, turn one of them off. Go to the room with the lights. You have 3 lights. One will be on, 2 will be off, one of those 2 will be WARM! So the one that is WARM is the one that you turned off after waiting for some time. [ March 08, 2002, 08:18 AM: Message edited by: Sip ] Quote Link to comment Share on other sites More sharing options...
Azat Posted March 8, 2002 Report Share Posted March 8, 2002 Sip, are you going to make as encrypt and number and send the encrypted code without the key and they have to guess it is it odd or even? Keep the clues slow as I like to see if I could get the solution. I still think my answer was easier and better. Quote Link to comment Share on other sites More sharing options...
Sip Posted March 8, 2002 Report Share Posted March 8, 2002 Yes, basically that's what has to be done. So we are looking for a function F(x), that has these properties: 1) F(x) must be completely defined. Both parties have to know it before tossing the coin. 2) F(x) is uniquely defined for any given x, i.e. if you have any different x1 and x2, then F(x1) is NOT equal to F(x2) 3) It must be VERY hard to determine inverse of F(x). That means one should not be able to easily go back from F to x. This way, if I do the toss and the outcome is x, I send you the F(x). You still have NO idea what x is but later, when I tell you what x was, you can verify it by applying F(x) to it and checking to see if it matches to what I sent earlier. Basically, this is how 1-way hash functions work (like MD5 and SHA). I have a feeling that the square rooting method you proposed first has a problem with #2 above. You have to specify your method very clearly and then we can check to see if it works Edit: In this problem things are simple since there are only 2 things that can happen ... heads or tails. So our function is just a simple way of "encoding" the heads or the tails information. [ March 08, 2002, 02:34 PM: Message edited by: Sip ] Quote Link to comment Share on other sites More sharing options...
Guest Fadi Posted March 8, 2002 Report Share Posted March 8, 2002 Someone pointed me this and asked me why the answer is zero. "(x+a)(x-(x+c)(x-d)(x+e)... All the way to ...(x-z)" Well, Harut I would like to know your method of calculation... because the question is vague, first I agreed with the answer you gave supposing that when he asked for the answer he ment the possible solution, and I supposed that a, b, c etc... are just subsequent numbers of the type b = a + 1, c = a + 2 etc... and I ended up with the product answer ending with a natural number of (abcedfghig...z), then it would be a factorial, and since the x with the highest power would be x^26, and supposing that a, b, c etc... are natural numbers > 0, we will end up with the possibility that (...)^1/26 should exist then the ... should be > 0, in order that we don't end up with a complex number(i), then being so the only possibility in order to make this product exist in this case that I found was 0... But this is the problem, if we extend this with these 26 multiplication fonctions we find a graphic that will have different proptrieties in every area,s so in order that the answer be zero we have to suppose that a to z would be in a D "voisinage" of some sort of limit that we fix... In some, even if we use what Azad has suggested(using a supper computer), we should know if a...b are numbers, and if they are linked with each others( for example b= a+1 etc...) if not, they are fonctions, the forget about it I do not know any super computer that would be able to find any results... I just was wondering which methods you took [ March 08, 2002, 05:19 PM: Message edited by: Domino ] Quote Link to comment Share on other sites More sharing options...
Sip Posted March 8, 2002 Report Share Posted March 8, 2002 I just assume it is zero becuase you have the term (x-x) in there Quote Link to comment Share on other sites More sharing options...
Guest Fadi Posted March 9, 2002 Report Share Posted March 9, 2002 seaphan, not a good answer, you suppose that there is no "nonderterminated" term in this fonction so supposing that the term x would be the same as the other term x, then there is no condition asked by Azat, because I can say then "a" approch infinit, then we will have a infinit(0) form that is non derterminated I tough of this first, but again we have no idea of what a, b, c etc... are, what if there is a kind of 1/0 for that will end up of having a 0/0 form. See ? You tough you got me on that, did you not ? (To say you the truth I tough that the x of the a, b, c etc... was not the same kind of variable as the first x, because I tough Azat was asking a math question not a kind of hidding ... like x-x ) [ March 08, 2002, 06:18 PM: Message edited by: Domino ] Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.