Rutgers Discrete Mathematics Seminar

Title: Representing Integers ONLY using ONE

Speaker: Edinah Gnang, IAS

Date: Tuesday, February 25, 2014 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


Suppose that you have a Reverse Polish Calculator where the only functioning keys are the "plus", "times", and "power", "1", and, of course the "Enter" key. In how many ways can you express 40? (Ans.: 2601671905509333123020 ways). Also, how to generate, uniformly at random, one such expression? Also, what is the shortest way of doing it? In our talk we present an answer to these questions and discuss their connections with complexity theory.