User dan - MathOverflow

Answer by Dan for Which mathematicians have influenced you the most?

2010-05-21T17:12:08Z

Raymond Smullyan, in elementary school. His book "Alice in Puzzleland" was a childhood favorite of mine and is what and inspired a life long interest in math.

Generalization of Finch Cheney's 5 Card Trick

2010-04-07T21:43:25Z

The Original Fitch Cheney puzzle goes like this:

A Volunteer from the crowd chooses any five cards at random from a deck, and hands them to you so that nobody else can see them. You glance at them briefly, and hand one card bakc, which the volunteer then places face down on the table to one side. You quickly place the remaining four cards face up on the table, in a row from left to right. Your confederate, who has not been privy to any of the proceedings so far, arrives on the scene, inspects the faces of the four cards, and promptly names the hidden fifth card.

The solution to this is:

One of the 4 suits must be represented 2 times in your set of 5 cards due to the pigeon hole principle. Consider the 13 cards of that suit A=1,... K=13 to be arranged in a clockwise circle. We can see that the cards are at most 6 away from each other, meaning counting clockwise one of them lies at most 6 vertices past the other. Use the "higher" one as the hidden card and place the "lower" one as the first card face up on the table.

Now, using an established value for all 52 cards in the deck, the remaining 3 cards can be placed in 6 orders, Low-Middle-High=1, LHM=2, MLH=3, MHL=4, HLM=5, and HML=6, and give each one of these a value of +1,..., +6 from the first card.

For example, Jc, 2c, 3h, 4d, 2s are handed to you. Choosing the lower club, (2-Jack(11) Mod 13 is 4, so the Jack is the lower one and the 2 is +4 from the jack. Hide the 2c and place the Jc in the first spot. Then using MHL, our +4 value, we arrange the remaining 3 cards with the 3 first, than the 4, now the 2. This implies that the hidden card is a club, and it is +4 from the Jc in the first spot, so we know it is the 2c.

The 124 card solution is discussed in the January 2001 issue of Emissary or Michael Kleber’s article in The Mathematical Intelligencer, Winter 2002 (which I don't have access to).

It can be shown that with 5 cards there is a strategy to do the trick on a deck of size up to 124 cards (n!+(n-1)).

My question is this: With the audience choosing n cards out of a deck of size (n!+(n-1)) and one card being hidden, how many unique strategies could the magician and the assistant use?

Diophantine: Ax+B=Cy

2010-03-15T17:53:35Z

For some given positive integers A, B, and C, how can I find the lowest value of x such that:

Ax+B=Cy

where x,y also positive integers.

For example 10x+6=7y the lowest value of x is x=5 where y=8.

I thought I could use Euclidean algorithm, but I haven't figured out how I could apply it here. Is there a different general algorithm for solving this?

Thanks,

Dan

(Not homework, just related something I'm working on)

Weird relationship: Exists x(not 1), x^3=1 MOD M if and only if 3|Phi(M)

2010-01-16T17:27:01Z

I found a weird relationship and was hoping someone could explain why it happens:

In module M, there exists a x not equal to 1, such that x^3=1

If and only if:

3 divides the Euler Totient Phi function of M.

Any insights? (if this is not accurate, please let me know, but this relationship seems to hold true for all modulo bellow 300)

Thanks.

(Sorry if my tagging is bad... don't know enough to properly tag this)

Answer by Dan for Pascal Triangle and Prime Numbers

2009-12-17T17:52:43Z

Looks like some people already came up with some better answers, so I'll just quickly mention that you may like solving problems on ProjectEuler.net as some of the problems are right up this way of thinking.

For one of the problems I created the following way to determine the number of times p divides M choose N:

M!/(N!*(M-N)!)
K(M,p)-K(N,p)-K(M-N,p)
Where K(X,p) is the number of times p divides X! and is equal to:
K(X,p)=Floor(X/p)+Floor(X/p^2)+Floor(X/p^3)+...

(Quick explination: Even for each p^2 bellow X there are two factors of p added to the product, but one was already counted in Floor(X/p), so we just add the extra one for the new power of p)

Probably not original, but it was fun to come up with it.

Dan

Comment by Dan

2010-03-15T19:43:31Z

Thanks. Took me a bit of tooling around but I now got it. Taking Extended Euclidean gives me 10*2+1=7*3. Which gives 10*12+6=7*18. This is just one possible answer, to get the one I want I must take y MOD A (18 mod 10) and x MOD C which gives me 10*5+6=7*8.