Logic/maths puzzles

[Dannyboy-the-Dane]

Because there's no other way to determine their own eye colour. If there are n blue eyed people, then they all have to wait n-1 days to rule out there only being n-1 blue eyed people. In the original case, a given blue eyed person realises that everyone is either seeing 99 other people (like him), or (if he doesn't have blue eyes), 98. There's no way of ruling out there being 98 people without thinking about the reasoning that would go on in that situation, and so everyone has to wait to ensure that the embedded hypotheticals are false.

 

Yep.

Ah, so it works because they all follow every hypothesis and its consequences to the very end?

 

Person 1: 99 have blue eyes, I assume I have brown.

 

In this hypothetical scenario, person 2 would think: 98 people have blue eyes, I assume I have brown.

 

In THIS hypothetical scenario, person 3 would think: 97 people have blue eyes, I assume I have brown.

 

For each day, every blue eyed person is able to prove a link of this chain false, and at the final day, they will all have proven false every other possibility than them all having blue eyes.

[Supergrunch]

Yep, you guys have both got it. What the green eyed person says is important because he lets the people know that everyone knows there is someone with blue eyes, including people in the hypothetical cases, which is important for the hypothetical situation of there only being one blue eyed person.

[chairdriver]

But what about brown eyed people?

 

How do they know that they aren't blue eyed?

 

Say there is the 1 green, 1 brown and 2 blue.

 

He says "I can see someone with blue eyes." After night 2, the 2 blue ones leave. How does the brown one deduce which colour eyes he has?

[SPAMBOT4000]

They see 100 blue eyed people instead of 99 so effectively are waiting for the night after all the blue people leave, at which point, they know they don't have blue eyes. Righhht?

[Jonnas]

This thread moves fast

I probably wouldn't have gotten the blue-eyes riddle without Grunch's clue about 7 people, though (no, I didn't look at the solution of that clue). It's hard to wrap our heads around all of these hypothetical scenarios, but if we assume that each person is a computer, and each person already knows how each scenario goes, it works.

 

@chairdriver: How do they know their eyes aren't green? All they know is that the blue guys left. They waited for that 101st day, and if no one left, they'd conclude that they were the 101st blue-eyed person on the island. But they left, so they know they aren't blue-eyed.

 

Now, the green-eyed person needs to shout "I see someone with brown eyes!" so they can leave in another 100 days.

[MoogleViper]

The brown eyes never leave. MWAHAHAHAHAHA!

[Supergrunch]

Next puzzle!

 

This one actually has practical applications. Imagine you're writing the program for a computer to search a block of text for a particular sequence of characters (or string). Let's assume we're using a large but finite alphabet, which includes letters, numbers, spaces, unicode twaddle, etc. Thus we can view the text as a sequence of these characters, and we want to find a given string in this sequnce. The most obvious way to do this is as follows:

 

Check the first letter - does it match with the first letter of the string?

(i) Yes - does the second letter match with the second letter of the string?

(ii) No - move along one position and check the second letter - does this match with the first letter of the string?

 

And basically repeat this process until the string is found or the whole text has been searched. An example of this:

 

Here's our text (it's short, for convenience):

 

GARLIC AND SAPPHIRES IN THE MUD CLOT THE BEDDED AXLE-TREE

 

We're searching for the string "CLOT".

 

Here's what happens:

 

GARLIC AND SAPPHIRES IN THE MUD CLOT THE BEDDED AXLE-TREE

CLOT

 

The first letter gets checked, but it's not the same as the first letter of "CLOT", so we move along.

 

GARLIC AND SAPPHIRES IN THE MUD CLOT THE BEDDED AXLE-TREE

_CLOT

 

Neither is the second letter, so we move along again, and so on. When we come across the first "C", however:

 

GARLIC_AND SAPPHIRES IN THE MUD CLOT THE BEDDED AXLE-TREE

_____CLOT

 

We have a match! So we check the following character, but it's a space (marked with an underscore so I can colour it) rather than an "L", so we move on again.

 

But when we get to "CLOT", everything matches, and so we've found the string:

 

GARLIC AND SAPPHIRES IN THE MUD CLOT THE BEDDED AXLE-TREE

_______________________________CLOT

 

Anyway, that's the idea of this process. The question, however, is whether you can think of a more efficient way of doing things - do all the letters have to be checked?

Edited January 28, 2010 by Supergrunch

[MoogleViper]

ctrl + f "clot"?

[Supergrunch]

ctrl + f "clot"?

Lol, you're presumably joking. This is about the kind of programming underlying functions like ctrl+f.

[Mr_Odwin]

Interesting. Never thought about this before. I think I have at least some of it.

 

Going with the clot example.

Check the first letter to see if it is a c, if it is then check until fail/success.

When there is a fail you can skip forward four letters from where it failed. If this is not c, l, o or t then you don't need to check the preceding letters, and can skip forward four letters ahead again. If it is one of those then make the appropriate checks forwards/backwards.

 

 

 

[Supergrunch]

Interesting. Never thought about this before. I think I have at least some of it.

 

Going with the clot example.

Check the first letter to see if it is a c, if it is then check until fail/success.

When there is a fail you can skip forward four letters from where it failed. If this is not c, l, o or t then you don't need to check the preceding letters, and can skip forward four letters ahead again. If it is one of those then make the appropriate checks forwards/backwards.

 

 

That doesn't work, because there's nothing to stop arrangements like this:

 

ACLOTXYZ

 

Here the first check would fail:

 

ACLOTXYZ

CLOT

 

But if you skip forward, you miss the word:

 

ACLOTXYZ

____CLOT

 

You're on the right track though.

 

Edit: Oh wait I think I see what you mean. After the skip, the "T" means you check backwards? I guess that would work to some extent, but would make for some pretty complex code. Plus long words make things difficult, as you're going to come up against a load of letters that have to be checked but have no instances of the word. It may well still be an improvement however, but there's a much more elegant way of doing a similar sort of thing.

 

Edited January 28, 2010 by Supergrunch

[Jonnas]

For the following, I will call the method Supergrunch described as merely "Supergrunch"

 

1) Check the first character

-1a) If "C", check the second character, apply Supergrunch, until it completes the string, or finds a wrong character (in which case, apply step 2);

-1b) If "not-C", proceed to step 2.

 

2) Skip the next character. Check the one after that.

-2a) If "C", apply Supergrunch until it completes the string, or finds a wrong character (in which case, repeat step 2 from the beginning);

-2b) If "L", apply Supergrunch starting with the previous character until it completes the string, or finds a wrong character (in which case, repeat step 2 from the beginning);

-2c) If neither "C" nor "L", repeat step 2 from the beginning.

 

 

Now, I doubt that what I wrote above is the full correct answer, but am I getting close?

[Supergrunch]

For the following, I will call the method Supergrunch described as merely "Supergrunch"

 

1) Check the first character

-1a) If "C", check the second character, apply Supergrunch, until it completes the string, or finds a wrong character (in which case, apply step 2);

-1b) If "not-C", proceed to step 2.

 

2) Skip the next character. Check the one after that.

-2a) If "C", apply Supergrunch until it completes the string, or finds a wrong character (in which case, repeat step 2 from the beginning);

-2b) If "L", apply Supergrunch starting with the previous character until it completes the string, or finds a wrong character (in which case, repeat step 2 from the beginning);

-2c) If neither "C" nor "L", repeat step 2 from the beginning.

 

 

Now, I doubt that what I wrote above is the full correct answer, but am I getting close?

Interesting. I guess that would be faster, but there's an even faster and more uniform way of doing things, and your method would have to be modified when searching for one character strings. Also note that there's not necessarily only one correct answer, given the open-ended nature of the problem.

[Supergrunch]

Is nobody getting any further? How about a hint:

Does the word have to be checked forwards?

 

[Jonnas]

Is nobody getting any further? How about a hint:

Does the word have to be checked forwards?

 

I tried that line of thinking, but I still don't see how it could be faster (and different from Mr_Odwin's theory). I'm stumped, here

[Supergrunch]

Right, seeing as nobody seems to be getting further, I'll present the method that I was thinking of:

You guys have the right idea about skipping out letters and so on, but there's a much more uniform way of doing this. Following Odwin's basic ideas, we check words backwards, but the key thing is that we only check them backwards, and not forwards. However, if we still move fowards through the text, this works out very nicely.

 

For example then, if we have a string like "CLOT" that's 4 letters long, we start by checking the 4th character and seeing whether it's "T" - if it is, we then check the 3rd character to see if it's "O" and so on. If we get a mismatch though, we can skip a lot further:

 

SAPPHIRES

CLOT

 

Now the mismatching character is a "P". We can then check "CLOT", and if it doesn't occur anywhere in the word (as is the case here), we know for certain that CLOT is in none of the following positions:

 

SAPPHIRES

CLOT

_CLOT

__CLOT

___CLOT

 

So we can start checking again at the 8th position:

 

SAPPHIRES

____CLOT

 

And then we can move along 4 letters again, and so on. Of course, if the mismatching letter is in the word, you can get around this with methods of varying efficiency - probably the best thing to do is to try fitting the word in where it may go.

 

This approach is known as the Boyer-Moore string search algorithm, and has the weird property of being faster at searching for longer words. I find it pretty cool, anyway.

 

Having typed all that up, I realised that Odwin's solution is fairly close.

Edited February 3, 2010 by Supergrunch

[Jonnas]

Ahhh... What struck me as odd was you dismissing Odwin's theory as being "too complex". The answer was actually just a way of making sure his theory worked.

[Supergrunch]

Ahhh... What struck me as odd was you dismissing Odwin's theory as being "too complex". The answer was actually just a way of making sure his theory worked.

I guess I meant too complex in that you have to check both backwards and forwards, but his solution was more similar than I was thinking.

[Mr_Odwin]

So ... turns out I'm pretty awesome?

[Supergrunch]

Seems so. Now someone post another puzzle, or I shall...

[MoogleViper]

Here's an easy one:

 

There are three bulbs in your basement. And three corresponding switches for them upstairs. The switches aren't labelled. And you can't tell from standing at the switches which bulb is on. How can you work out which switches correspond to which bulbs if you can only make one trip to the basement?

[Supergrunch]

I've heard the solution to this before, and I'd say it's kind of a borderline trick question, but I'll let it slide as it involves deduction too.

[MoogleViper]

Ok well here's a maths one that I've found.

 

There are one thousand lockers and one thousand students in a school. The head teacher asks the first student to go to every locker and open it. Then he has the second student go to every second locker and close it. The third goes to every third locker and, if it is closed, he opens it, and if it is open, he closes it. The fourth student does this to every fourth locker, and so on. After the process is completed with the thousandth student, how many lockers are open?

[Supergrunch]

Gah, it's horrible doing these problems when tipsy - I keep going round in circles.

 

I'm pretty sure the answer is:

31. This question is basically about factors - if we refer to each locker by its number, it becomes clear that lockers with an odd number of factors will be the only ones left open, as lockers will be opened for their first factor (1), then closed for their second, opened for their third and so on. So we need to work out how many numbers there are between 1 and 1000 inclusive that have an odd number of factors. But only square numbers have an odd number of factors - we can see this by looking at pairs of factors. For example, the non-square 12 is equal to 1x12, 2x6 and 3x4, so the factors are 1, 2, 3, 4, 6, and 12 - there has to be an even number due to the pairing off. But a square has a repeated pair - e.g. 16 has 1x16, 2x8, and 4x4, leading to 1, 2, 4, 8, and 16 - an odd number of factors. So it's just a matter of finding the number of squares between 1 and 1000, and 31^2 = 961 whereas 32^2 = 1024, so the answer is 31.

 

As for the light problem, if you've abandoned it, am I right in saying this is the solution?

Let's call the switches A, B, and C. If you turn on switch A for a period of time, then turn it off, and turn on switch B, you can then go down to the basement. The lit bulb is obviously controlled by switch B, the one that is off but feels warm by switch A (because it was left on), and the remaining one by switch C. I guess you don't have to turn off switch A, and can just touch both lit bulbs, but turning it off seems clearer to me.

 

I guess people can judge for themselves whether that counts as a trick, or just ignore the spoiler and solve it anyway.

Edited February 5, 2010 by Supergrunch

[MoogleViper]

Yeah they're both correct.

 

Ok some more. (spoilered to look tidier.)

 

What is the probability that the next person you meet has an above average number of arms?

 

Impossible, Very Unlikely, Unlikely, Even, Likely, Very Likely, Certain.

 

 

* There are 10 baskets containing apples.

* There are various amounts of apples in each basket ranging from 10 to 20.

* 9 of the baskets contain apples weighing 4 ounces each.

* 1 of the baskets contains apples weighing 5 ounces each.

* All the apples look the same.

* The equipment you have is a set of scales and an empty basket.

* It is late and the lorry is waiting to take the apples to market. You only have time to make one measurement using the scales.

 

Can we find out which basket has the heavier apples? If so how?

 

PS. the scales measure weight, not two-way balance scales.

 

 

A census taker approaches a house and asks the woman who answers the door,"How many children do you have, and what are their ages?"

 

Woman: "I have three children, the product of their ages are 36, the sum of their ages are equal to the address of the house next door."

 

The census taker walks next door, comes back and says, "I need more information."

 

The woman replies, "I have to go, my oldest child is sleeping upstairs."

 

Census taker: "Thank you, I now have everything I need."

 

What are the ages of each of the three children?

 

Edited February 6, 2010 by MoogleViper