It's that time of year again!

[theweaselking]

Today I do math nerdery and puzzles.

I was looking for the answer to the old one-off marble puzzle[1] because I knew it HAD a solution and I knew it had a SIMPLE solution but I couldn't remember what it was. In the process, I ran into this fun little puzzle:

PUZZLE #1:
"For any prime number greater than 3 (labelled "p") why is it that p²-1 is ALWAYS evenly divisible by 24?"

eg: 5 is prime. 5²-1 is 24. 13 is prime. 13²-1 is 168, which is 24x9. 17 is prime. 17²-1 is 288, which is 24x12. 4027 is prime. 4027²-1 is 16216728, which is 24x675697. For ALL prime numbers over 3, the number, squared, minus 1, will be evenly divisible by 24. Why?

In fact, while I'm here, PUZZLE #2
A vending machine dispenses two kinds of chocolate bar. It has three buttons - "Snickers", "Mars", and "Random". Snickers gets you a Snickers bar, Mars gets you a Mars bar, Random gets you either a Snickers or a Mars, 50/50 chance. At least, that's how it's SUPPOSED to work, but the guy who set it up screwed up the labels so none of the labels on the buttons are right. It costs $1 for a chocolate bar; what's the minimum amount of money required to be able to know, for certain, which button is which?



[1]: You know the one, right? You have 12 marbles, identical except one of them is either lighter or heavier than the others. You don't know which is the odd one out or if the odd one is light or heavy. You have only an old-style balance scale to use so you can measure marbles or groups of marbles against each other but not against anything else. Using only this scale, determine which is the odd one, and if it's light or heavy, in no more than 3 weighings. You know what, now that I've written it out, why not throw this out as a question to the audience, too? PUZZLE #3! It's super-old but has a neat counterintuitive solution.



Comments screened, correct answers will stay screened until I post solutions.

Comments

[scifantasy.livejournal.com]

Puzzle 1:

By the difference of squares formula, p² - 1 = (p+1) * (p-1).

Let's call those q and r (though they should be q and o, but o is bad).

If p is prime, then p is not divisible by 3. So it's either modulo 1 or 2 if you divide by 3.

So either q or r is a multiple of 3.

Likewise, if p is prime and greater than 3, it must be odd (the only even prime is 2), so q and r must both be even.

Finally likewise, if p is prime and greater than 3, and therefore odd, when modulo divided by 4 it must be either 1 or 3. (If it were modulo 2, it would be even. No dice.) Which means that one exactly one of q and r is divisible by 4--that is to say, 2^2.

So, within the prime factorizations of q and r, collectively, there is a 3, a 2, and 2².

Which means that within the prime factorization of q * r, there is 3 * 2 * 2 * 2...which is 24.

[theweaselking.livejournal.com]

Correct! Rescreening this now.

[pappy-legba.livejournal.com]

#2: $3. For buttons A,B,C, push buttons A and B once. Both dispense Snickers. You know one of the two is the random, and one is the dedicated Snickers button. By inference, you know C must be the Mars button. Push button A again, and get a Mars. Whelp, A is the random button, thus B is the Snickers button.

This is all irrelevant, since it is all hateful candy that pollutes chocolate with nuts.

[theweaselking.livejournal.com]

But what if you get a Mars and a Snickers in the first two pushes? Or if you push button A again, and get another Snickers? And another? And another? A might be the Random button but give you Snickers 9, 10, 100 times in a row.

(Also, it's worth noting, the buttons ARE labelled. They're just all labelled incorrectly.)

[scifantasy.livejournal.com]

That's the key. There we go. Answer to follow:

[pappy-legba.livejournal.com]

Ah. You want the minimum to be certain in all circumstances, not the theoretical minimum circumstance on could arrive at the question. (And I missed the -none- of the labels are right, which may decrease even the theoretical minimum.)

[pappy-legba.livejournal.com]

Oh yeah. It decreases the minimum to the minimum. $1 if all labels are known to be incorrect:

Push Random. That determines whether Random button gives mars or snickers (since we know it can't give random).

If Mars, then the button labelled Mars gives Snickers, and Snickers must give Random.
If Snickers, then the button labelled Snickers gives Mars, and Mars must give Random.

[theweaselking.livejournal.com]

Also: Mars bars have no nuts. They're just nougat and caramel inside chocolate. Snickers have nuts, though.

[pappy-legba.livejournal.com]

https://en.wikipedia.org/wiki/Mars_%28chocolate_bar%29

Mars bars have nuts. Not all Mars bars have nuts. Some Mars bars have no nuts.

[theweaselking.livejournal.com]

American fake Mars bars had nuts at one point. They were not Mars bars.

[pappy-legba.livejournal.com]

The is no meaningful value of 'true' for factory-manufactured piles of industrial confection.

[theweaselking.livejournal.com]

I didn't say "true." I said "fake", where "fake" means "not what I personally expect based on my childhood experiences"

[scifantasy.livejournal.com]

Puzzle 2:

Push the Random button once. Whatever it dispenses is what it is (If it gives Mars it's Mars, Snickers it's Snickers.)

Whatever is labeled what you got is the other one. (If you got Mars, then the one labeled Mars is Snickers. If you got Snickers, then the one labeled Snickers is Mars.)

The third is random.

(The key is that you know that all three buttons are wrong. Once you know which the one labeled Random is, that's the only way that none of the labels is accidentally right.)

[ironphoenix.livejournal.com]

The first one is pretty neat.

Start with a difference of squares factorization: p^2 - 1 = (p-1) (p+1)

Now, figure out a couple of things about p-1 and p+1. I'll use modulo notation; if and only if a is evenly divisible by b, a mod b = 0.

p mod 2 can't be 0, so it must be 1, therefore (p+1) mod 2 = 0 and (p-1) mod 2 = 0. Also, either (p-1)/2 mod 2 = 0, in which case (p-1) mod 4 = 0, or (p-1)/2 mod 4 = 1, in which case (p-1+2) mod 4 = (p+1) mod 4 = 0.

Also, p mod 3 can't be 0, so p mod 3 must be 1 or 2. If p mod 3 = 1, (p-1) mod 3 = 0, and if p mod 3 = 2, (p+1) mod 3 = 0.

From the above, one of (p+1) and (p-1) must be divisible by 4, and the other must be still divisible by 2; also, one of them must be divisible by 3. Multiplying 2, 3, and 4, we find that the product of (p-1) and (p+1) must be divisible by 24.

[ironphoenix.livejournal.com]

2. If all the labels are guaranteed to be wrong, you only need to spend $1 and push the button marked random. It should have the label for the specific kind of bar it delivers. The other specific label then moves to the button which was labeled with the kind of chocolate bar you got, and the Random label goes to the button which was marked with the ind of chocolate bar you didn't get.

[thornae.livejournal.com]

So, #2 first because it's the easy one: Provided you know that all three buttons are incorrectly labelled, I believe the answer is $1. You push the Random button, if you get a Mars, then it's actually the Mars button, leaving labels buttons labelled Snickers and Mars which you know are actually Random and Snickers - since the Snickers button is definitely not Snickers. And now I've got Snickers semantic satiation.

#3, I didn't know of, and initially thought I had a solution using 3 groups of 4 marbles, but then realised that about 50% of the time, it needs a 4th weighing to solve. Will sleep on it.


#1 is very interesting, and I suspect has something to do with 24 being 2³ * 3, but I'm far too foggy of brain to math it out. Might have to cheat and look up the solution, as it's a fascinating little mathoid.


ETA (after looking at the answer): Oh, right - factoring into (p-1)(p+1) where p > 3, and it all falls out. Hah, that's very neat.

[metahacker.livejournal.com]

Ever since Piers Anthony used #3 as the basis for an entire chapter, with souls in place of marbles, I have detested logic puzzles. :P

[theweaselking.livejournal.com]

.... I vaguely remember that. The Immortals books, right? The one where there's a theological "debate" held with an uneducated twelfth century peasant as absolute moderator/judge?

[ronebofh.livejournal.com]

Guessing someone already answered, but here's my sloppy answer for #1.

p²-1 equals p+1 times p-1. Given p-1, p, and p+1, one of them is a multiple of 3. Given that p-1 and p+1 are even, one of them is a multiple of 2, and the other will be a multiple of 4. 2*3*4 == 24.

[theweaselking.livejournal.com]

There's been several right answers. Yours is one of them! Rescreening it now.

[skiriki.livejournal.com]

I'll answer #3 -- weigh six marbles against six, take heavier bunch; halve, and weigh three against three, take heaviest bunch again; weigh any two against each other. If both remain even, it is the one you did not weigh, otherwise pick the heaviest.

[theweaselking.livejournal.com]

Nope! That only works if the outlier is HEAVIER.

If the outlier is LIGHTER, you would weigh 6v6, discard the light half, weigh 3v3.... and they level.

Now you have one measurement left to determine which of the light half is the light one, which AFAIK can't be done.

[skiriki.livejournal.com]

Bollocks, teaches me right not to read too well. :D

[skington.livejournal.com]

I have no idea about puzzle 1. I suspect there's some maths logic to do with integrals and derivations, but I never grokked that stuff.

Puzzle 2: minimum required is $3. Press button 1: get foo chocolate bar. Press button 2: get bar chocolate bar. Press button 2 again: get foo chocolate bar. Ergo button 2 is the random button, button 1 will always deliver foo chocolate bar (whether it's Mars or Snicker); ergo button 3 is the button that delivers whatever button 1 doesn't.

Puzzle 3: gah, I never remember this one. Weigh the first four marbles against the next four, and when Monty Hall says one weighs more than the other, pick the remaining four.

[skington.livejournal.com]

Puzzle 2: if you're not asking "what's the smallest convenient number of results that could produce certainty" but "what's the smallest number of results that could produce certainty in a world full of coincidences", that's trickier. You could be really unlucky (or lucky, depending on whether you like Snickers or Mars bars and which way random chance goes), and the button that produces a random chocolate bar could be "stuck" on the same choice for dozens or hundreds of presses, so you couldn't distinguish between e.g. the Snickers button or the random button, because both have, so far, only ever produced Snickers bars.

But that assumes a perfectly spherical vending machine of uniform density. So I'm assuming the limiting factor is the number of chocolate bars of each type that the machine contains. Let's suppose it contains 50 Mars bars and 50 Snickers bar, and the random number gods are against us, so button A gives us a Mars bar and buttons B and C give us a Snickers bar. We know one of buttons B or C has to be the "always Snickers", and button A therefore has to be the "always Mars" button, so we're out $3, and we have 49 Mars bars left and 48 Snickers bars.

We then press buttons B and C each another 24 times, which costs us another $48. We get a Snickers bar from each of them.

Thereafter, assuming that if the machine is out of what you want you get your money back, we feed a dollar into the machine, pressing button B or C, until one of them gives us a Mars bar.

So the total cost is VENDING_MACHINE_CAPACITY + 2?

Or, alternatively, you could tell the guy in charge of the vending machine "hey, can I rig up my electrician's tools to your machine?" or "you set it up wrong, you probably know what you did wrong better than I did".

[theweaselking.livejournal.com]

The answer I'm looking for for Puzzle #2 is "what's the minimum amount of money required to know, for certain, which button does what". And while a service call to get the buttons changed would work, it would cost more than the right answer.

[the-gneech.livejournal.com]

These things always make my brain lock up like Robbie the Robot, but I gave the last one a try. I did manage to create a scenario that could find the result in three, but only 1/4 of the time, which was this:

Put three marbles on one side and six on the other.

-If the six are exactly twice as heavy, none of the nine weighed marbles are the oddball. Remove them and place one each of the unweighed marbles on the scale. If they are still equal, neither of these are the oddball, so replace one with the final (odd) marble to find out if it's heavier or lighter. If they are not equal, replace the heavier one with a previously-weighed marble. If the scale levels, the removed oddball was heavier. If the scale remains tipped, the remaining oddball is lighter.

Unfortunately, if the six AREN'T exactly twice as heavy, that means you know that one of the weighed marbles is the oddball, and you have two weighings left to sort through nine marbles, which I couldn't work out before my brain gave up for the night. Am I even close to being on the right track?

-TG

[theweaselking.livejournal.com]

An old-style balance cannot tell you "twice as heavy". It can only tell you "these sides are in balance" or "one side is heavier than the other" - the side that's heavier will tilt the balance fully (it may take a few seconds). In order for it to do things like "twice as heavy" it would have to have some kind of resistance mechanism in the pivot, and that would screw it up for use as a balance.

So no, you're not close to the right track.

[the-gneech.livejournal.com]

Ah, okay.

-TG

[reynardo.livejournal.com]

Question 1) OK, I've got as far as 12, and I can see that it has to be 24 as well, but I can't prove the last little bit. Going to ask a friend for help on it. (And I'm also pretty chuffed at getting as far as 12, I have to say :-)

[secretagentmoof]

#1 p^2 - 1 = (p+1)(p-1). either p+1 or p-1 must be a factor of 3, as p itself cannot itself have a factor of 3 (as it's prime), and out of any three consecutive whole numbers one of them must be divisible by three. Similarly, as we are guaranteed that p is odd (as it's prime) p+1 and p-1 are consecutive even integers, and thus one must be divisible by two (and not four), and the other by four.

#2: $1. Push random; it'll produce either S or M. If it gives S, what's labeled M must be random (as it can't be M), and what's labeled S must be M. Similarly, if label-R gives M, label-M is S, label-S is random.

#3 I hated that fucking puzzle because it requires a series of arbitrary states and I always just looked up the answer in the Spellbreaker walkthrough.

I think I've seen all of the questions (or variations therein) before, so it feels unfair. I blame Raymond Smullyan.

[reynardo.livejournal.com]

Right - got it.

OK, any prime number greater than 3, p, is going to be odd. Therefore the two bracketing numbers will be even, and one will be a multiple of 4.

Also that same number will be either one greater or one less than a multiple of 3, because if it *was* a multiple of 3, it wouldn't be prime. And out of any 3 consecutive numbers, one of them will be a multiple of 3.

So, p²-1 = (p+1)(p-1)

Assume p+1 is the multiple of 4. P-1 will also be a multiple of 2, and one or the other will be a multiple of 3.

(Or you could take it the other way around. Either works)

Thus the product of p+1 and p-1 must have 2x4x3 as one of its factors.

(Kudos to lederhosen for the help.

[calankh.livejournal.com]

1. something to do with 2^2 * 3 being 24.

2. $1. hit random. whatever it spits out is what it is supposed to be labeled, say mars. Then you have two buttons labeled mars and snickers. since you know they are wrong, the one labeled mars must be snickers, and the one labeled snickers must be random. vice versa if the random spits out a snickers.

3. my intuition here is that the solution involves weighing all 12 in groups of 6 just scrambled each time. but not sure if that will get you down to knowing it's a single marble in 3 groupings.